HelloKoding

Practical coding guides

Linked List Data Structure

In this article, you will learn about singly and doubly Linked List data structures and theirs implementations

Linked List is a linear data structure consisting of a collection of elements (nodes) which are stored in separated physical memory locations and linked to each other via pointer reference. Typically, there are two type of linked list: singly and doubly

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

A singly linked list

Operations and Time complexity

  • Traversal O(N)
  • Add First O(1), Add Last O(N)
  • Remove First O(1), Remove Last O(N)

MyLinkedList.java

package com.hellokoding.datastructure;

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);
        myLinkedList.traversal();

        myLinkedList.removeFirst();
        myLinkedList.traversal();

        myLinkedList.removeLast();
        myLinkedList.traversal();
    }

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

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

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

A doubly linked list

Operations and Time complexity

  • Traversal O(N)
  • Add First O(1), Add Last O(1)
  • Remove First O(1), Remove Last O(1)

MyDoublyLinkedList.java

package com.hellokoding.datastructure;

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);
        myLinkedList.traversal();

        myLinkedList.removeFirst();
        myLinkedList.traversal();

        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;
        }
    }
}
Follow HelloKoding