Linked List

A linked list is a sequence of data structures, which are connected together via links.

Linked List is a sequence of links which contains items. Each link contains a connection to another link.

Linked list is used where frequent data modification, insertion and deletion is required

Linked lists can continue to expand as long as there is space on the machine

---

Following are the various types of linked list.

Simple Linked List − Item navigation is forward only.

Doubly Linked List − Items can be navigated forward and backward.

Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.

---

Java Program to insert into a linked list:

package com.mk.ds.linkedlist;

class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
        next = null;
    }
}
public class LinkedList {
    private Node head;

    public void addFromStart(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }
    public void addLast(int data) {
        if (head == null)
            head = new Node(data);
        else {
            Node tmp = head;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next =  new Node(data);
        }
    }
    public void print() {
        Node node = head;
        while (node != null) {
            System.out.print(node.data + "->");
            node = node.next;
        }
    }
    public void clear() {
        head = null;
    }
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        for (int i = 0; i < 10; i++) {
            linkedList.addFromStart(i);
        }
        linkedList.print(); //9->8->7->6->5->4->3->2->1->0->
        linkedList.clear();
        System.out.println();
        for (int i = 0; i < 10; i++) {
            linkedList.addLast(i);
        }
        linkedList.print(); //0->1->2->3->4->5->6->7->8->9->
    }
}

---

Java Program to reverse a linked list:

package com.mk.ds.linkedlist;

public class LinkedList<T> {
    private Node<T> head;

    private static class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    public void addFirst(T item) {
        head = new Node<T>(item, head);
    }

    public void addLast(T data) {
        if (head == null) {
            addFirst(data);
        } else {
            Node<T> tmp = head;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = new Node<T>(data, null);
        }
    }

    public void print(Node node) {
        while (node != null) {
            System.out.print(node.data + "->");
            node = node.next;
        }
        System.out.print("NULL");
        System.out.println();
    }

    public Node reverse(Node currentNode) {
        Node reverseNode = null;
        Node nextNode = null;
        while(currentNode != null) {
            nextNode = currentNode.next;
            currentNode.next = reverseNode;
            reverseNode = currentNode;
            currentNode = nextNode;
        }
        return reverseNode;
    }

    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList();
        for (int i = 1; i <= 5; i++) {
            linkedList.addLast(i);
        }

        linkedList.print(linkedList.head);
        Node reverseNode = linkedList.reverse(linkedList.head);
        linkedList.print(reverseNode);
    }
}

---

Java Program to reverse a linked list(Recursively)

public Node reverse(Node currentNode) {

    if(currentNode == null) {
        return currentNode;
    }

    if(currentNode.next == null) {
        return currentNode;
    }

    Node reverseNode = reverse(currentNode.next);
    currentNode.next.next = currentNode;
    currentNode.next = null;
    return reverseNode;
}

---

Java Program to find middle element of linked list-

To find middle element we maintain 2 pointer to iterate the linked list no pointer will move one node in sequence while other pointer which is fast pointer will move 2 node at a time, so when fast pointer will reach the end of the linked list slow pointer will be at the middle position at that time.

Refer below code snippet.

public void printMiddle(Node currentNode) {

    Node slowPtr = currentNode;
    Node fastPtr = currentNode;

    if (null != currentNode) {
        while (null != fastPtr && null != fastPtr.next) {
            fastPtr = fastPtr.next.next;
            slowPtr = slowPtr.next;
        }
        System.out.println("Middle element is ::" + slowPtr.data);
    }
}

---

Reverse a linked list in given size.

Reverse a linked of given size n, suppose length of linked list is m, m> n than reverse the chunk of n element in linked list.

Like- if M = 10 and n -2

Linked list - 1->2->3->4->5->6->7->8->9->10->NULL

Reversed linked list in size of 2 = 2->1->4->3->6->5->8->7->10->9->NULL

Refer below code snippet –

package com.mk.ds.linkedlist;

public class LinkedList<T> {

    private Node<T> head;
    private static class Node<T> {
        private T data;
        private Node<T> next;
        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }
    public void addLast(T data) {
        if (head == null) {
            head = new Node<T>(data, head);
        } else {
            Node<T> tmp = head;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = new Node<T>(data, null);
        }
    }
    public void print(Node<T> node) {
        while (node != null) {
            System.out.print(node.data + "->");
            node = node.next;
        }
        System.out.print("NULL");
        System.out.println();
    }
    public Node reverseInGivenSize(Node<T> currentNode, int size) {
        Node<T> finalReverseNode = null;
        Node<T> reverseNode = null;
        Node<T> nextNode = null;
        int count = 0;
        while(currentNode != null) {
            count = count+1;
            nextNode = currentNode.next;
            currentNode.next = reverseNode;
            reverseNode = currentNode;
            currentNode = nextNode;
            if(count == size  || currentNode == null) {
                if(finalReverseNode == null) {
                    finalReverseNode = reverseNode;
                } else {
                    Node<T> tmp = finalReverseNode;
                    while (tmp.next != null) {
                        tmp = tmp.next;
                    }
                    tmp.next = reverseNode;
                }
                reverseNode= null;
                count = 0;
            }
        }
        return finalReverseNode;
    }

    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList();
        for (int i = 1; i <= 10; i++) {
            linkedList.addLast(i);
        }
        linkedList.print(linkedList.head);   // 1->2->3->4->5->6->7->8->9->10->NULL
        Node reverseNode1 = linkedList.reverseInGivenSize(linkedList.head, 2);
        linkedList.print(reverseNode1);     //2->1->4->3->6->5->8->7->10->9->NULL
    }
}

---

Detect a loop in Linked list-

To detect a loop again we have to maintain 2 pointer slow pointer and fast pointer as mention one of previous solution fast pointer will move 2 node while slow pointer will move 1 node at a time, if linked list have a loop than these pointer will meet on same node after some time.

Refer below code snippet-

package com.mk.ds.linkedlist;

public class CircularLinkedList<T> {
    private Node<T> head;
    public Node<T> tail;

    private static class Node<T> {
        private T data;
        private Node<T> next;
        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    public void add(T data) {
        Node<T> node = new Node<T>(data, head);
        if (head == null) {
            // for blank linked list head and tail will
            //point to same node and
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        tail.next = head;
    }

    public void print(Node<T> node) {
        Node<T> head = node;
        while (node.next != head) {
            System.out.print(node.data + "->");
            node = node.next;
        }
        System.out.print(node.data);
    }

    public void detectLoop(Node<T> node) {
        Node<T> slowPtr = node;
        Node<T> fastPtr = node;
        boolean circularFlag  = false;

        while (null != fastPtr && null != fastPtr.next) {
            fastPtr = fastPtr.next.next;
            slowPtr = slowPtr.next;
            if(slowPtr == fastPtr) {
                circularFlag = true;
                break;
            }
        }

        if(circularFlag) {
            System.out.print("Circular");
        } else
             System.out.print("Non Circular");

    }

    public static void main(String[] args) {
        CircularLinkedList<Integer> linkedList = new CircularLinkedList();
        for (int i = 1; i <= 3; i++) {
            linkedList.add(i);
        }linkedList.detectLoop(linkedList.head);   }}

---

Remove duplicate nodes in an unsorted linked list

To remove duplicate element store all element in a map node as key and duplicate occurrence as value than create a linked list from map keys only.

public void removeDuplicate(Node<Integer> node){

    Node unique = null;
    Map<Integer, Integer> mapData = new HashMap<>();
    while(null != node) {
        if(null != mapData.get(node.data)) {
            mapData.put(node.data, mapData.get(node.data)+1);
        } else {
            mapData.put(node.data, 1);
        }
        node = node.next;
    }

    LinkedList<Integer> linkedList = new LinkedList();
    Set<Integer> key = mapData.keySet();
    for(int val : key) {
        linkedList.addLast(val);
    }
    linkedList.print(linkedList.head);
}

---

Nth node from the end in a linked list-

To find the Nth node from the last maintain 2 pointer again, fast pointer and slow pointer

first start fast pointer and when it reaches to nth node from the head, than start second slow pointer, in this way when fast pointer reaches the last node, slow pointer will be at Nth node from the end.

public void nTheNodeFromEnd(Node currentNode, int n) {

    Node slowPtr = currentNode;
    Node fastPtr = currentNode;
    int count = 1;

    if (null != currentNode) {
        while (null != fastPtr && null != fastPtr.next) {
            fastPtr = fastPtr.next.next;
            if(count > n)
                slowPtr = slowPtr.next;
        }
        System.out.println("nth element from end is ::" + slowPtr.data);
    }
}

---

Insert a node in a given linked list

To insert a node first find the appropriate position to insert mark prev node and next node on that position,

prev-node -> next-node

temp = prev-node.next

prev-node.next = inserted-node

inserted-node.next = temp

prev-node -> inserted-node -> next-node

---

Delete a node in a given linked list

To delete a node find the deleted node position and identify the prev-node and next-node, than store the pointer of next-node in prev-node

prev-node-> delete-node ->next-node

temp -> delete-node.next

prev-node -> temp

prve-node -> next-node

---

Rotate a linked list by N node.

Assume anti-clock wise rotation by k node, let’s explain from given example

1->2->3->4->5->6->7   rotate by 4 node so resultant will be

5->6->7->1->2->3->4

public Node rotateByNthNode(Node currentNode, int n) {
    if (n == 0)
        return currentNode;
    Node current = currentNode;
    int count = 1;
    while (count < n && null != current) {
        current = current.next;
        count++;
    }

    Node nThNode = current;
    while (null != current && null != current.next)
        current = current.next;
    current.next = currentNode;
    currentNode = nThNode.next;
    nThNode.next = null;
    return currentNode;
}