Data Structures: Linked Lists

Introduction to LinkedLists

What is a Linked List?

A linked list is a data structure that consists of a group of nodes that together represent a sequence.

Each node is composed of a generic data element and a reference to the next node in the sequence.

Comparison to Arrays

• Arrays can be traversed randomly, while linked lists must be traversed sequentially.
• Linked list can grow dynamically, while arrays must define a size before its instantiation.
• Because arrays have fixed sizes, we must know the upper limit of the number of elements in advance.
• Memory allocation for an array is compile time and linked list is run time.
• Inserting elements into an array is expensive since we have to shift all elements coming after the insertion node over one. For linked lists, however, you can simply insert a node by reconfiguring the node coming before it.
• Linked lists allow for dynamic resizing, making it easy to add more data.

Types of Linked Lists

There are several types of linked lists, but we'll begin by looking at the simplest - the singly-linked list.

A singly-linked list has only a NEXT pointer, which points to the next node in sequence. A doubly-linked list would have an additional PREV pointer that points to the previous node.

There is also a circular linked list, in which one next NEXT pointer points to a previous element.

The linking of a group of NODE objects is what gives us a linked list. Each NEXT pointer connects one node to the next. If the node is at the end, its NEXT pointer will point to NULL.

Head and Tail

Additionally, there are two more pointers in a linked list. The HEAD of the linked list holds the first node in the list, while the TAIL holds the last.

Performance

Implementing a Node

We'll be using Java Generics in our guide here, so it's highly recommended to learn that before moving on.

Implementing a Node is simple. It should store a generic element along with get and set methods to retrieve and mutate that element.

Additionally, since we are using this for a singly-linked list, it should have a next pointer, which points to the next node in the sequence.

/** 
 *  A Node object implementation to hold data in a LinkedList.
 *  
 *  @author  CodeSnipcademy
 *  @version  1.0.0 Jan 07, 2015
 */
public class Node<E> {
  private Node<E> next;   // Points to the next Node
  private E data;         // Holds data to be     | stored in Node
  /**
   * Create a new node with no next Node and no     | data.
   */
  public Node() {
    this(null, null);
  }
  /** 
   * Create a new Node with given data.
   *
   * @param  inputData - element to be stored
   */
  public Node(E inputData) {
    this(inputData, null);  
  }
  /** 
   * Create a new Node with data at the given index.
   * 
   * @param  inputData - element to be stored
   * @param  inputNext - next Node to be pointed to 
   */ 
  public Node(E inputData, Node<E> inputNext) {
    this.next = inputNext;
    this.data = inputData;
  }
  /**
   * Retrieve data of current Node.
   * @return  data - data stored in this Node
   */     
  public E getData() {
    return this.data;
  }
  /**
   * Set new data to Node.
   * @param  inputData - data stored in this Node
   */     
  public void setData(E inputData) {
    this.data = inputData;
  }
  /**
   * Return the next Node in the sequence.
   * @return  next - next data in the Node
   */     
  public Node<E> getNext() {
    return this.next;
  }
  /**
   * Set next value in current Node.
   * @param  inputNode - next Node to be set
   */     
  public void setNext(Node<E> inputNode) {
    this.next = inputNode;
  }
}

Implementing a Linked List

Parameters

Our linked list should have a head and tail, which point to the first and last nodes. Additionally, a integer value that contains how many nodes are in our list (listSize) is useful for our purposes.

Node Inner Class

To implement a linked list, we need a node class that holds an element and a pointer to the next node. We create this class within the LinkedList object.

Adding / Insertion

There are three methods for adding: addToHead(), addToTail(), and addAfterIndex().

To add, we must create a new node. Then we traverse the linked list until we get to the targetNode, which is where we are to insert our new node after.

Then we have to set our new node's next to the targetNode's next. Then our targetNode's next must be set to our newNode. Don't forget to increment the listSize!

Node newNode = new Node<>(data);
// Traverse to the Node that we want to insert after
Node targetNode = this.head;
for (int i = 1; i < index; i++) {
  targetNode = targetNode.getNext();
}
newNode.setNext(targetNode.getNext());
targetNode.setNext(newNode);
this.listSize++;

Removing / Deleting

We have three similar methods as in adding: removeHead(), removeTail(), and removeAtIndex().

Additionally, when removing from a linked list, it is customary to return the data being removed.

We first load our previousNode variable with the head of the linked list, then traverse until we get to the user's desired index. Then we place that node's data into the nodeData variable, which we'll use to return. To do the actual deleting, we link the previousNode to the next-next node. Java's garbage collector can take care of the rest, but if you're using C, you must deallocate the memory.

Node previousNode = this.head;
// Reaches to the previous of the node we want to remove
for (int i = 1; i < index - 1; i++) {
  previousNode = previousNode.getNext();
}
E nodeData = previousNode.getNext().getData();
previousNode.setNext(previousNode.getNext().getNext());
listSize--;
return nodeData; 

Full code

Here's the entire code. There are some intracacies of adding or removing from the head and tail that you may want to review.

/** 
 * A <code>LinkedList</code> implementation that uses the Node class.
 * 
 * @author Code Snipcademy 
 * @version 1.0.0 Dec 07, 2015
 */
public class LinkedList<E> {
  protected Node<E> head;      // First node
  protected Node<E> tail;      // Last node
  protected int listSize;      // Size of  LinkedList
  /**
   * Default constructor for LinkedList.
   * 
   * Points head and tail to null.
   * ListSize is initially zero.
   */
  public LinkedList() {
    this.head = null;
    this.tail = null;
    this.listSize = 0;
  }
  /**
   * Output LinkedList in String format.
   */
  public String toString() {
    Node<E> currentNode = this.head;
    StringBuilder output = new StringBuilder();
    while (currentNode != null) { 
      output.append("[");
      output.append(currentNode.getData());
      output.append("]");
      currentNode = currentNode.getNext();
    }
    return output.toString();
  }
  /**
   * Return the amount of Nodes in our LinkedList.
   */
  public int size() { 
    return this.listSize; 
  }
  
  /**
   * Return true if LinkedList is empty.
   *
   * @return true if no Nodes in LinkedList.
   */
  private boolean isEmpty() { 
    return this.size() == 0; 
  }
  /**
   * Clears the list - all elements are to be removed.
   * 
   * To be used when removing last element from LinkedList.
   * 
   * @return head element.
   */
  public E clear() {
    E headData = this.get(1);
    head = null;
    tail = null;
    listSize = 0;
    return headData;
  }
  /**
   * Add a node with element data to end of LinkedList.
   *
   * @param data - element to be stored
   */   
  public void addToTail(E data) {
    Node<E> newNode = new Node<>(data);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = head;
    } else {
      (this.tail).setNext(newNode);
      this.tail = newNode;
    }
    this.listSize++;
  }
  /**
* Add a node with element data to front of LinkedList.
   *
   * @param data - element to be stored
   */
  public void addToHead(E data) {
    Node<E> newNode = new Node<>(data);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = head;
    } else {
      newNode.setNext(this.head);
      this.head = newNode;
    }
    this.listSize++;
  }
  /**
   * Add a node after a specific index.
   * 
   * index = 0 to add to front, n to add after element n.
   * 
   * @param data - element to be store
   * @param index - point at which to add data
   */ 
  public void addAfterIndex(E data, int index) {
    if (index <= 0) { 
      this.addToHead(data);
    } else if (index >= this.size())  {
      this.addToTail(data);
    } else {
      Node<E> newNode = new Node<>(data);
      // Traverse to the Node that we want to insert after
      Node<E> targetNode = this.head;
      for (int i = 1; i < index; i++) {
        targetNode = targetNode.getNext();
      }
      newNode.setNext(targetNode.getNext());
      targetNode.setNext(newNode);
      this.listSize++;
    }
  }
  /**
   * Returns object at the specified position of LinkedList.
   *
   * @param index - index of element to retrieve.
   * @return element at that index.
   */
  public E get(int index) {
    if (index <= 0 || index > size()) {
      return null;
    }
    Node<E> currentNode = this.head;
    for (int i = 1; i < index; i++) {
      currentNode = currentNode.getNext();
    }
    return currentNode.getData();
  }
  /**
   * Remove from the tail end of LinkedList.
   * 
   * @return data stored in tail Node.
   */
  public E removeTail() {
    if (this.isEmpty()) {
      return null;
    } else if (this.size() == 1) {
      return this.clear();
    } else {
 
      Node<E> previousNode = this.head;
      for (int i = 1; i < size()-1; i++) {
        previousNode = previousNode.getNext();
      }
  
      E returnData = get(this.size());
      previousNode.setNext(null);
      this.tail = previousNode;
  
      listSize--;
      return returnData;
    }
  }
  /**
   * Remove from the front of the LinkedList.
   * 
   * @return data contained in head node.
   */
  public E removeHead() {
    // If nothing inside of the LinkedList
    if (isEmpty()) {
      return null;
    } else if (size() == 1) {
      return clear();
    } else {
      E headData = get(1);
      this.head = head.getNext();
      this.listSize--;
      return headData;
    }
  }
    
  /**
   * Remove from a specified index in LinkedList.
   * 
   * @return data contained at the index.
   */ 
  public E removeAtIndex(int index) {
    if (index <= 1) {
      return removeHead();
    } else if (index >= size()) { 
      return removeTail();
    } else {
      Node<E> previousNode = this.head;
// Reaches to the previous of the node we  want to remove
      for (int i = 1; i < index - 1; i++) {
        previousNode = previousNode.getNext();
      }
      E nodeData = previousNode.getNext().getData();
      previousNode.setNext(previousNode.getNext().getNext());
      listSize--;
      return nodeData;
    }
  }
  public void insert(E[] testInput) {
    for (int i = 0; i < testInput.length; i++) {
      this.addToTail(testInput[i]);
    }
    
  }
  
}