Summary

A linked list stores each value in a small box called a node. Every node holds its value and a pointer to the next node. The boxes can sit anywhere in memory, joined only by those pointers. This makes adding and removing items at the front very fast, but reaching the middle is slow.

A linked list is like a treasure hunt. Each clue holds one item and tells you where to find the next clue. You follow the chain one step at a time.

That design makes a linked list strong where an array is weak, and weak where an array is strong. Let me show you the chain, the code and the real trade against arrays.

What is a linked list?

A linked list is a chain of nodes. Each node holds two things. It holds a value, like a number or a name. And it holds a pointer, which is the address of the next node in the chain.

The list keeps one extra pointer called the head, which points to the very first node. To use the list, you start at the head and follow the pointers from node to node. The last node points to nothing, which marks the end.

This is different from an array, where all the values sit together in one block of memory. In a linked list, the nodes can live anywhere, joined only by their pointers.

How does a linked list work step by step?

Reading the idea is one thing. Watching the pointers is another. So let’s build and walk a small linked list by hand.

Say we have three nodes holding 10, 20 and 30. The head points to the node with 10. That node points to 20. The node with 20 points to 30. The node with 30 points to nothing, so we know the list ends there.

To read the list, start at the head and follow each pointer. You visit 10, then 20, then 30. This is called traversal, and it is the only way to reach a node. You cannot jump straight to the third one.

Now add a new value, 5, at the front. You make a node for 5, point it at the old first node 10, then move the head to point at 5. Three small steps and the new value is in front. No other node has to move.

Linked list code in Python and C++

First we need a node, which holds a value and a pointer to the next node. Then the list keeps a head. Here it is in Python.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None        # pointer to the next node

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

    def add_front(self, value):
        new_node = Node(value)
        new_node.next = self.head    # point new node at old first
        self.head = new_node         # head now points to new node

    def traverse(self):
        current = self.head
        while current is not None:
            print(current.value)
            current = current.next   # follow the pointer

The add_front method does exactly the three steps from our trace. The traverse method walks the chain until it hits the end. Here is the same idea in C++, the language most Indian placement tests expect.

struct Node {
    int value;
    Node* next;
};

Node* addFront(Node* head, int value) {
    Node* newNode = new Node();
    newNode->value = value;
    newNode->next = head;        // point at old first node
    return newNode;             // new node becomes the head
}

void traverse(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->value << endl;
        current = current->next;   // follow the pointer
    }
}

Both versions store a value plus a next pointer, then walk the chain by following next over and over. That walking is the heart of every linked list operation.

What is the time complexity of a linked list?

Adding or removing at the front is O(1), since you only change a couple of pointers. That is the linked list superpower. An array would have to shift every item to make room at the front, which is O(n).

But reaching an item by position is O(n). To get the fifth node, you must start at the head and follow four pointers. There is no jumping. An array reaches any position instantly at O(1). The space is O(n), with a little extra for each pointer. You can read the formal details on Wikipedia’s linked list page.

The hidden cost most tutorials skip

On paper a linked list looks great for inserts. In real machines it is often slower than its Big O suggests. The reason is that the nodes are scattered around memory, so the computer cannot read them in one smooth sweep like it reads an array. Each pointer jump can mean a slow trip to a far part of memory. So an array often wins in practice even when the linked list looks better on paper. Always test, do not just trust the Big O.

Linked list vs array

The choice comes down to what you do most. Pick a linked list when you add and remove from the front or ends a lot, and you rarely need to jump to a random position. The pointer swaps stay cheap no matter how big the list gets.

Pick an array when you need fast access by position or you mostly read rather than insert. Arrays are also friendlier to the machine, as the box above explains. Many structures build on the linked list, including the stack and the queue, since both add and remove from the ends.

FAQ

What is a linked list in simple terms?

It is a chain of nodes where each node holds a value and a pointer to the next node. You start at the head and follow the pointers to move through the list.

What is the time complexity of a linked list?

Adding or removing at the front is O(1). Reaching an item by position is O(n), because you must follow the pointers one by one. The space is O(n).

What is the difference between a linked list and an array?

An array keeps values together with fast access by position. A linked list scatters nodes joined by pointers, with fast inserts at the front but slow access by position.

When should I use a linked list?

Use one when you add or remove from the ends often and rarely jump to a random spot. Stacks and queues use linked lists for this reason.

What is the head of a linked list?

The head is a pointer to the first node. It is your only way into the list. If you lose the head, you lose access to every node in the chain.

Are linked lists slower than arrays in practice?

Often yes, even when Big O looks equal or better. The scattered nodes make memory access slow, while arrays read smoothly. So test with real data before choosing.

So what should you remember?

A linked list is a chain of nodes, each pointing to the next. That design makes front inserts fast at O(1), but access by position slow at O(n). It is the opposite trade from an array.

Keep the hidden memory cost in mind too. The Big O can look great while the real speed lags, because the nodes are scattered. Know both sides and you will pick the right structure every time.

Now picture this. You have a linked list of 100 nodes and you want the value in the last node. How many pointers must you follow from the head to reach it?