Linked Lists Explained

A linked list stores a sequence of elements as separate nodes, where each node holds a value and a pointer to the next node. Unlike an array, the nodes are not laid out contiguously in memory — they can sit anywhere, connected only by these pointers. This buys you cheap insertion and deletion at the cost of losing instant indexing.

Anatomy of a node

Every node in a singly linked list has two parts: the data it stores, and a next pointer to the following node. The last node's next points to nothing (null), which marks the end of the list. A single pointer called the head points to the first node, and that is your only handle on the entire chain.

To visit element five, you start at the head and follow next five times. There is no address arithmetic like an array, so reaching a particular position is O(n).

Why insertion can be fast

Adding a node to the front of a linked list is O(1): you create the node, point its next at the current head, and update the head to the new node. Nothing shifts. Compare that with inserting at the front of an array, which forces every existing element to move along — an O(n) operation.

Building a singly linked list

#include <iostream>
using namespace std;

// A node stores one value and a link to the next node.
struct Node {
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

// Insert a new value at the front of the list.
// This is O(1): no traversal, no shifting.
Node* insertAtHead(Node* head, int value) {
    Node* node = new Node(value); // make the new node
    node->next = head;            // it points to the old first node
    return node;                  // the new node becomes the head
}

// Walk the list from head to tail, printing each value. O(n).
void printList(Node* head) {
    Node* current = head;
    while (current != nullptr) {  // stop when we reach the end
        cout << current->data << " -> ";
        current = current->next;  // step to the next node
    }
    cout << "null" << endl;
}

int main() {
    Node* head = nullptr;       // empty list
    head = insertAtHead(head, 30);
    head = insertAtHead(head, 20);
    head = insertAtHead(head, 10);
    printList(head);            // prints: 10 -> 20 -> 30 -> null
    return 0;
}

Notice there is no resizing and no copying of a whole block. The trade-off is that to find the node holding 30, you must walk the chain from the head.

Linked list versus array

*Amortised for dynamic arrays. **O(1) if you keep a tail pointer.

Linked lists shine when you do many insertions and deletions and rarely need random access. Arrays win when you index frequently and value cache-friendly iteration.

Common mistakes

• Losing the head. If you reassign the head pointer without keeping a reference to the old chain, you orphan the whole list and leak memory.
• Forgetting the null check. Dereferencing current->next when current is null crashes the program. Always test for the end before stepping.
• Memory leaks. In C++, every new Node needs a matching delete when the node is removed. Forgetting this leaks memory over time.
• Assuming O(1) access. Linked lists do not support indexing in constant time. If you find yourself writing a loop to reach position i constantly, an array is the better fit.
• Breaking the chain mid-edit. When inserting or deleting, set the new links before discarding the old ones, or you will lose the rest of the list.

FAQ

Why use a linked list if arrays are usually faster? Linked lists give O(1) insertion and deletion at known positions without shifting, which matters for queues, certain caches, and structures that change shape constantly.

What is the difference from a doubly linked list? A doubly linked list adds a prev pointer so you can walk backwards and delete a node in O(1) without needing its predecessor. See Doubly Linked Lists Explained.

Keep learning

Build on this with Doubly Linked Lists, revisit Arrays as a Data Structure to compare the trade-offs, and explore the full DSA hub.

Want to implement linked lists with guidance from instructors in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.