Linked List

linked-list: The Ultimate Cheatsheet

1. Detailed Explanation

A linked list is a linear data structure where elements are stored in nodes. Each node contains data and a pointer (or reference) to the next node in the sequence. Unlike arrays, linked lists don’t store elements contiguously in memory. This allows for dynamic memory allocation and efficient insertion/deletion of elements anywhere in the list.

Why is it important? Linked lists are crucial because they excel in scenarios where frequent insertions and deletions are needed. Arrays require shifting elements, which is O(n) time complexity. Linked lists, on the other hand, only require updating pointers, resulting in O(1) time complexity for insertion and deletion (given the node’s location).

Core Concepts:

• Node: A basic building block containing data and a pointer (next) to the subsequent node.
• Head: A pointer to the first node in the linked list.
• Tail: (Optional) A pointer to the last node in the linked list. Simplifies appending operations.
• Null/None: The pointer value indicating the end of the list.

2. When to Use linked-list (and When Not To)

Use Linked Lists when:

• Frequent insertions or deletions are required at arbitrary positions.
• Memory efficiency is a concern and the size of the data structure is unknown beforehand.
• Implementing stacks or queues is needed.

Don’t Use Linked Lists when:

• Random access to elements is frequently required (arrays are much faster for this).
• Memory locality is crucial (linked lists suffer from poor cache performance compared to arrays).
• The size of the list is known and relatively fixed.

3. Core Algorithm / Data Structure Template

This template shows a singly linked list (each node points only to the next). Doubly linked lists (nodes point to both the next and previous nodes) are also common but add complexity.

Pseudocode for inserting at the beginning:

1. Create a new node with the given data.
2. Set the new node’s next pointer to the current head.
3. Set the head pointer to the new node.

Pseudocode for searching:

1. Start at the head node.
2. Iterate through the list, comparing the data of each node to the target value.
3. Return true if the target is found; otherwise, return false after reaching the end of the list.

4. Code Implementations

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def search(self, data):
        current = self.head
        while current:
            if current.data == data:
                return True
            current = current.next
        return False

    def print_list(self): #Helper function for demonstration
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

Java

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    boolean search(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    void printList(){ //Helper function for demonstration
        Node current = head;
        while(current != null){
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

C++

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void insertAtBeginning(int data) {
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
    }

    bool search(int data) {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == data) {
                return true;
            }
            current = current->next;
        }
        return false;
    }

    void printList(){ //Helper function for demonstration
        Node* current = head;
        while(current != nullptr){
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }
};

5. Complexity Analysis

Operation	Best Case	Average Case	Worst Case	Space Complexity
Search	O(1)	O(n)	O(n)	O(n)
Insertion (Head)	O(1)	O(1)	O(1)	O(n)
Deletion (Head)	O(1)	O(1)	O(1)	O(n)
Insertion (Mid)	O(n)	O(n)	O(n)	O(n)
Deletion (Mid)	O(n)	O(n)	O(n)	O(n)

6. Pro Tips, Tricks, and Common Pitfalls

• Memory Leaks: Always free dynamically allocated memory in C++ when nodes are deleted or the list is destroyed to avoid memory leaks. Python’s garbage collection handles this automatically.
• Null Pointer Exceptions: Always check for null or nullptr before dereferencing pointers to avoid crashes.
• Head Pointer: Carefully manage the head pointer during insertions and deletions; losing track of it renders the list unusable.
• Doubly Linked Lists: For bidirectional traversal, use doubly linked lists, but be aware of increased memory usage and complexity.
• Circular Linked Lists: Useful for certain applications (e.g., implementing circular buffers), but require careful handling of the tail pointer to avoid infinite loops.

7. Classic Problem Examples

Example: Add Two Numbers

High-Level Approach:

1. Iterate through both linked lists simultaneously, adding corresponding digits.
2. Handle carry-over from previous additions.
3. Create a new linked list to store the sum, adding each digit as a new node.
4. Handle the case where one list is longer than the other.

This approach involves iterating through the lists once, resulting in O(max(m,n)) time complexity where ‘m’ and ‘n’ are the lengths of the input lists. Space complexity is O(max(m,n)) to store the resulting sum list. The code implementation would involve creating a new Node for each digit in the sum and linking them together. Careful attention must be paid to handling the carry-over digit.