Linked Lists

September 06, 2019 5 minutes

A LinkedList is a linear data structure comprised of a sequence of nodes where each node is made up of two components:

  1. Value: the actual value that the node holds.
  2. Next: a reference to the next node in the sequence.

Below is an illustration of the Node structure and their arrangement to form a LinkedList:

LinkedList

The first node is also known as the head or root node. Similarly, the last node is known as tail node.

Types of LinkedList

The nodes of a linked list can be arranged (and structured) in various forms to build different kinds of LinkedList suitable for various purposes.

For Example:

  1. Doubly LinkedList: a list having two (instead of one) reference components. One of the references is assigned to the next node (as in the case of singly LinkedList) and the other is assigned to the previous node. This helps in iterating the list in both the directions as compared to just one-way iteration in singly linked lists.

  2. Circular LinkedList: is another arrangement of list node, in which the next reference of the tail node points back to the head node instead of a being a null or unassigned reference. This helps in forming a ring like data-structure and is used in various scenarios like scheduling tasks in a round-robin fashion.

Note: The head and tail references does not holds any significance for circular lists. Any node can be considered as a head or tail.

LinkedList

Structure

The Node class holding data of type T can be represented as follows:

//a class representing the Node of a singly linkedList. 
public class ListNode<T> {
    //actual value held by this node
    private T value;
    // a refence to the next node. Null if there is none
    private ListNode<T> next;
}

As clear from the above mentioned code, the reference $next$ is actually of type ListNode itself. In other words, we can say it will refer to intances of its own type.

Common Methods

Some of the common methods available in the LinkedList data structure are:

  1. addFirst: Create a new Node and insert it as the first node of the list.
  2. addLast: Create a new Node and append it to the end of the list.
  3. contains: Check if a Value is present in the LinkedList or not?
  4. delete: Delete a node (if present)
  5. get: Get the value at ith index.
  6. addAtIndex: Add the given value at a specific index.

addFirst

The method is responsible for creating a new node and adding it to the head of the linked list. While creating a new node as the first node, we need to see if the list is already initialized or not:

  1. If the list is already initialized, the next reference of the newly created node will point to the existing head. Once set, the head reference will be re-set to point to this newly created node.
  2. If not, we simply assign the newly created node to the head reference.

    public void addFirst(T value) {
    //create new node
    ListNode<T> newNode = new ListNode<>();
    newNode.setValue(value); 
    size++; //increment the size
    //if list already initialized, set the next of new node to existing root
    if (null != root) {
     newNode.setNext(root);
    }
      
    //update the root reference to point to newly created node
    root = newNode;
    }
    

addLast

Another common use-case is to create a new node and append it to the end of the list. Now there can be multiple ways to do this. For example, we can keep a reference to the last node of the list and every time we need to append a new node, we can use the same to update the entries at the rear end.

The same operation can also be done by simply iterating to the end of the list and creating a new node there (as mentioned below):

    // the method is used to insert a new node at the end of the list
    public LinkedList<T> insertAtLast(T value) {
        //if first node
        if (null == root) {
            insertAsFirstNode(value);
        } else {
            //iterate to last node
            ListNode<T> lastNode = iterateToIndex(size - 1);
            lastNode.setNext(new ListNode<>(value));
            size++;
        }
        return this;
    }

    // a utility method to return the node at @param:index position
    private ListNode<T> iterateToIndex(int index) {
        ListNode<T> iterator = root;
        int count = 0;
        while (count < index) {
            iterator = iterator.getNext();
            count++;
        }
        return iterator;
    }

contains

The method serves the functionality to perform look-up operations on the individual nodes for the existence of some value passed as input. It simply returns a boolean true, if the value is present and false otherwise.

Note: With a few changes to the code, the method can be updated to return the index in case the values is present in the list.

//iterate over the list nodes and check if the @param:value
//is present in the list or not
public boolean contains(T value) {
     ListNode<T> iterator = root;
     while (null != iterator) {
        if (value.equals(iterator.getValue())) {
            return true;
        }
        iterator = iterator.getNext();
     }
     return false;
}

get

The get method is used to get the value present at the $i^{th}$ index location. We will need to handle the edge cases like: 1. Empty List 2. Negative Index or Index more than size of the list.

Once the validation is complete, we can simply iterate to the node(if present) and can return the value held.

    public Optional<T> get(int index) throws IllegalArgumentException {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("invalid index");
        }
        ListNode<T> node = iterateToIndex(index);
        return Optional.ofNullable(node.getValue());
    }

For a detailed implementation, please checkout the code at this git repository.

comments powered by Disqus