Linked List Implementation in Java

Copy Link LinkedIn Message Facebook Email X

You can take a look at a basic linked list implementation and explore some of the basic operations.

Java Linked List Example

First, look at a possible Node class implementation in Java:

public class Node<T> {
  // The Node list is generic and holds a piece of "data"
  T data;

  // The Node class (this class) has an instance variable
  // which points to another Node object
  Node next;

  // Constructor
  public Node(T data) {
    this.data = data;
    this.next = null;
  }
}

Notice how the Node<> class contains an instance variable called next, which is itself of type Node? This is how one Node object links to another Node object -- next holds the reference to the next item in the list.

Because of this, you can now do something like this, assuming you have a Person class defined:

public class SimpleLinkExample {
  public static void main(String[] args){

    // create a simple Node and pass in a Person object
    Node<Person> node = 
      new Node(new Person("Test", "User1", "[email protected]"));

    // set the "next" variable inside the node object to new Node
    node.next = new Node(new Person("Test", "User2", "[email protected]"));

  }
}

This ability to chain Node objects together using the next variable is what defines the linked list. This is where the dynamic nature of the linked list comes from -- you can link more and more Node objects onto each other, effectively changing the size of the linked list as the program runs.

Of course, in the real world, you don't have to manipulate and manage Node objects directly. You create a MyLinkedList class, which will manage the Node objects. Here's what a linked list might look like implemented in Java:

import Node;

public class MyLinkedList<T>{
  Node<T> head=null;
}

The MyLinkedList class uses the Node class internally, so to recreate the code from above, you can use the following:

public static void main(String[] args){
  MyLinkedList<Person> myPeople = new MyLinkedList();

  myPeople.addHead(new Person("Test", "User1", "[email protected]"));
  myPeople.addHead(new Person("Test", "User2", "[email protected]"));
}

Great, but where does the .addhead() method come from? You can explore how to add, remove, and find information in a linked list.

Add Data to a Linked List

Adding data to a linked list can be done in one of three ways:

1. Add new data at the head of the list.
2. Add new data at the tail of the list.
3. Add new data somewhere in the middle of the list.

You can look at the code for each of these.

1. Add Data at the Head of a List

Adding data to the head of the list occurs quickly because you already know where the head of the list is. Here's how this looks in code:

public void addHead(T data) {
  Node newNode = new Node(data);
  if (head == null){
     head = newNode;
     return;
  } 
  newNode.next = this.head;
  this.head = newNode;
}

So what's going on here? Conceptually, you:

1. Create a new node with the new data to be added.
2. Set the next reference of the new node to be the head of the list.
3. Set the head of the list to be the new node.

This works even if the list is empty since head == null in that case.

Graphically, here's what those steps look like:

2. Add Data at the Tail of a List

Of course, if you can add to the head of a list, you can also add it to the tail. However, this is a little more involved, as you need to find the tail before you can add data to it. If the list is long, this can be time-consuming. You can take a look at the code:

public void addTail(T data) {
  Node newNode = new Node(data);

  // Is the list empty?
  if (this.head == null){
    this.head = newNode;
    return;
  }

  // Find the last item in the list
  Node currentNode = this.head;

  // Find the end of the list
  while (currentNode.next != null)
    currentNode = currentNode.next;

    // Link the new node here
    currentNode.next = newNode;
}

You can see this is a little more involved than simply adding something at the head of the list. In this case, you need to:

1. Create a new node with the new data to be added.
2. Check to see if the list is empty. a. If it is, set the new node as the sole item in the list
3. Otherwise: a. Check that currentNode.next is not null. b. If it is, set currentNode = currentNode.next and keep checking. c. Otherwise, set currentNode.next to be the new node.

The while loop (described in steps 3a and 3b) demonstrates a technique called traversing or walking the list. A Node variable (in this case, currentNode) is used to check each link in the list, using the .next references to visit each link. Traversing is a common technique used in many linked list operations and algorithms, and you'll see more of that later in this unit.

Graphically, this is what a list traversal to add data to the tail looks like:

3. Add Data in the Middle of a List

Of course, you can add data at any point in a linked list. You just need to know where in the list to put the new node. This is normally done when trying to keep a list of items in a specific order.

You can assume you want to insert your data before another piece of data. Here's what that code might look like:

public void addBefore(T data, T compare) {
  Node newNode = new Node(data);

  // Is the list empty?
  if (this.head == null){
    this.head = newNode;
    return;
  }

  // Is the head what you want to follow our new node?
  if (this.head.data == compare){
    newNode.next = this.head;
    this.head = newNode;
    return;
  }

  // Find the node you want to follow the new node
  // This uses a trailing reference traversal
  Node compareNode = this.head;
  Node trailingNode = null;

  while (compareNode != null 
      && compareNode.data != compare) {
    trailingNode = compareNode;
    compareNode = compareNode.next;
  }

    // You are either at the end of the list, or 
    // you found the compare data
    // In either case, you can insert newNode 
    // between trailingNode and compareNode
    trailingNode.next = newNode;
    newNode.next = compareNode;

}

As with the .addTail() method, you first check if the list is empty before doing any work. However, you can also check if the head contains the data for which you are searching. If so, then you can add the new node to the head of the list.

Otherwise, you have to search for the data in the list using a traversal technique called a trailing reference. With the trailing reference technique, you have to use Node variables to walk the list. The compareNode variable refers to the node you want to check for the data to compare. The trailingNode variable refers to the previous node in the list. Graphically, this looks like this:

Using a trailing reference provides you references to two adjacent Node objects. You can then insert your new node between them. Once the while loop is done, compareNode is either pointing to the node you want to follow your new data or has walked off the end of the list and is null. In either case, you can insert newNode between them by making trailingNode.next point to newNode, and newNode.nextpoint tocompareNode.

Of course, you can also add data after another node in the list -- that is left as part of a lab.

Remove Data from a Linked List

As with adding data, you can remove data from a list in three ways:

1. Remove data from the head of the list.
2. Remove data from the tail of the list.
3. Remove data from the middle of the list.

You can take a look at all three techniques.

1. Remove the Head of a List

Removing the head of the list, like adding a new head, is quick. Conceptually, after checking for an empty list, you assign head to be head.next. This removes the first node from the list. If you wish, you can save the data in that node first, perhaps to be used as a return value as seen in the code below:

public T removeHead() {
  // Is the list empty?
  if (this.head == null)
    return null;

  // Save the head to return its data
  Node returnNode = this.head;

  // Make the head the next item in the list
  this.head = this.head.next;

  // Return the saved head
  return (T) returnNode.data;
}

2. Remove the Tail of a List

Removing data from the tail of the list requires that you not only find the tail but also the node just before the tail. The trailing reference technique can be used here as it was earlier, as it will allow you to find both references. All you need to do is make sure there are at least two items in the list to make use of the technique:

public T removeTail() {
  // Is the list empty?
  if (this.head == null)	
    return null;

  // Is there only one item in the list?
  if (this.head.next == null) {
    // You just need to return it
    Node returnNode = this.head;
    this.head = null;
    return (T) returnNode.data;
  }

  // Otherwise, you walk the list with two nodes
  Node returnNode = this.head;
  Node trailingNode = returnNode;

  // As long as you're not at the end
  while (returnNode.next != null) {
    // Make sure trailing node follows one link back
    trailingNode = returnNode;
    returnNode = returnNode.next;
  }

  // You set trailing node as the new end of the list.
  trailingNode.next = null;
  return (T) returnNode.data;
}

3. Remove Data from the Middle of a List

Removing data from the middle of a linked list uses the same trailing reference technique as you've seen before. If the data to be removed is found in the list, you can set the .next reference of the previous node to the .next reference of the node being deleted. If you don't find the data to remove, then you do nothing:

public void remove(T data) {
  // Is the list empty?
  if (this.head == null)
    return;

  Node removeNode = this.head;
  Node trailingNode = removeNode;

  // As long as you haven't:
  // - Reached the end of the list, and
  // - Found the data item
  // Keep walking the list
  while (removeNode != null && removeNode.data != data) {
    trailingNode = removeNode;
    removeNode = removeNode.next;
  }

  // If remove_node is null, then you didn't find anything
  if (removeNode != null)
    // Are you removing the head?
    if (removeNode == trailingNode)
      this.head = this.head.next;
    else
      // Excise this node from the list
      trailingNode.next = removeNode.next;
}

This method doesn't return anything, because you passed the data contained in the removed node as a parameter.

Search for data in a Linked List

Finding a piece of data in a linked list requires you to traverse the list and inspect each item, looking for the data you want to find. Conceptually, this is like flipping through the pages of a book from start to finish:

public boolean find(T data) {
  // Set the current node to the head of the list
  Node currentNode = this.head;

  // As long as you haven't:
  // - Reached the end of the list, and
  // - Found the data item
  // Keep walking the list
  while (currentNode != null 
      && currentNode.data != data)
    currentNode = currentNode.next;

  // If currentNode is null, then you never found it
  return currentNode != null;
}

You can also traverse a list to output the items in a list, which is left as a lab exercise.

If you'd like to continue learning about Linked Lists, check out the following resources in the Java 301 course:

• Introduction to Linked Lists
• Using Java's built-in LinkedList class
• Video: Using Java's built-in LinkedList

Summary: Linked Lists in Java

Implementing a linked list in Java requires two classes -- one for the node in which data is stored and another for the list structure itself. Adding, removing, and finding data in the list is possible using a technique called traversing the list.

In general, you do not need to implement your own Linked List, but understanding its structure and how it operates will give you insight into how the linked lists work, and how you can use them when necessary.