[Data Structures] Linked List

A Linked list is a data structure that represents a sequence of nodes. In a singly linked list, each node points to the next node in the linked list. A doubly linked list gives each node pointers to both the next node and the previous one.

 

Unlike an array, a linked list does not provide constant-time access to a particular "index' within the list. This means that if you'd like to find the K'th element in the list, you will need to iterate through K elements. The benefit of a linked list is that you can add and remove items from the beginning of the list in constant time. 

 

Creating a Linked List:

class Node {
    Node next = null;
    int data;

    public Node(int value){
        data = value;
    }

    void insertNodeAtTail(int value){
        Node newNode = new Node(value);
        Node n = this;
        while(n.next != null) {
            n = n.next;
        }
        n.next = newNode;
    }
}

Deleting a Linked List:

public Node deleteNode(Node head, int value) {
    Node n = head;
    if (n.data==value){
        return head.next;
    }

    while (n.next.next != null){
        if (n.next.data == value){
            n.next = n.next.next;
            return head; //head doesn't change
        }
        n = n.next;
    }
    return head;
}

It returns head to keep in track of the linked list.

 

The "Runner" Technique

The "runner" technique is used in many linked list problems. The runner technique means that you integrate through the linked list with two pointers simultaneously, one ahead of the other. The "fast" node might be ahead by a fixed amount, or it might be hopping multiple nodes for each node that the "slow" node iterates through. 

 

For example, suppose you have a linked list a1 -> a2 -> /// an-> b1 -> b2 -> ... -> bn and you wanted to rearrange it into a1 -> b1 -> a2 -> b2 -> ... -> an -> bn. You do not know the length of the linked list (but you do know that the length is an even number).

 

You could have one pointer p1 (the fast pointer) move every two elements for every one move that p2 makes. When p1 hits the end of the linked list, p2 will be at the midpoint. Then, move p1 back to the front and begin "weaving" the elements. On each iteration, p2 selects an element and inserts It after p1.

 

Why? It's just like a circle. This algorithm helps with finishing the task in just one round.

 

Recursive Problems:

Several linked list problems rely on recursions. If you're having trouble solving a linked list problem, you should explore if a recursive approach will work.

 

Problem: Recursive algorithm takes at least O(n) space, where n is the depth of the recursive call. All recursive algorithms can be implemented iteratively, although they may be much more complex. 

 

From: Cracking the Coding Interview