Introduction

In the previous chapter, we discussed arrays and ArrayLists, which insert elements at the end and access them in constant time, O(1). However, what if we encounter scenarios where we need to frequently add or remove elements at the beginning or middle of the list? Arrays become inefficient for such tasks, as they require shifting elements around, resulting in a time complexity of O(N). This is where linked lists come in! Linked lists store data using nodes, with each node containing the data itself and a pointer linking it to the next node in the sequence. This pointer-based approach allows linked lists to efficiently insert and delete elements in the middle compared to arrays. Throughout this chapter, we'll delve into the world of linked lists and explore their structure.

What is 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 node

singly linked list and doubly linked list diagram:

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 Kth 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. For specific applications, this can be useful.

How to create a Linked List?

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

void appendToTail(int d) { 
Node end= new Node(d); 
 Node n = this;
 while (n.next != null) { 
  n = n.next; 
 }
n.next = end;
 }
}

In this implementation, we don't have a Linked List data structure. We access the linked list through a reference to the head Node of the linked list. When you implement the linked list this way, you need to be a bit careful. What if multiple objects need a reference to the linked list, and then the head of the linked list changes? Some objects might still be pointing to the old head.

let's consider an example:

public class Main {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.appendToTail(2);

        // Multiple objects referencing the head Node
        Node object1 = head;
        Node object2 = head;

        // Change the head of the linked list
        head = head.next;

        // Print data from objects referencing the old head
        System.out.println(object1.data);  // This may lead to unexpected behavior
        System.out.println(object2.data);  // This may lead to unexpected behavior
    }
}

In this example, both object1 and object2 initially reference the head Node of the linked list. However, when the head is changed, these objects are still pointing to the old head, leading to potential inconsistencies or errors when accessing data through them.

To address this issue, one approach is to encapsulate the linked list functionality within a separate class, where the class maintains a reference to the head Node. This way, changes to the head can be managed internally, ensuring consistency across all references to the linked list

Here's an example of encapsulating the linked list within a separate class:

class LinkedList {
    private Node head;

    public LinkedList() {
        head = null;
    }

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

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.append(1);
        list.append(2);
        list.append(3);

        list.printList(); // Output: 1 2 3
    }
}

Deleting a Node from a Singly Linked List

Deleting a node from a linked list is fairly straightforward. Given a node n, we find the previous node prev and set prev. next equal to n. next. If the list is doubly linked, we must also update n. next to set n. next. prev equal to n. prev.

The important things to remember are:

Check for the null pointer
Update the head or tail pointer as necessary. Additionally, if you implement this code in C, C++ or another language that requires the developer to do memory management, you should consider if the removed node should be deallocated.

Node deleteNode(Node head, int d) { 
 Node n = head; 

 if (n.data == d) { 
 return head.next; /* moved head*/ 
 } 

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

The "Runner" Technique

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

For example, suppose you had 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 pl (the fast pointer) move every two elements for every one move that p2 makes. When pl hits the end of the linked list, p2 will be at the midpoint. Then, move pl back to the front and begin "weaving" the elements. On each iteration, p2 selects an element and inserts it after pl.

Recursive Problems

Several linked list problems rely on recursion. If you're having trouble solving a linked list problem, you should explore if a recursive approach will work. We won't go into depth on recursion here, since a later chapter is devoted to it.

However, you should remember that recursive algorithms take at least O( n) space, where n is the depth of the recursive call.

Cracking the Coding Interview [Ch.2: Linked Lists]