Linked List Implementation in Java

You are most likely familiar with arrays. They have great access times- essentially instantaneous. The caveat is their inflexibility: they cannot grow or shrink in size, and to store a dynamic amount of objects, one must create a new array each time.

Let's say you wanted to store a list of guests currently staying at the hotel. You could use an array, but it would be rather difficult to shrink or expand the number of guests. This is where linked lists come in!

Linked lists are stored as a list of nodes, starting at a head and pointing to the next node in the list. This is an incredibly simple example, so hopefully it is easy to digest!

Nodes

In Java, the nodes for this example look a little something like this:

public class HotelNode {

    String guestName;
    HotelNode next;
    
    public HotelNode() {
        guestName = null; 
        next = null;
    } // HotelNode
    
    public HotelNode(String guestName) {
        this.guestName = guestName;
        next = null;
    } // HotelNode
    
    public HotelNode(String guestName, HotelNode next) {
        this.guestName = guestName;
        this.next = next;
    } // HotelNode
    
    public HotelNode getNext() {
        return next;
    } // getNext
    
    public String getGuestName() {
        return guestName;
    } // getGuestName
    
    public void setNext(HotelNode next) {
        this.next = next;
    } // setNext
    
    public void setGuestName(String guestName) {
        this.guestName = guestName;
    } // setGuestName
} // class

Each node has both a value (in this case a guest name), and a pointer to the next node. There are three constructors- a default, one with a name value supplied, and one with both a name value and a next HotelNode. Then, there are getters and setters for both the value and the next reference.

Feel free to add other instance variables to your node class; in this example I could have included the age of a guest or the room number they stayed in. Don't feel limited to just having a single value and a next reference!

Code for a Linked List Class

Here is a simple linked list. Note that there is only one variable pointer to the head. Also note that the last node has a null value for its next pointer; this signifies the end of the list.

The skeleton of the class is as follows:

// Class to store HotelGuest Names, implements several other interfaces 
// but the most important once is List
public class HotelGuestList implements List { 

    private HotelNode head;
    
    // other methods to be implemented 
    
} // HotelGuestList

Traversing the Linked List

In order to traverse the linked list, you must follow the pointers to the next node, which is slower than an array's access.

// n must be less than size() and nonnegative
// returns the node at position n in the list
public HotelNode nodeAt(int n) {
    HotelNode searcher = head;
    for (int i = 0; i < n; i++) {
        searcher = searcher.getNext()
    } // for
    return searcher;
} // nodeAt

Adding and deleting

Adding and deleting elements is considerably easier than in an array. Simply move the pointers accordingly. For instance, let's say that I wanted to add John in between Sally and Tim in the above example.

First, I would make a new node with John as the guest name and the next value pointing at Tim.

Then, I would set Sally's pointer to John's node. Voila! Easy as that. Think about how hard that would be with an array- you'd have to shift all of the indexes to the right or even make a new array altogether and copy all of the values.

This is the implementation:

 
// adds a new node at a specified index
public boolean add(int index, String name) {
    if (name == null || index > size || index < 0) {
        return false;
    } // if
    if (index == 0) {
        head = new HotelNode(name, head);
    } else {
        HotelNode newNode = new HotelNode(s, nodeAt(index));
        nodeAt(index - 1).setNext(newNode);
    } // else
    return true;

Deleting is even simpler. To delete, simply set the previous element another element ahead so that it skips the deleted node. For instance, if I wanted to delete the node at position 5, I would just set the next value of the element at 4 to the element at 6. 5 is lost, and there is no pointer to it. Easy peasy!

 
// removes node at index and returns content of removed node
// index must be between 0 and size() - 1, inclusive
public String remove(int index) {
    String removed = nodeAt(index).getGuestName();
    if (index == 0) {
        head = head.getNext();
    } else {
        nodeAt(index - 1).setNext(nodeAt(index + 1));
    } // else
    return removed;
} // remove

Summary

To recap: linked lists are good for adding and deleting elements, which is advantageous for activities such as dynamic storage of changing elements (i.e. guests checking in and out of a hotel). However, they are not as good at retrieval and traversing the items as arrays are. For a linked list, retrieval is O(n) compared to random access in an array.

Hopefully this was an easy way for you to become briefly acquainted with the idea of a linked list in Java! For more reading, go to this OpenGenus article: Java Collections: Linked List

Questions for further consideration:

1. Consider if each node pointed to two other nodes. How would this improve search time? Storage?
2. Is there a way we can combine arrays and linked lists to further improve search, retrieval, and storage? See hash maps for further reading.
3. Java's implementation of a linked list is doubly linked, so that each element has a pointer to the nodes both before and after it. How does this affect traversal speed?

Thank you for reading!