Linked List Data Structure

In this article, we are going to understand what is a linked list and its variations. We will also see insertions, deletions, and search in a linked list. We will also see a linked list implementation in Java.

Linked List

Linked List is one of most used and common data structures made of a sequence of nods. Each node contains a value and a pointer to the next node in the sequence. The “head” node points to the first node of the sequence and the last node of the sequence point to NULL (for singly-linked list). Linked Lists are dynamic and, since adding any new node or deleting a node is about changing the pointers, the linked list becomes very easy to operate on.

1. Benefits and Usage of Linked List

With the dynamic nature of Linked list, the Linked List Data structure provides a lot of benefits. Let’s look at some major benefits and usage of linked list data structure.

1. Unlike arrays, the nodes (links) of a Linked List don’t need to continuously present in the memory. They are placed randomly and will be connected using the next.
2. This model is more memory-optimized.
3. Linked List doesn’t allow an “empty” node.
4. The size of a linked list doesn’t to be declared in advance and it can as big as the memory permits.
5. Linked List maintains the insertion order.
6. We can use linked List for implementing Stacks and Queues.
7. Linked List can used to implementing Graphs using adjacency lists.

2. Limitations

Before using the linked list data structure, we should also keep in mind the following limitation of the data structure.

1. Linked List requires more memory than Arrays because each node contains a pointer and that requires extra memory.
2. Unlike arrays, we can’t randomly access any element. It is sequential starting from the head, and it requires more access time.
3. In Singly Linked List, we can’t traverse backward.

3. Linked List Vs Array

1. Linked List allows dynamic size (at runtime) as data can exist randomly in memory, unlike arrays where data has to be in contiguous blocks on memory.
2. Array’s memory allocation happens at compile time, whereas for Linked List it is at runtime.
3. Linked List takes more memory than Arrays because it stores the pointer to the next element.
4. Array elements can be picked randomly with index, for Linked List we must traverse from head to that element so it takes more time.

4. Linked List Types

There are three major types of Linked List supported in the data structure:

• Singly Linked List – In a singly list, nodes traversal and navigation can happen only in one forward direction.
• Doubly Linked List – In a doubly list, node traversal and navigation can happen both in the backward and the forward directions. We can navigate items forward and backward.
• Circular Linked List – In a circular list, the last node contains the link of the first node as “next” and the first node contains the link of the last node as “previous”.

In this article, we will focus only on the singly linked list.

5. Singly Linked List Representation

A linked list is made of a sequence of nods. Each node contains a value and a pointer to the next node in the sequence.

As per the above illustration, the following are the important points to be considered.

1. Head node points to the first node of the list.
2. Each node has a data field (s) and a pointer to the next node.
3. The last node points to NULL.

6. Basic Operations on Linked List Data Structure

We will go through the major operations of a linked list and they are insertion, deletion, display, search, and size.

6.1. Insertion

In a linked list, we can insert a node in three different ways. Here are the three options to insert an element in to a list.

1. Inserting the new node as the first node.
2. Inserting node after a node.
3. At the end of the list.

In the first case, we will add the new node before the first node of the linked list and its next would point previous first node. The head will now point to the newly added node. As you can see below, we had a linked list 1->2->3 with the head pointing to 1 and we added a new node 0 and the linked list becomes 0->1->2->3 with the head pointing to node 0 now.

Here is the code of inserting the node as the first node in the list

public static void  insert(MySinglyLinkedList list, int data)
{
    Node node = new Node(data);
    node.next = null;

    // If the LinkedList is empty, then make the new node as head.
    if (list.head == null) {
        list.head = node;
    }
    else {// else traverse the list till the last node and insert at the last.
        Node last = list.head;
        while (last.next != null) {
            last = last.next;
        }
        // Insert the new node at last node
        last.next = node;
    }
}

In case , we wish to insert a node after any node, we will first traverse until given node. Next, we will do two things:

1. The new node’s next will point to the node’s next.
2. The node’s next will point to the new node

As you can see below, we had a linked list 1->3->4 and we want to insert node 2 after node 1, so we will change the pointers as per the above steps and the linked list will become 1->2->3->4.

public void insertAfter(Node previousNode, int dataToBeInserted)
{
    if (previousNode == null)
    {
        System.out.println("The given previous node cannot be null");
        return;
    }
    Node newNode = new Node(dataToBeInserted);
    newNode.next = previousNode.next;
    previousNode.next = newNode;
}

In case we want to insert a node at the last of a linked list, we will traverse the linked list until the next points to NULL. At this stage we will do the following 2 things:

1. The current last node’s next will point to the new node.
2. The new node’s next will point to NULL now

As you can see below, we had a linked list 1->2->3->NULL and we want to insert node 4 at last, so we will change the pointers as per the above steps and the linked list will become 1->2->3->4->NULL.

7. Deleting Nodes from Linked List

Like insertion, we can delete a node from a linked list in 3 ways:

To delete a node from the linked list, we need to do the following steps. 

1. Deleting the first node.
2. Delete any middle element.
3. Deleting last element.

To delete the first node from the linked list, point the head to the current first node’s next. You can see the illustration in the following diagram.

Here is the code snippet showing the delete operation in the list.

public void deleteAtPosition(MySinglyLinkedList list, int pos) {
    System.out.println("trying to delete node at position:" + pos);

    Node currentNode = list.head;
    Node prev = null;
    int counter = 0;

    if (currentNode != null) {
        if (pos == 0) {
            list.head = currentNode.next;
            System.out.println("element at position" + pos + " has been deleted");
        } else {
            // Count for the pos to be deleted, keep track of the previous node as it is needed to change currentNode.next
            while (currentNode != null) {
                if (counter == pos) {
                    prev.next = currentNode.next;
                    System.out.println("element at " + pos + " has been deleted");
                    break;
                } else {
                    prev = currentNode;
                    currentNode = currentNode.next;
                    counter++;
                }
            }
        }
    }
    if (pos > counter) {
        System.out.println("no node found at position:" + pos + " ,as it greater than the size of the list");
    }
}

To delete any middle element from the linked list, traverse till the second last element (using next!=null and keeping track of current and previous node) and change the previous node’s next to the current node’s next.You can see the illustration in the following diagram.

For deleting the last element from the linked list, traverse until the second last element (using next!=null and keeping track of the previous node) and change the previous node’s next to NULL. You can see the illustration in the following diagram.

8. Linked List Searching

To search a node of the linked list, we will need to start from the head and check if the current node’s data is equal to the data, or else we will move to the next node in the list. We will continue to go to the next node until the current node’s next is not equal to NULL and in that case, the data is not present in our linked list or better, we don’t have a node that has the data. You can see the code for this below.

public boolean search(Node head, int data)
{
    if (head == null)
        return false;
    if (head.data == data)
        return true;
    return search(head.next, data);
}

9. Size

To calculate the size of a linked list, we will set a counter at 0 and keep incrementing by 1 once we visit a node. We will start with the head and continue to go to the next node until the current node’s next is not equal to NULL. As said, we will increment the counter for each node we traverse. At the end, we will have the size of the list in the counter variable. You can see the code for this below.

public int size(MySinglyLinkedList list){
    int count=0;
    Node currNode = list.head;
    while (currNode != null) {
        count++;
        currNode = currNode.next;
    }
    return count;
}

10. Linked list Time and Space Complexity

Linked list is a good option to insert and delete as it provides a constant time (O(1)) for these operations.

11. Linked List Implementation in Java

Now we have a fundamental understanding of the linked list data structure. Let’s see a linked list implementation in Java. This example shows the Java implementations of the linked list.

Java provides a build in data structure for Linked List, in case you are looking for using the linked list, please use the JDK linked list or other similar implementation for the List interface.

package linkedlist.singly;

public class MySinglyLinkedList {

    /**
     * Head of the LinkedList
     */
    public Node head;

    /**
     *  This is a method static class defining a LinkedList Node.
     *  since it is static, main() method  can access it
     */
    public static class Node {
        public int data;
        public Node next;
        Node(int data) {
            this.data = data;
            next = null;
        }
    }

    /**
     * Insert a node to the given LinkedList
     * This method will insert at head if the list is empty
     * Or else, it will inset at last
     * @param list - LinkedList
     * @param data - node data
     */
    public static void insert(MySinglyLinkedList list, int data) {
        Node node = new Node(data);
        node.next = null;

        // If the LinkedList is empty, then make the new node as head.
        if (list.head == null) {
            list.head = node;
        } else { // else traverse the list till the last node and insert at the last.
            Node last = list.head;
            while (last.next != null) {
                last = last.next;
            }
            // Insert the new node at last node
            last.next = node;
        }
    }

    /**
     * This method will insert the new node after any given node.
     * @param previousNode
     * @param dataToBeInserted
     */
    public void insertAfter(Node previousNode, int dataToBeInserted) {
        if (previousNode == null) {
            System.out.println("The given previous node cannot be null");
            return;
        }
        Node newNode = new Node(dataToBeInserted);
        newNode.next = previousNode.next;
        previousNode.next = newNode;
    }


    /**
     * Delete a node by given data at the node.
     * @param list - LinkedList
     * @param data - node data
     */
    public void deleteByKey(MySinglyLinkedList list, int data) {
        System.out.println("trying to delete node with data:" + data);
        // Store head node
        Node currentNode = list.head;
        Node prev = null;

        if (currentNode != null) {
            if (currentNode.data == data) {
                list.head = currentNode.next; // Changed head
                System.out.println("element " + data + " has been deleted");
            } else {
                while (currentNode != null && currentNode.data != data) {
                    prev = currentNode;
                    currentNode = currentNode.next;
                }
                if (currentNode != null) {
                    prev.next = currentNode.next;
                    System.out.println("element " + data + " has been deleted");
                } else {
                    System.out.println("no node found with data:" + data);
                }
            }
        }
    }

    /**
     * Delete a node by given position.
     * @param list - LinkedList
     * @param pos - position of the node
     */
    public void deleteAtPosition(MySinglyLinkedList list, int pos) {
        System.out.println("trying to delete node at position:" + pos);

        Node currentNode = list.head;
        Node prev = null;
        int counter = 0;

        if (currentNode != null) {
            if (pos == 0) {
                list.head = currentNode.next;
                System.out.println("element at position" + pos + " has been deleted");
            } else {
                // Count for the pos to be deleted, keep track of the previous node as it is needed to change currentNode.next
                while (currentNode != null) {
                    if (counter == pos) {
                        prev.next = currentNode.next;
                        System.out.println("element at " + pos + " has been deleted");
                        break;
                    } else {
                        prev = currentNode;
                        currentNode = currentNode.next;
                        counter++;
                    }
                }
            }
        }
        if (pos > counter) {
            System.out.println("no node found at position:" + pos + " ,as it greater than the size of the list");
        }

    }

    /**
     * Recursive Searching
     * find a node with given data in the LinkedList
     * @param head - head node
     * @param data - node data
     * @return - boolean value (true/false)
     */
    public boolean search(Node head, int data) {
        if (head == null)
            return false;
        if (head.data == data)
            return true;
        return search(head.next, data);
    }


    /**
     * Traverse and print the list
     * @param list
     */
    public void traverseAndPrintList(MySinglyLinkedList list) {
        Node currNode = list.head;
        System.out.print("LinkedList: ");
        while (currNode != null) {
            System.out.print(currNode.data + " ");
            currNode = currNode.next;
        }
        System.out.println();
    }

    /**
     *
     * @param list
     * @return the size of the list
     */
    public int size(MySinglyLinkedList list) {
        int count = 0;
        Node currNode = list.head;
        while (currNode != null) {
            count++;
            currNode = currNode.next;
        }
        return count;
    }
}

Testing Class

package linkedlist.singly.test;

import linkedlist.singly.MySinglyLinkedList;
import org.junit.Test;

public class MySinglyLinkedListTest {
    @Test
    public void testLinkedList() {
        MySinglyLinkedList list = new MySinglyLinkedList();
        //insertion
        MySinglyLinkedList.insert(list, 1);
        MySinglyLinkedList.insert(list, 2);
        MySinglyLinkedList.insert(list, 3);
        MySinglyLinkedList.insert(list, 4);
        MySinglyLinkedList.insert(list, 5);
        MySinglyLinkedList.insert(list, 6);
        MySinglyLinkedList.insert(list, 7);
        MySinglyLinkedList.insert(list, 8);
        MySinglyLinkedList.insert(list, 9);
        MySinglyLinkedList.insert(list, 10);
        MySinglyLinkedList.insert(list, 11);
        MySinglyLinkedList.insert(list, 12);
        MySinglyLinkedList.insert(list, 13);
        MySinglyLinkedList.insert(list, 14);
        MySinglyLinkedList.insert(list, 15);
        MySinglyLinkedList.insert(list, 16);

        //size of the list
        System.out.println("size of the list at the beginning: " + list.size(list));

        //delete by key
        list.traverseAndPrintList(list);
        list.deleteByKey(list, 1);

        list.traverseAndPrintList(list);
        list.deleteByKey(list, 4);

        list.traverseAndPrintList(list);
        list.deleteByKey(list, 10);

        list.traverseAndPrintList(list);
        list.deleteByKey(list, 17);

        list.traverseAndPrintList(list);

        //delete by position
        list.deleteAtPosition(list, 0);
        list.traverseAndPrintList(list);

        list.deleteAtPosition(list, 2);
        list.traverseAndPrintList(list);

        list.deleteAtPosition(list, 10);
        list.traverseAndPrintList(list);

        list.deleteAtPosition(list, 18);
        list.traverseAndPrintList(list);

        //search
        System.out.println("searching for element with data 13");
        if (list.search(list.head, 13))
            System.out.println("Yes, given data is present in the list");
        else
            System.out.println("No, given data is not present in the list");
        list.traverseAndPrintList(list);

        //size of the list
        System.out.println("size of the list at the end: " + list.size(list));

        System.out.println("Add element 99 at 3rd position");
        list.insertAfter(list.head.next, 99);
        list.traverseAndPrintList(list);
    }
}

Output:

Summary

In this article, we have learned:

1. The basics of Linked List.
2. The usage of a Linked List.
3. The benefits of a Linked List.
4. The limitations of a Linked List.
5. Array vs Linked List comparison.
6. The variations of Linked List.
7. The insertion in a Singly List
8. The deletion in a Singly Linked List
9. The search on a Singly List
10. The size of a Singly Linked List
11. The Java program to create a Singly-Linked List and perform all the operations.
12. The test class and program output.

The source code for this article is available on our GitHub Repository.