---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.14.7
kernelspec:
  display_name: Java
  language: java
  name: java
---

(chapter5:solutions)=
# Solutions to the Practice Problems

(chapter5:solutions:node)=
## But First, What is a Node?
1.
   ```{code-block} java
   Node<Integer> node1 = new Node<>(100);
   Node<Integer> node2 = new Node<>(15);
   Node<Integer> node3 = new Node<>(150);
   Node<Integer> node4 = new Node<>(75);
   ```
2. ```{code-block} java
   node2.setNext(node4);
   node4.setNext(node1);
   node1.setNext(node3);
   ```
3. ```{code-block} java
   node2.getNext().getNext().getNext().getValue()
   ```
4. Use your own name, but here is a solution for "Rosanna":
   ```{code-block} java
   Node<Character> node1 = new Node<>('R');
   Node<Character> node2 = new Node<>('o');
   Node<Character> node3 = new Node<>('s');
   Node<Character> node4 = new Node<>('a');
   Node<Character> node5 = new Node<>('n');
   Node<Character> node6 = new Node<>('n');
   Node<Character> node7 = new Node<>('a');
        
   node1.setNext(node2);
   node2.setNext(node3);
   node3.setNext(node4);
   node4.setNext(node5);
   node5.setNext(node6);
   node6.setNext(node7);
   ```

[Back to Questions](chapter5:node:practice)

(chapter5:solutions:linkedList)=
## The Linked List Data Type
1. ```{code-block} java
   public Node<V> getHead(){
      return head;
   }
   ```
2. ```{code-block} java
   public Node<V> getTail(){
      return tail;
   }
   ```
3. ```{code-block} java
   public int getSize(){
      return size;
   }
   ```
[Back to Questions](chapter5:linkedList:practice)

(chapter5:solutions:operations)=
## Operations (Methods) for a Linked List

1. ```{code-block} java
   LinkedList<String> favFoods = new LinkedList<>();
   favFoods.addFirst("blueberries");
   favFoods.addFirst("pizza");
   favFoods.addFirst("fresh garden salad");
   favFoods.addFirst("vanilla ice cream");
   favFoods.addFirst("pepper steak");
     
   System.out.println("My favorite foods are: " + favFoods);
   ```
2. ```{code-block} java
   public class CourseMark {
      private String course;
      private double mark;
    
      public CourseMark(String course, double mark){
         this.course = course;
         this.mark = mark;
      }
    
      @Override
      public String toString(){
         return course + " " + mark;
      }
   } //class CourseMark

   //In main, or somewhere else:
   LinkedList<CourseMark> myMarks = new LinkedList<>();
   myMarks.addFirst(new CourseMark("AUCSC 112", 97));
   myMarks.addFirst(new CourseMark("AUMAT 116", 85));
   myMarks.addFirst(new CourseMark("AUMAT 120", 92));
   myMarks.addFirst(new CourseMark("AUIDS 101", 78));
        
   System.out.println("My courses and marks: " + myMarks);
   ```
3. ```{code-block} java
   /**
    * Finds the average of the integer values in a linked list.
    * 
    * @param intList - Linked List made of Integers
    * @return - the average of the integers in the list.  NOTE: if the
    *           list is empty, returns 0.
    */
    public static double findAvLL(LinkedList<Integer> intList){
       Node<Integer> cursor = intList.getHead();
       double sum = 0;
        
       if (cursor == null){ //nothing in list
          return 0;
       }
        
       while (cursor != null){
          sum = sum + cursor.getValue();
          cursor = cursor.getNext();
       }
        
       return sum / intList.getSize(); 
   }
   ```
4. ```{code-block} java
   /**
    * Add a node onto the end of the list, with node containing
    * the value given.
    * 
    * @param aValue - value to put into the node to add
    */
   public void addLast(V aValue){
      Node<V> aNode = new Node(); 
      aNode.setValue(aValue);
       
      if (size == 0){
         head = aNode;
      }
      else{
         tail.setNext(aNode);
      }
        
      tail = aNode;       
      size++;
   }
   ```
5. ```{code-block} java
   /**
    * Adds a node into the linked list, the node has 1st value and
    * is inserted right after the node with the 2nd value.
    * 
    * @param addValue - insert a node with this value
    * @param addAfterValue - right after a node with this value
    * NOTE:  if the 2nd value is not in the linked list, nothing is
    *        done but an error message is printed.
    */
   public void addAfter(V addValue, V addAfterValue){
      Node<V> location = findNode(addAfterValue);
       
      if (location == null){
         System.out.println("ERROR - value " + addAfterValue + " not found");
      }
      else{
         Node<V> newNode = new Node(addValue);
         newNode.setNext(location.getNext());
         location.setNext(newNode);
            
         if (tail == location){ //adding at the end
             tail = newNode;
         }
      }
   }
   ```

[Back to Questions](chapter5:operations:practice)

(chapter5:solutions:otherKinds)=
## Other Kinds of Linked Lists
1. ```{code-block} java
   public class DNode<V> {
      //Instance Fields ===========================
      private V value;
      private DNode<V> next;
      private DNode<V> previous;

      //Constructors ==============================
      public DNode(V inValue, DNode<V> toNode, DNode<V> fromNode) {
         value = inValue;
         next = toNode;
         previous = fromNode;
      }

      public DNode(V inValue) {
         this(inValue, null, null);
      }

      public DNode() {
         this(null, null, null);
      }

      //Getters ====================================
      public V getValue() {
         return value;
      }

      public DNode<V> getNext() {
         return next;
      }
    
      public DNode<V> getPrevious() {
         return previous;
      }

      //Setters =====================================
      public void setValue(V value) {
         this.value = value;
      }

      public void setNext(DNode<V> next) {
         this.next = next;
      }
    
      public void setPrevious(DNode<V> previous) {
         this.previous = previous;
      }
   }
   ```
2. ```{code-block} java
   /**
     * Adds a node with an element to the "front" of the list.
     *
     * @param value - the new information to store in the new node
     */
    public void addFirst(V value) {
        if (size == 0) { //if list is empty, then this node is the only node
            entry = new DNode<V>(value); 
            entry.setNext(entry); //circle on itself        
        }
        else { //put node in at entry, list has at least 1 node already
            DNode<V> newNode = new DNode<V>(value); 
            newNode.setNext(entry.getNext());
            entry.setNext(newNode);
            entry = newNode;
        }
        
        size++;
    }//addFirst
   ```
3. ```{code-block} java
   public void addLast(V aValue){
      DNode<V> aNode = new Node(); 
      aNode.setValue(aValue);
       
      if (size == 0){
         head = aNode;
         tail = aNode;
      }
      else{
         aNode.setPrev(tail);
         tail.setNext(aNode);
      }
        
      tail = aNode;       
      size++;
   }
   ```
4. End of double: $\theta(1)$<br>
   End of single: $\theta(1)$
5. $\theta (n)$ as we would have to find the middle
6. 
   ```{image} figures/doubleCircle.png
   :alt: A doubly linked circular list
   :align: left
   :width: 50%
   ```
   Advantage: can traverse easily in both directions.<br>
   Disadvantage: extra memory required for the 2nd link.

<br><br><br><br><br><br>

[Back to Questions](chapter5:otherKinds:practice)

<br><br>