Nodes and Linked Lists

Nodes

• Nodes are objects that store data and point to other nodes
• Nodes contain a single datum or multiple pieces of data
• Generic
• Many data structures are implemented using nodes

Visually, we can think of nodes in the following way:

Generic Node Class

public class Node<E> {

  private E data;
  private Node<E> next;

  public Node(E data, Node<E> next) {
    this.data = data;
    this.next = next;
  }

  public Node(E data) {
    this(data, null);
  }

  public E getData() {
    return data;
  }

  public void setData(E data) {
    this.data = data;
  }

  public Node<E> getNext() {
    return next;
  }

  public void setNext(Node<E> next) {
    this.next = next;
  }
}

Implementing Lists with Nodes

• Need to keep track of head of list
• Need to keep track of size of list
• The list is built with with nodes pointing to each other
• In an empty list, head points to null and size = 0

public class List<E> {

  private Node<E> head;
  private int size;

  public List() {
    this.head = null;
    this.size = 0;
  }
  
  //...

Adding to a List

Adding to an empty list

• Update head to new node
• make sure new node points to null

Adding to the front of a list

• Change head to point to new node
• Update new node to point to what head used to point to

Adding to the end of a list

• Iterate through list until you read end (node points to null)
• Make end node point to new node
• Make new node point to null

Adding somewhere in between

• Find node/index that comes before new node
• Set before node's point to new node
• Set new node's pointer to before node's next point

  /**
   * Inserts the item at the given index, pushing any exiting items to right.
   * If index == size(), adds item to the end of the list.
   * Throws IndexOutOfBoundsException if the index is outside of list range.
   */
  public void add(int index, E item) {
    if (index == 0) {
      //special case: adding to head of list
      this.head = new Node<E>(item, this.head);
      this.size++;
    }else {
      Node<E> before = this.getNode(index - 1); //also checks index for us
      Node<E> toAdd = new Node<E>(item, before.getNext());
      before.setNext(toAdd);
      this.size++;
    }
  }

Getting From a List

Returning the node at a particular index

/**
 * Returns the node at the given 0-based index in this list.
 * Throws IndexOutOfBoundsException if the index is outside the list.
 */
  private Node<E> getNode(int index) {
    if (index < 0 || index >= this.size) {
      //always thrown if list is empty
      throw new IndexOutOfBoundsException("index: " + index +
          "; size: " + this.size);
    }

    //start at head and move to next node index times.
    Node<E> curr = this.head;
    for (int i = 0; i < index; i++) {
      curr = curr.getNext();
    }
    return curr;
  }

What if we just wanted to return the data?

  /**
   * Returns the item at the given 0-based index in this list.
   * Throws IndexOutOfBoundsException if the index is outside of list range.
   */
   public E get(int index) {
     return this.getNode(index).getData();
   } 

toString

 /**
   * Returns a String representation of this lists contents using the
   * format: [item1, items2, item3]
   */
  @Override public String toString() {
    String str = "[";
    Node<E> curr = this.head;
    while (curr != null) {
      str += curr.getData();  //implicitly calls toString on data item
      curr = curr.getNext();
      if (curr != null) {
        str += ", ";
      }
    }
    str += "]";
    return str;
  }

Removing from Linked List

Removing from front

• Change head to point to "node to be removed" next

Removing from end of list

• Determine next to last node in list
• Set next to last node's point to null

Removing Within List

• Find node previous to node to be removed
• Set previous node's next to node to be removed next

 /**
   * Removes and returns the item at the given 0-based index in this list.
   * Throws IndexOutOfBoundsException if the index is outside of list range.
   */
   public E remove(int index) {
     if (index == 0 && this.head != null) {
       //special case: removing first node
       E item = this.head.getData();
       this.head = this.head.getNext();
       this.size--;
       return item;
     }else {
       Node<E> toRemove = this.getNode(index);  //confirm that index is valid
       Node<E> before = this.getNode(index - 1);
       before.setNext(toRemove.getNext());
       this.size--;
       return toRemove.getData();
     }
   }