C++UCS301
Linear Data StructuresC++17

Singly Linked List

Each node stores a value and a pointer to the next node. Lists avoid shifting elements but sacrifice random access.

What to understand

  • Node ownership
  • Head and tail pointers
  • Insertion and deletion
  • Reversal

Remember this

  1. 1Access is sequential
  2. 2Head insertion is O(1)
  3. 3Update links before losing nodes
  4. 4Handle empty and single-node cases

Detailed notes

A singly linked list stores nodes independently and connects them through next pointers. It grows without relocating existing nodes, but reaching the kth element requires following k links.

A head pointer is sufficient; an optional tail makes append constant-time. Ownership must be explicit because removing a link does not automatically free the detached node when raw pointers are used.

How it works

  1. 1Draw the affected links before modifying them.
  2. 2Save next before deleting or reversing a node.
  3. 3Treat head changes as a separate boundary case or use a dummy node.
  4. 4Maintain tail whenever the last node changes.

Worked trace

Reverse 1 → 2 → 3

previous = null, current = 1
  1. 1Save next=2; point 1.next to null.
  2. 2Move previous to 1 and current to 2.
  3. 3Save next=3; point 2.next to 1.
  4. 4Point 3.next to 2 and make 3 the new head.
Result: 3 → 2 → 1 → null · every link changed once

Where it is used

  • Separate chaining in hash tables
  • Adjacency lists
  • Free lists and lightweight sequences with frequent front updates

Common mistakes

  • Losing the rest of the list by overwriting next too early
  • Dereferencing null during deletion
  • Leaking nodes or deleting the same node twice

Complexity analysis

OperationBestAverageWorstExtra space
Access/searchO(n)O(n)O(n)O(1)
Insert at headO(1)O(1)O(1)O(1)
Insert at tailO(1)O(1)O(n)O(1)
Delete after known nodeO(1)O(1)O(1)O(1)

C++ implementation

C++17 reference
main.cpp

Singly linked list with reversal

The destructor prevents leaks; reverse changes each next pointer exactly once.

#include <iostream>
using namespace std;

class LinkedList {
    struct Node { int value; Node* next; };
    Node* head = nullptr;
public:
    ~LinkedList() {
        while (head) { Node* old = head; head = head->next; delete old; }
    }
    void pushFront(int value) { head = new Node{value, head}; }
    void reverse() {
        Node *previous = nullptr, *current = head;
        while (current) {
            Node* next = current->next;
            current->next = previous;
            previous = current;
            current = next;
        }
        head = previous;
    }
    void print() const {
        for (Node* node = head; node; node = node->next)
            cout << node->value << ' ';
    }
};

int main() {
    LinkedList list;
    for (int value : {3, 2, 1}) list.pushFront(value);
    list.reverse();
    list.print();
}
33 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.