Linked Lists

Linked List Overview

A LinkedList (singly-linked list) class in Java has the following attributes:

a public head Node instance variable
a constructor with a head property
.addToHead() to add new nodes to the head
.addToTail() to add new nodes to the tail
.removeHead() to remove the head node
.printList() to output a human-readable ordered list of node data values

public class LinkedList {

  public Node head;

  public LinkedList() {
    this.head = null;
  }

  public void addToHead(String data) {
    Node newHead = new Node(data);
    Node currentHead = this.head;
    this.head = newHead;
    if (currentHead != null) {
      this.head.setNextNode(currentHead);
    }
  }

  public void addToTail(String data) {
    Node tail = this.head;
    if (tail == null) {
      this.head = new Node(data);
    } else {
      while (tail.getNextNode() != null) {
        tail = tail.getNextNode();
      }
        tail.setNextNode(new Node(data));
    }
  }  

  public String removeHead() {
    Node removedHead = this.head;
    if (removedHead == null) {
      return null;
    }
    this.head = removedHead.getNextNode();
    return removedHead.data;
  }

  public String printList() {
    String output = "<head> ";
    Node currentNode = this.head;
    while (currentNode != null) {
      output += currentNode.data + " ";
      currentNode = currentNode.getNextNode();
    }
    output += "<tail>";
    System.out.println(output);
    return output;
  }  

}

Linked List Constructor

A Java LinkedList constructor takes no parameters and sets the head instance variable to null.

public LinkedList() {
  this.head = null;
}

Adding to the Head

A Java LinkedList class can implement a public void .addToHead() instance method for adding new data to the head of the list. .addToHead() takes a single String data argument. It uses data to create a new Node which it adds to the head of the list.

public void addToHead(String data) {
  Node newHead = new Node(data);
  Node currentHead = this.head;
  this.head = newHead;
  if (currentHead != null) {
    this.head.setNextNode(currentHead);
  }
}

Adding to the Tail

A Java LinkedList class can implement a public void .addToTail() instance method for adding new data to the tail of the list. .addToTail() takes a single String data argument. It uses data to create a new Node which it adds to the tail of the list.

public void addToTail(String data) {
  Node tail = this.head;
  if (tail == null) {
    this.head = new Node(data);
  } else {
    while (tail.getNextNode() != null) {
      tail = tail.getNextNode();
    }
      tail.setNextNode(new Node(data));
  }
}

Removing the Head

A Java LinkedList class can implement a public String .removeHead() instance method for removing the head of the list. .removeHead() takes no arguments. It removes and returns the head of the list’s data, and sets the head’s next node as the new head.

public String removeHead() {
  Node removedHead = this.head;
  if (removedHead == null) {
    return null;
  }
  this.head = removedHead.getNextNode();
  return removedHead.data;
}

Printing the List

A Java LinkedList class can implement a public String .printList() instance method for printing the list in a clear and readable way and takes no arguments. It iterates through the list and adds the data from each element to a string, which it prints and returns at the end of the method.

public String printList() {
  String output = "<head> ";
  Node currentNode = this.head;
  while (currentNode != null) {
    output += currentNode.data + " ";
    currentNode = currentNode.getNextNode();
  }
  output += "<tail>";
  System.out.println(output);
  return output;
}

Removing a node from the middle of a linked list

When removing a node from the middle of a linked list, it is necessary to adjust the link on the previous node so that it points to the following node. In the given illustration, the node a1 must point to the node a3 if the node a2 is removed from the linked list.

Linked List data structure

A linked list is a linear data structure where elements are not stored at contiguous location. Instead the elements are linked using pointers.

In a linked list data is stored in nodes and each node is linked to the next and, optionally, to the previous. Each node in a list consists of the following parts:

data
A pointer (Or reference) to the next node
Optionally, a pointer to the previous node

A linked list with each node holding its data and pointing to the next node.

Adding a new head node in a linked list

When adding a new node to the start of a linked list, it is necessary to maintain the list by giving the new head node a link to the current head node. For instance, to add a new node a0 to the begining of the linked list, a0 should point to a1.

The Head Node in Linked Lists

The first node in a linked list is called the head node. If the linked list is empty, then the value of the head node is NULL.

A linked list structure with Head and Tail pointers.

Implementing a linked list

A linked list exposes the ability to traverse the list from one node to another node. The starting node is considered the head node from where the list can be traversed.