Linked List is a linear data structure consisting of a collection of nodes which are stored in separated physical memory locations

There are multiple types of Linked List. In this article, we will learn about the singly and doubly linked list. We will also implement some Linked List common operations including

  • Traversal: traverse all elements in a Linked List

  • Add First and Add Last: add a new element into the head and the tail of a Linked List

  • Remove First and Remove Last: remove the first and last element of a Linked List

We can manage a Linked List by using only the head node or using both head and tail nodes to reduce the time complexity of Add Last and Remove Last operations

Singly Linked List

Each node in a singly linked list comprises two parts, the data and the pointer which is linked to the next node. The next pointer of the tail node is linked to null

In Java, the node object of a singly linked list can be represented as below

class Node {  
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
    }
}

The type of data variable can be any. The type of next variable has to be the class itself

The following example is a singly linked list implementation in Java. The linked list is managed via a head node

public class MyLinkedList {  
    Node head;

    public void addFirst(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }

        Node newNode = new Node(data);
        newNode.next = this.head;

        this.head = newNode;
    }

    public void addLast(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }

        Node currentNode = this.head;
        while (currentNode.next != null) {
            currentNode = currentNode.next;
        }

        currentNode.next = new Node(data);
    }

    public void removeFirst() {
        if (this.head == null) return;

        this.head = this.head.next;
    }

    public void removeLast() {
        if (this.head == null) return;

        if (this.head.next == null) {
            this.head = null;
            return;
        }

        Node currentNode = this.head;
        while (currentNode.next.next != null) {
            currentNode = currentNode.next;
        }

        currentNode.next = null;
    }

    public void traversal() {
        Node currentNode = this.head;
        while (currentNode != null) {
            System.out.printf("%d ", currentNode.data);
            currentNode = currentNode.next;
        }

        System.out.println();
    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(2);
        myLinkedList.addLast(6);
        myLinkedList.addFirst(9);

        System.out.println("Traverse all elements");
        myLinkedList.traversal();

        System.out.println("Remove the first node");
        myLinkedList.removeFirst();
        myLinkedList.traversal();

        System.out.println("Remove the last node");
        myLinkedList.removeLast();
        myLinkedList.traversal();
    }

    static class Node {
        public int data;
        public Node next;

        public Node(int data) {
            this.data = data;
        }
    }
}

Output

Traverse all elements  
9 2 6  
Remove the first node  
2 6  
Remove the last node  
2

Time complexity

Operation        Time complexity  
--------------------------------
Traversal        O(n)  
Add first        O(1)  
Add last         O(n)  
Remove first     O(1)  
Remove last      O(n)

Doubly Linked List

Each node in a doubly linked list comprises three parts, the data and two pointers in which one is linked to previous node and the other is linked to next node. The previous pointer of the head node is linked to null while the next pointer of the tail node is linked to null

In Java, the node object of a doubly linked list can be represented as below

static class Node {  
    public int data;
    public Node previous;
    public Node next;

    public Node(Node previous, int data, Node next) {
        this.previous = previous;
        if (previous != null) previous.next = this;

        this.data = data;

        this.next = next;
        if (next != null) next.previous = this;
    }
}

The type of data variable can be any. The type of previous and next variable has to be the class itself

The following example is a doubly linked list implementation in Java. The linked list is managed via both head and tail nodes to reduce the time complexity of Add and Remove Last operations

public class MyDoublyLinkedList {  
    Node head;
    Node tail;

    public void addFirst(int data) {
        Node newNode = new Node(null, data, this.head);
        this.head = newNode;
        if(this.tail == null) this.tail = this.head;
    }

    public void addLast(int data) {
        Node newNode = new Node(this.tail, data, null);
        this.tail = newNode;
        if(this.head == null) this.head = this.tail;
    }

    public void removeFirst() {
        if (this.head == null) return;

        this.head = this.head.next;
        if (this.head == null) this.tail = null;
        this.head.previous = null;
    }

    public void removeLast() {
        if (this.head == null) return;

        if (this.head.next == null) {
            this.head = null;
            this.tail = null;
            return;
        }

        Node beforeTail = this.tail.previous;
        beforeTail.next = null;
        this.tail = beforeTail;
    }

    public void traversal() {
        Node currentNode = this.head;
        while (currentNode != null) {
            System.out.printf("%d ", currentNode.data);
            currentNode = currentNode.next;
        }

        System.out.println();
    }

    public static void main(String[] args) {
        MyDoublyLinkedList myLinkedList = new MyDoublyLinkedList();
        myLinkedList.addLast(2);
        myLinkedList.addLast(6);
        myLinkedList.addFirst(9);

        System.out.println("Traverse all elements");
        myLinkedList.traversal();

        System.out.println("Remove the first node");
        myLinkedList.removeFirst();
        myLinkedList.traversal();

        System.out.println("Remove the last node");
        myLinkedList.removeLast();
        myLinkedList.traversal();
    }

    static class Node {
        public int data;
        public Node previous;
        public Node next;

        public Node(Node previous, int data, Node next) {
            this.previous = previous;
            if (previous != null) previous.next = this;

            this.data = data;

            this.next = next;
            if (next != null) next.previous = this;
        }
    }
}

Output

Traverse all elements  
9 2 6  
Remove the first node  
2 6  
Remove the last node  
2

Time complexity

Operation        Time complexity  
--------------------------------
Traversal        O(n)  
Add first        O(1)  
Add last         O(1)  
Remove first     O(1)  
Remove last      O(1)