Section 02 — Section 2: Singly Linked List Implementation & Pointer Operations

1. Introduction: Contiguous Arrays vs. Singly Linked Lists

In computer science, linear collections can be represented primarily in two foundational memory formats: contiguous array blocks or discrete pointer-linked nodes. Understanding the computational tradeoffs between these two memory representations is fundamental to mastering data structures.

Output

ARRAY (Contiguous Memory):
+-----------+-----------+-----------+-----------+
|  arr[0]   |  arr[1]   |  arr[2]   |  arr[3]   |   Direct address: Base + (i * size)
|    10     |    20     |    30     |    40     |   Instant O(1) random indexing
+-----------+-----------+-----------+-----------+
  0x1000      0x1004      0x1008      0x100C

LINKED LIST (Scattered Heap Nodes):
[ Head: 10 | 0x24B0 ] ---> [ 20 | 0x38F0 ] ---> [ 30 | 0x19A0 ] ---> [ Tail: 40 | nullptr ]
     @ 0x1050                   @ 0x24B0             @ 0x38F0               @ 0x19A0

1.1 Structural Limitations of Contiguous Arrays

Fixed Size & Reallocation Penalty: Standard C++ arrays possess fixed capacity at compile time. Dynamic arrays (std::vector) must allocate a new, larger memory block and copy all existing elements over when capacity is exceeded ( $O(n)$ reallocation cost).
Costly Insertions and Deletions ( $O(n)$ ): Inserting or deleting an element at arbitrary positions requires shifting all downstream elements forward or backward in memory.

1.2 Advantages and Trade-offs of Linked Lists

A Singly Linked List allocates memory dynamically for each element as a standalone Node on the heap. Nodes are linked unidirectionally via address pointers.

Dynamic Growth: Consumes heap memory strictly proportional to the number of stored elements.
Efficient Insertions & Deletions ( $O(1)$ ): Splicing a new node into the list or removing an existing one only requires redirecting adjacent pointers, requiring zero element shifting.
No Instant Random Access ( $O(n)$ ): Because nodes are scattered at non-contiguous memory locations, accessing index $i$ requires sequential pointer traversal starting from head.

1.3 Comparative Feature Matrix

Evaluation Aspect	Standard Contiguous Array	Singly Linked List
Memory Allocation	Single contiguous memory block	Scattered heap nodes linked by pointers
Element Access	Instant random access by index: `arr[i]` ( $O(1)$ )	Sequential pointer walk from `head` ( $O(n)$ )
Insertion at Beginning	Requires shifting all $n$ items ( $O(n)$ )	Redirect `head` pointer ( $O(1)$ )
Insertion at End	$O(1)$ if spare capacity; $O(n)$ on reallocation	$O(1)$ with dedicated `tail` pointer
Deletion at Beginning	Requires shifting all $n-1$ items ( $O(n)$ )	Advance `head` and `delete` ( $O(1)$ )
Memory Overhead	Minimal (strictly data payload)	Additional memory per node for pointer (`next`)
Cache Locality	High (adjacent memory benefits CPU prefetching)	Low (scattered addresses induce cache misses)

2. Anatomy of a Node & Class Blueprint

Every element in a singly linked list is modeled as an independent Node. Each node holds two fundamental members:

data: The payload value (e.g., int).
next: A raw pointer storing the memory address of the next Node in sequence, or nullptr for the terminal node.

Output

+-----------------------+
|         Node          |
+-----------------------+
|  data  : int          |  Payload
|  next  : Node*        |  Pointer to subsequent Node (or nullptr)
+-----------------------+

2.1 Struct Node Definition in C++

cpp

struct Node {
    int data;
    Node* next;

    // Node constructor initializes data and defaults next pointer to nullptr
    Node(int value) : data(value), next(nullptr) {}
};

Modern C++ Practice: Always use nullptr instead of NULL or 0. nullptr is strongly typed (std::nullptr_t), eliminating ambiguous overload resolution bugs between pointers and integers.

2.2 LinkedList Class Architecture: Head and Tail

The LinkedList class encapsulates node manipulation and maintains internal state:

head: Pointer to the very first node in the sequence (the entry portal).
tail: Pointer to the last node in the sequence.

Output

EMPTY LIST:
head = nullptr
tail = nullptr

SINGLE-NODE LIST:
head ---> [ 10 | nullptr ] <--- tail

MULTI-NODE LIST:
head ---> [ 10 | • ] ---> [ 20 | • ] ---> [ 30 | nullptr ] <--- tail

cpp

class LinkedList {
private:
    Node* head;
    Node* tail;

public:
    LinkedList() : head(nullptr), tail(nullptr) {}

    // Core Member Operations
    void insertAtBeginning(int value);
    void insertAtEnd(int value);
    void insertAtPosition(int value, int position);

    void deleteFromBeginning();
    void deleteAtEnd();
    void deleteAtPosition(int pos);

    void traverse();
    void search(int key);
};

3. Insertion Operations

3.1 Insert at Beginning (`insertAtBeginning`)

Inserting at the front prepends a new node before the current head. This is an instantaneous $O(1)$ operation regardless of list size.

Algorithmic Procedure:

Allocate a new heap node: Node* newNode = new Node(value).
Connect newNode->next to the current head.
Reassign head to point to newNode.
Boundary Condition: If the list was initially empty (tail == nullptr), the newly inserted node is simultaneously the head and the tail.

Output

BEFORE:
head ---> [ 10 | • ] ---> [ 20 | nullptr ] <--- tail

STEP 1 & 2:
newNode ---> [ 5 | • ]
               |
               v
head --------> [ 10 | • ] ---> [ 20 | nullptr ] <--- tail

STEP 3:
head = newNode
head ---> [ 5 | • ] ---> [ 10 | • ] ---> [ 20 | nullptr ] <--- tail

C++ Implementation:

cpp

void insertAtBeginning(int value) {
    Node* newNode = new Node(value);
    newNode->next = head;
    head = newNode;
    if (tail == nullptr) {
        tail = newNode;
    }
}

Time Complexity: $O(1)$
Space Complexity: $O(1)$

3.2 Insert at End (`insertAtEnd`)

Appending an element to the tail of the list. By maintaining an explicit tail pointer, this operation executes in $O(1)$ time without requiring an $O(n)$ scan from head.

Algorithmic Procedure:

Allocate a new heap node: Node* newNode = new Node(value).
Boundary Condition (Empty List): If head == nullptr, set both head = newNode and tail = newNode.
Populated List: Link the current tail->next = newNode, then update tail = newNode.

Output

BEFORE:
head ---> [ 10 | • ] ---> [ 20 | nullptr ] <--- tail

STEP 1 & 2:
tail->next = newNode
head ---> [ 10 | • ] ---> [ 20 | • ] ---> [ 30 | nullptr ] <--- newNode

STEP 3:
tail = newNode
head ---> [ 10 | • ] ---> [ 20 | • ] ---> [ 30 | nullptr ] <--- tail

C++ Implementation:

cpp

void insertAtEnd(int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        head = tail = newNode;
    } else {
        tail->next = newNode;
        tail = newNode;
    }
}

Time Complexity: $O(1)$ with tail pointer ( $O(n)$ if list only maintains head)
Space Complexity: $O(1)$

3.3 Insert at an Arbitrary Position (`insertAtPosition`)

Inserts a value at a specified 1-based index position.

Algorithmic Procedure:

If position == 1, delegate directly to front insertion (newNode->next = head; head = newNode; and update tail if needed).
Otherwise, initialize a pointer Node* temp = head and traverse $position - 2$ steps forward to reach the node immediately preceding the target index.
If temp == nullptr, the requested position exceeds the list bounds.
Pointer Splicing Sequence (Crucial Order):
- Step A: newNode->next = temp->next; (connect new node to the downstream chain first).
- Step B: temp->next = newNode; (connect upstream node to new node).
Tail Maintenance: If newNode->next == nullptr, the new node has become the last node; update tail = newNode.

Output

INSERT AT POSITION 3 (between node 2 and node 3):

temp (at pos 2)
  [ 10 | • ] ---> [ 20 | • ] -------------> [ 30 | nullptr ]
                     ^                           ^
                     |                           |
                     |   newNode ---> [ 25 | • ]-+  (Step A: newNode->next = temp->next)
                     +-------------------+          (Step B: temp->next = newNode)

Warning — The Pointer Overwrite Trap: Never execute temp->next = newNode before newNode->next = temp->next. Doing so permanently breaks the pointer chain and leaves all subsequent nodes orphaned in memory (unreachable memory leak).

C++ Implementation:

cpp

void insertAtPosition(int value, int position) {
    Node* newNode = new Node(value);
    if (position == 1) {
        newNode->next = head;
        head = newNode;
        if (tail == nullptr) tail = newNode;
        return;
    }

    Node* temp = head;
    for (int i = 1; i < position - 1 && temp != nullptr; i++) {
        temp = temp->next;
    }

    if (temp == nullptr) {
        cout << "Position out of bounds" << endl;
        delete newNode; // Avoid memory leak on invalid insertion
    } else {
        newNode->next = temp->next;
        temp->next = newNode;
        if (newNode->next == nullptr) {
            tail = newNode;
        }
    }
}

Time Complexity: $O(n)$ in the worst case (traversing up to position $n$ )
Space Complexity: $O(1)$

4. Deletion Operations & Memory Management

In C++, memory allocated dynamically via new persists on the heap until explicitly released using delete. Dropping pointers without calling delete causes memory leaks.

Output

DELETION WORKFLOW:
1. Save target node address to a temporary pointer.
2. Re-link upstream and downstream pointer paths.
3. Call 'delete temp' to release heap memory.
4. Verify boundary pointers (head and tail).

4.1 Delete from Beginning (`deleteFromBeginning`)

Removes the frontmost node in $O(1)$ time.

Algorithmic Procedure:

Empty Guard: If head == nullptr, report that the list is empty and exit.
Hold the current head in a temporary pointer: Node* temp = head.
Advance head: head = head->next.
Deallocate the isolated node: delete temp.
Empty Reset: If head == nullptr following deletion, reset tail = nullptr.

Output

BEFORE:
head ---> [ 10 | • ] ---> [ 20 | • ] ---> [ 30 | nullptr ] <--- tail

STEP 1 & 2:
temp = head
head = head->next
temp ---> [ 10 | • ]
head --------------> [ 20 | • ] ---> [ 30 | nullptr ] <--- tail

STEP 3:
delete temp;
head --------------> [ 20 | • ] ---> [ 30 | nullptr ] <--- tail

C++ Implementation:

cpp

void deleteFromBeginning() {
    if (head == nullptr) {
        cout << "List is empty!" << endl;
        return;
    }
    Node* temp = head;
    head = head->next;
    cout << "Deleted " << temp->data << " from beginning." << endl;
    delete temp;
    if (head == nullptr) {
        tail = nullptr;
    }
}

Time Complexity: $O(1)$
Space Complexity: $O(1)$

4.2 Delete at End (`deleteAtEnd`)

Deleting the terminal node requires updating the second-to-last node's next pointer to nullptr.

Key Asymmetry: In a singly linked list, deleteAtEnd is $O(n)$ even when a tail pointer is present. Because pointers are strictly unidirectional, there is no direct way to step backward from tail to find its predecessor without traversing forward from head.

Algorithmic Procedure:

Empty Guard: If head == nullptr, exit.
Single-Node Case: If head->next == nullptr, delete head and reset head = tail = nullptr.
Multi-Node Case: Traverse until temp->next->next == nullptr (locating the second-to-last node).
Free the tail node: delete temp->next.
Seal the chain: temp->next = nullptr.
Reposition tail: tail = temp.

Output

TRAVERSE TO SECOND-TO-LAST:
head ---> [ 10 | • ] ---> [ 20 | • ] ---> [ 30 | nullptr ]
                           ^                ^
                           |                |
                          temp          temp->next (tail to delete)

AFTER DELETION:
head ---> [ 10 | • ] ---> [ 20 | nullptr ] <--- tail (temp)

C++ Implementation:

cpp

void deleteAtEnd() {
    if (head == nullptr) {
        cout << "List is empty!" << endl;
        return;
    }
    if (head->next == nullptr) {
        cout << "Deleted " << head->data << " from end." << endl;
        delete head;
        head = tail = nullptr;
        return;
    }

    Node* temp = head;
    while (temp->next->next != nullptr) {
        temp = temp->next;
    }

    cout << "Deleted " << temp->next->data << " from end." << endl;
    delete temp->next;
    temp->next = nullptr;
    tail = temp;
}

Time Complexity: $O(n)$
Space Complexity: $O(1)$

4.3 Delete at an Arbitrary Position (`deleteAtPosition`)

Deletes the node residing at 1-based index pos.

Algorithmic Procedure:

Empty Guard: If head == nullptr, return.
Position 1 Special Case: Delegate to head removal (delete toDelete; head = head->next;).
Traverse to position pos - 1 with pointer temp.
Validate bounds: if temp == nullptr or temp->next == nullptr, index is invalid.
Identify node to remove: Node* toDelete = temp->next.
Bypass the target node: temp->next = toDelete->next.
Free heap memory: delete toDelete.
Tail Maintenance: If temp->next == nullptr, the removed node was the previous tail; update tail = temp.

Output

DELETE AT POSITION 2:
head ---> [ 10 | • ] -------> [ 20 | • ] -------> [ 30 | nullptr ]
             ^                   ^
             |                   |
            temp             toDelete

BYPASS:
temp->next = toDelete->next
head ---> [ 10 | • ] ---------------------------> [ 30 | nullptr ]
                                 [ 20 | • ] (freed via delete toDelete)

C++ Implementation:

cpp

void deleteAtPosition(int pos) {
    if (head == nullptr) {
        cout << "List is empty" << endl;
        return;
    }
    if (pos == 1) {
        Node* toDelete = head;
        head = head->next;
        cout << "Deleted " << toDelete->data << " from position 1." << endl;
        delete toDelete;
        if (head == nullptr) tail = nullptr;
        return;
    }

    Node* temp = head;
    for (int i = 1; temp != nullptr && i < pos - 1; i++) {
        temp = temp->next;
    }

    if (temp == nullptr || temp->next == nullptr) {
        cout << "Invalid position" << endl;
        return;
    }

    Node* toDelete = temp->next;
    temp->next = toDelete->next;
    cout << "Deleted " << toDelete->data << " from position " << pos << "." << endl;
    delete toDelete;

    if (temp->next == nullptr) {
        tail = temp;
    }
}

Time Complexity: $O(n)$
Space Complexity: $O(1)$

5. Inspection Operations: Traversal & Linear Search

5.1 Traversal (`traverse`)

Visits every node sequentially starting from head until temp reaches nullptr.

Output

POINTER WALK:
temp = head
while (temp != nullptr) {
    process(temp->data);
    temp = temp->next;   // Advance one link forward
}

cpp

void traverse() {
    if (head == nullptr) {
        cout << "List is empty." << endl;
        return;
    }
    Node* temp = head;
    cout << "List: ";
    while (temp != nullptr) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

Time Complexity: $O(n)$
Space Complexity: $O(1)$

5.2 Linear Search (`search`)

Scans the list sequentially comparing temp->data against target key. Returns immediately upon first match.

cpp

void search(int key) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == key) {
            cout << key << " found in the list." << endl;
            return;
        }
        temp = temp->next;
    }
    cout << key << " not found in the list." << endl;
}

Time Complexity: $O(n)$ worst-case; $O(1)$ best-case (key at head)
Space Complexity: $O(1)$

6. Critical Edge Cases & Common Pitfalls

Edge Scenario	Potential Vulnerability	Defensive Implementation Rule
Empty List Operations	Segmentation fault when dereferencing `head->next`	Guard with `if (head == nullptr)` at the start of every operation
Single-Node Deletion	Dangling `tail` pointing to deallocated memory	When the last remaining node is deleted, explicitly reset `head = tail = nullptr;`
Position Out of Bounds	Accessing invalid memory when traversing past end	Ensure `temp != nullptr` in loop conditions and verify `temp->next != nullptr`
Splicing Order Inversion	Dropping rest of list into an unreachable memory leak	Connect `newNode->next = temp->next` before assigning `temp->next = newNode`
Omission of `delete`	Memory leak on the heap	Every `new Node(...)` removed from the chain must be released with `delete ptr`
Tail Not Updated on Appends	Tail points to stale inner node	Update `tail = newNode` whenever inserting at the end of the chain

7. Complete Executable Program & Trace Walkthrough

Below is the complete, self-contained C++ source code corresponding to linked-list.cpp.

cpp

/*
 * Data Structures & Algorithms - Section 2: Linked Lists
 * Complete singly linked list implementation in modern C++.
 *
 * Compilation: g++ -std=c++17 linked-list.cpp -o linked-list
 * Execution:   ./linked-list (or linked-list.exe on Windows)
 */

#include <iostream>
using namespace std;

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

class LinkedList {
private:
    Node* head;
    Node* tail;

public:
    LinkedList() : head(nullptr), tail(nullptr) {}

    // ----- INSERTION -----
    void insertAtBeginning(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
        if (tail == nullptr) tail = newNode;
    }

    void insertAtEnd(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    void insertAtPosition(int value, int position) {
        Node* newNode = new Node(value);
        if (position == 1) {
            newNode->next = head;
            head = newNode;
            if (tail == nullptr) tail = newNode;
            return;
        }
        Node* temp = head;
        for (int i = 1; i < position - 1 && temp != nullptr; i++) {
            temp = temp->next;
        }
        if (temp == nullptr) {
            cout << "Position out of bounds" << endl;
            delete newNode;
        } else {
            newNode->next = temp->next;
            temp->next = newNode;
            if (newNode->next == nullptr) tail = newNode;
        }
    }

    // ----- DELETION -----
    void deleteFromBeginning() {
        if (head == nullptr) {
            cout << "List is empty!" << endl;
            return;
        }
        Node* temp = head;
        head = head->next;
        cout << "Deleted " << temp->data << " from beginning." << endl;
        delete temp;
        if (head == nullptr) tail = nullptr;
    }

    void deleteAtEnd() {
        if (head == nullptr) {
            cout << "List is empty!" << endl;
            return;
        }
        if (head->next == nullptr) {
            cout << "Deleted " << head->data << " from end." << endl;
            delete head;
            head = tail = nullptr;
            return;
        }
        Node* temp = head;
        while (temp->next->next != nullptr) {
            temp = temp->next;
        }
        cout << "Deleted " << temp->next->data << " from end." << endl;
        delete temp->next;
        temp->next = nullptr;
        tail = temp;
    }

    void deleteAtPosition(int pos) {
        if (head == nullptr) {
            cout << "List is empty" << endl;
            return;
        }
        if (pos == 1) {
            Node* toDelete = head;
            head = head->next;
            cout << "Deleted " << toDelete->data << " from position 1." << endl;
            delete toDelete;
            if (head == nullptr) tail = nullptr;
            return;
        }
        Node* temp = head;
        for (int i = 1; temp != nullptr && i < pos - 1; i++) {
            temp = temp->next;
        }
        if (temp == nullptr || temp->next == nullptr) {
            cout << "Invalid position" << endl;
            return;
        }
        Node* toDelete = temp->next;
        temp->next = toDelete->next;
        cout << "Deleted " << toDelete->data << " from position " << pos << "." << endl;
        delete toDelete;
        if (temp->next == nullptr) tail = temp;
    }

    // ----- TRAVERSAL -----
    void traverse() {
        if (head == nullptr) {
            cout << "List is empty." << endl;
            return;
        }
        Node* temp = head;
        cout << "List: ";
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }

    // ----- SEARCH -----
    void search(int key) {
        Node* temp = head;
        while (temp != nullptr) {
            if (temp->data == key) {
                cout << key << " found in the list." << endl;
                return;
            }
            temp = temp->next;
        }
        cout << key << " not found in the list." << endl;
    }
};

int main() {
    LinkedList list;

    cout << "=== Insert at End ===" << endl;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.traverse();

    cout << "\n=== Insert at Beginning ===" << endl;
    list.insertAtBeginning(5);
    list.traverse();

    cout << "\n=== Insert at Position 3 ===" << endl;
    list.insertAtPosition(15, 3);
    list.traverse();

    cout << "\n=== Search ===" << endl;
    list.search(15);
    list.search(99);

    cout << "\n=== Delete from Beginning ===" << endl;
    list.deleteFromBeginning();
    list.traverse();

    cout << "\n=== Delete from End ===" << endl;
    list.deleteAtEnd();
    list.traverse();

    cout << "\n=== Delete from Position 2 ===" << endl;
    list.deleteAtPosition(2);
    list.traverse();

    return 0;
}

Expected Output

Output

=== Insert at End ===
List: 10 -> 20 -> 30 -> NULL

=== Insert at Beginning ===
List: 5 -> 10 -> 20 -> 30 -> NULL

=== Insert at Position 3 ===
List: 5 -> 10 -> 15 -> 20 -> 30 -> NULL

=== Search ===
15 found in the list.
99 not found in the list.

=== Delete from Beginning ===
Deleted 5 from beginning.
List: 10 -> 15 -> 20 -> 30 -> NULL

=== Delete from End ===
Deleted 30 from end.
List: 10 -> 15 -> 20 -> NULL

=== Delete from Position 2 ===
Deleted 15 from position 2.
List: 10 -> 20 -> NULL

8. Master Complexity Reference

Operation	Time Complexity (Head & Tail)	Time Complexity (Head Only)	Space Complexity	Primary Bottleneck / Rationale
Insert at Beginning	$O(1)$	$O(1)$	$O(1)$	Direct pointer reassignment at `head`
Insert at End	$O(1)$	$O(n)$	$O(1)$	Instant append via `tail->next` vs traversal
Insert at Position	$O(n)$	$O(n)$	$O(1)$	Sequential scan to target index $pos - 1$
Delete from Beginning	$O(1)$	$O(1)$	$O(1)$	Advance `head` and free memory
Delete at End	$O(n)$	$O(n)$	$O(1)$	Must traverse forward to find second-to-last node
Delete at Position	$O(n)$	$O(n)$	$O(1)$	Sequential scan to predecessor node
Linear Search	$O(n)$	$O(n)$	$O(1)$	Must scan elements until match or `nullptr`
Sequential Traversal	$O(n)$	$O(n)$	$O(1)$	Visits each of the $n$ nodes once

1. Introduction: Contiguous Arrays vs. Singly Linked Lists

1.1 Structural Limitations of Contiguous Arrays

1.2 Advantages and Trade-offs of Linked Lists

1.3 Comparative Feature Matrix

2. Anatomy of a Node & Class Blueprint

2.1 Struct Node Definition in C++

2.2 LinkedList Class Architecture: Head and Tail

3. Insertion Operations

3.1 Insert at Beginning (insertAtBeginning)

Algorithmic Procedure:

C++ Implementation:

3.2 Insert at End (insertAtEnd)

Algorithmic Procedure:

C++ Implementation:

3.3 Insert at an Arbitrary Position (insertAtPosition)

Algorithmic Procedure:

C++ Implementation:

4. Deletion Operations & Memory Management

4.1 Delete from Beginning (deleteFromBeginning)

Algorithmic Procedure:

C++ Implementation:

4.2 Delete at End (deleteAtEnd)

Algorithmic Procedure:

C++ Implementation:

4.3 Delete at an Arbitrary Position (deleteAtPosition)

Algorithmic Procedure:

C++ Implementation:

5. Inspection Operations: Traversal & Linear Search

5.1 Traversal (traverse)

5.2 Linear Search (search)

6. Critical Edge Cases & Common Pitfalls

7. Complete Executable Program & Trace Walkthrough

Expected Output

8. Master Complexity Reference

3.1 Insert at Beginning (`insertAtBeginning`)

3.2 Insert at End (`insertAtEnd`)

3.3 Insert at an Arbitrary Position (`insertAtPosition`)

4.1 Delete from Beginning (`deleteFromBeginning`)

4.2 Delete at End (`deleteAtEnd`)

4.3 Delete at an Arbitrary Position (`deleteAtPosition`)

5.1 Traversal (`traverse`)

5.2 Linear Search (`search`)