Linked List

In Turkish: Bağlı Liste

Updated September 30, 20263 min read

In short

A linked list is a data structure that stores items in separate nodes, where each node holds a value and a reference to the next node in the chain.

What is a linked list?

A linked list is a linear data structure made of nodes. Each node stores a value plus a reference, or pointer, to the next node, and the list itself only needs to remember the first node, called the head. The last node points to nothing, which is written as null in JavaScript or None in Python.

Because the nodes don't have to sit next to each other in memory, adding or removing an item at the front takes O(1) time: you only update a reference or two instead of shifting other items. The trade-off is access by position. To reach the 500th item you must start at the head and follow 499 links, so indexing and searching take O(n) time. A doubly linked list also stores a reference to the previous node, which lets you walk backward and remove a node you already hold in O(1).

Think of a treasure hunt where each clue tells you where to find the next one: you can't jump straight to clue ten without reading the nine before it. Linked lists are used as building blocks for stacks, queues, and the collision chains inside some hash tables. They also appear in LRU caches (caches that evict the least recently used entry first), where a doubly linked list keeps entries in order of use.

Linked lists are often confused with arrays. An array stores items in one continuous block of memory, so reading any index is O(1), but inserting in the middle means shifting everything after it. Despite the name, a Python list and a JavaScript Array are dynamic arrays, not linked lists, and in everyday code they are usually faster because their items sit close together in memory, which suits the CPU cache.

At a glance

Inserting at the front only re-points two references. No other node moves.

Key takeaways

Each node holds a value and a reference to the next node.
Inserting or removing at the head takes O(1) time.
Accessing an item by index or searching takes O(n) time, because you must walk the chain.
A doubly linked list also links each node to the previous one, so it can be walked in both directions.
Python lists and JavaScript arrays are dynamic arrays, not linked lists.

Example

Building and walking a singly linked listpython

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node  # the next node, or None at the end

# Build 1 -> 2 -> 3, then insert 0 at the front in O(1) time
head = Node(1, Node(2, Node(3)))
head = Node(0, head)

# Visiting the items means following the links one by one: O(n)
node = head
while node is not None:
    print(node.value)  # 0, 1, 2, 3
    node = node.next

Readers ask

When should I use a linked list instead of an array?

Use a linked list when you often insert or remove items at the ends, or next to nodes you already hold a reference to, and rarely need to jump to an index. For most everyday tasks, an array or your language's built-in list is simpler and faster.

What is the difference between a singly and a doubly linked list?

In a singly linked list each node points only to the next node. In a doubly linked list each node also points to the previous one, which uses more memory but lets you walk backward and delete a known node in O(1).

Is inserting into a linked list O(1) or O(n)?

Linking in a new node is O(1) once you already have a reference to the node before it, or when you insert at the head. Finding an arbitrary position first takes O(n), so inserting at a given index is O(n) overall.

Often compared

Array vs Linked ListAn array keeps elements side by side in memory, so any item is read instantly by index; a linked list chains nodes with pointers: cheap inserts, slow lookups.