Overview
A linked list is a linear data structure in which elements, called nodes, are stored in a sequence, with each node containing a data field and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, allowing efficient insertion and deletion of elements at arbitrary positions. They form the foundation for more complex data structures such as stacks, queues, and adjacency lists in graph theory. Because nodes are linked by pointers or references, the list can grow or shrink dynamically without the overhead of resizing.
1 Fundamental concepts
1.1 Node structure
Every node in a linked list consists of two parts: a data field that holds the actual value (of any valid type) and one or more link fields that store references to other nodes. In a singly linked list, each node has a single link pointing to the next node; in a doubly linked list, each node contains two links, one to the previous and one to the next node. The data field can be a primitive type, a composite object, or even another data structure. Node objects are typically allocated dynamically.
1.2 Head pointer and tail pointer
The head pointer is a reference that points to the first node of the linked list. It is essential for accessing the list; if the list is empty, the head pointer is null. The tail pointer, commonly used in singly and doubly linked lists, points to the last node. Maintaining a tail pointer enables constant‑time insertion at the end of the list. In circular linked lists, the tail pointer may point back to the head, but the concept of a designated last node remains.
1.3 Singly linked lists
A singly linked list is the simplest form, where each node contains a single link to the next node. Traversal proceeds only in one direction, from head to tail. Insertions and deletions at the head are constant‑time, but operations at the tail require a full traversal unless a tail pointer is maintained. Singly linked lists are memory‑efficient because each node stores only one link.
1.4 Doubly linked lists
In a doubly linked list, each node has two link fields: one to the previous node and one to the next node. This allows bidirectional traversal and simplifies certain operations, such as deletion of a node given only its reference. The extra link increases memory overhead but enables constant‑time removal of a node when its predecessor is known. Many standard library implementations (e.g., Java’s LinkedList) use doubly linked lists.
1.5 Circular linked lists
A circular linked list is a variation in which the last node’s link points back to the head (or, in a doubly circular list, also the head’s previous link points to the tail). This creates a closed loop, allowing traversal to continue indefinitely. Circular lists are useful for round‑robin scheduling and other cyclic data structures. They can be either singly or doubly linked.
2 Operations
2.1 Traversal
Traversal involves visiting each node in the list sequentially, starting from the head and following the next link until a null (or, for circular lists, the starting node again) is encountered. During traversal, the data at each node can be read or modified. Traversal time is O(n), where n is the number of nodes.
2.2 Insertion
Insertion adds a new node to the list. The operation typically requires updating the links of the predecessor and the new node. Depending on the position, the time complexity varies.
2.2.1 Insert at head
Inserting a node at the head involves setting the new node’s next link to the current head, then updating the head pointer to the new node. This is an O(1) operation.
2.2.2 Insert at tail
Insertion at the tail is O(1) if a tail pointer is maintained. The new node’s next is set to null, the current tail’s next is set to the new node, and the tail pointer is updated. Without a tail pointer, the operation takes O(n) to traverse to the end.
2.2.3 Insert at a given position
Insertion at an arbitrary index (or after a specific node) requires traversing to the predecessor node. The new node’s next points to the successor, and the predecessor’s next points to the new node. Time complexity is O(n) for singly linked lists (to find the predecessor) but O(1) if a reference to the predecessor is already known.
2.3 Deletion
Deletion removes a node from the list and adjusts the surrounding links.
2.3.1 Delete from head
Removing the head node is O(1). The head pointer is updated to point to the second node, and the old head is freed or left for garbage collection.
2.3.2 Delete from tail
Deleting the tail node requires locating the second‑to‑last node. In a singly linked list, this is O(n) because the entire list must be traversed. With a doubly linked list, the operation can be O(1) if the tail node’s previous link is followed directly.
2.3.3 Delete a specific node
Given a direct reference to the node to be deleted, deletion is O(1) in a doubly linked list (by updating the previous node’s next and the next node’s previous). In a singly linked list, one must locate the predecessor, incurring O(n) time.
2.4 Searching
Searching for a value involves traversing the list and comparing each node’s data. The average and worst‑case time complexity is O(n). In sorted linked lists, searching can be improved with skip lists (a related structure), but plain linked lists do not support binary search.
2.5 Reversal
Reversing a linked list changes the direction of links so that the original head becomes the tail. For singly linked lists, iterative reversal uses three pointers (previous, current, next). Recursive reversal is also common. Doubly linked lists require swapping both next and previous links. Time complexity is O(n), and space complexity is O(1) for iterative methods.
3 Variants
3.1 Xor linked lists (memory‑efficient doubly linked list)
An XOR linked list stores the XOR of the addresses of the previous and next nodes in each node’s link field. This ensures that a doubly linked list can be implemented with only one link per node, reducing memory overhead. However, traversal requires keeping track of the previously visited node to compute the next one. Xor linked lists are less common in modern practice because they are not compatible with garbage‑collected languages and are error‑prone.
3.2 Self‑organizing linked list
A self‑organizing linked list rearranges nodes based on access patterns to improve average search time. Common heuristics include move‑to‑front (move accessed node to the head) and transpose (swap with predecessor). These structures are used in caches and frequency‑based applications.
3.3 Sparse linked list
A sparse linked list represents a sparse matrix or array by storing only non‑zero elements as nodes. Each node typically holds the row, column, and value, along with links for row and column traversal (similar to orthogonal lists). This variant reduces memory usage for datasets with many empty entries.
3.4 Unrolled linked list
An unrolled linked list stores a small array of elements in each node to reduce pointer overhead and improve cache locality. Each node has a fixed‑capacity array and a link to the next node. When a node becomes full, it is split into two. This hybrid structure provides better performance for insertion and deletion at arbitrary positions compared to a plain linked list.
4 Implementations
4.1 In C
In C, linked lists are implemented using struct nodes with an explicit pointer member (e.g., struct Node { int data; struct Node* next; };). Functions manage dynamic memory allocation (malloc, free) and pointer manipulation. Typical operations include insert, delete, and print. C does not provide built‑in garbage collection, so manual memory management is required.
4.2 In C++
C++ offers both manual implementation using classes and the Standard Template Library (STL) container std::list (doubly linked) and std::forward_list (singly linked). Manual implementations often use templates for type flexibility, smart pointers (std::unique_ptr, std::shared_ptr) to simplify memory management, and iterators for traversal.
4.3 In Java
Java provides java.util.LinkedList (doubly linked) as part of the Collections Framework. It implements List and Deque interfaces, supporting insertion, deletion, and iteration. Manual implementations define a static inner Node class with generics. The JVM’s garbage collector handles node deallocation automatically.
4.4 In Python
Python does not have a built‑in linked list class. Manual implementation uses a custom Node class with a next attribute (and optionally prev). Although Python’s list is a dynamic array that may be preferred for many tasks, linked lists can be useful for educational purposes or specific algorithms (e.g., reversing a list in place).
4.5 In Rust
Rust’s ownership model makes linked list implementation non‑trivial. The standard library provides std::collections::LinkedList (doubly linked). Manual implementations often use Box (for heap allocation) and Option<Box<Node>> for the next link. Rust’s borrow checker enforces safe pointer usage, preventing common bugs like dangling pointers.
5 Performance analysis
5.1 Time complexity of basic operations
The table below summarises typical time complexities for a singly linked list (with optional tail pointer):
- Access (by index): O(n)
- Search: O(n)
- Insertion at head: O(1)
- Insertion at tail: O(1) with tail pointer, O(n) without
- Insertion at arbitrary position: O(n) (search for predecessor)
- Deletion at head: O(1)
- Deletion at tail: O(n) singly, O(1) doubly
- Deletion of a given node: O(1) doubly, O(n) singly
- Reversal: O(n)
5.2 Space complexity
Each node in a singly linked list stores one pointer and data – overhead of one pointer per element. Doubly linked lists require two pointers per node. The overall space complexity is O(n) for all variants. The constant factor depends on the size of the data and link fields; small data types suffer proportionally larger overhead.
5.3 Comparison with arrays
5.3.1 Access speed
Arrays provide O(1) random access by index, whereas linked lists require O(n) traversal. For frequent random access, arrays are far superior. Linked lists are preferred when sequential access is the norm.
5.3.2 Insertion/deletion efficiency
Insertion and deletion at arbitrary positions in an array are O(n) due to shifting elements. Linked lists achieve O(1) at the head and O(n) at arbitrary positions (search cost), but the actual pointer updates are constant‑time once the position is known. For frequent modifications at the ends or near a known node, linked lists outperform arrays.
5.3.3 Memory fragmentation
Arrays occupy a contiguous block of memory, which can lead to allocation failures if a large block is unavailable. Linked lists allocate nodes individually, causing fragmentation but allowing the use of scattered free memory. However, linked list nodes are small and may degrade cache performance due to lack of spatial locality.
6 Applications
6.1 Implementation of stacks and queues
Singly linked lists are commonly used to implement stacks (LIFO) with O(1) push/pop at the head. Queues (FIFO) are efficiently implemented with a linked list and both head and tail pointers, enabling O(1) enqueue and dequeue. Standard library containers often use linked lists for these structures.
6.2 Dynamic memory management (free lists)
Operating systems and memory allocators maintain free lists as linked lists of available memory blocks. When a process requests memory, the allocator traverses the free list to find a suitable block, splits it, and updates the list. Deallocation returns blocks to the free list.
6.3 Adjacency lists in graphs
In graph representations, each vertex stores a linked list of its adjacent neighbors (edges). This adjacency‑list format saves space for sparse graphs compared to an adjacency matrix. Operations like iterating over a vertex’s edges are O(degree), and insertions of new edges are O(1) if the list is unsorted.
6.4 Polynomial representation
Polynomials can be represented as linked lists where each node stores a coefficient, an exponent, and a link to the next term. Operations such as addition and multiplication are performed by traversing the lists and combining like terms. This representation avoids storing zero terms.
6.5 Undo functionality in software
Many applications (text editors, image editors) use a linked list of actions to implement undo/redo. Each node contains the state or command. Traversal backward and forward is natural with a doubly linked list. Inserting new actions at the current position and discarding the tail are efficient.
7 Common problems and solutions
7.1 Detecting cycles (Floyd’s cycle detection)
7.1.1 Tortoise and hare algorithm
Floyd’s algorithm uses two pointers moving at different speeds: the tortoise moves one node per step, the hare moves two. If the list has a cycle, the pointers will eventually meet inside the cycle. The algorithm detects cycles in O(n) time and uses O(1) space. After detection, the start of the cycle can be found by resetting one pointer to the head and moving both at the same speed until they meet again.
7.1.2 Handling circular lists
A circular linked list (where the tail points to the head) is a special case of a cycle. Floyd’s algorithm still works; detecting that the hare reaches the head again (or that the next pointer of a known tail points to head) is simpler. When implementing, care must be taken to avoid infinite loops during traversal.
7.2 Finding the middle node
The middle node of a singly linked list can be found using the tortoise‑and‑hare technique: the slow pointer moves one step, the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer is at the middle element. This is O(n) and O(1) space.
7.3 Merging two sorted linked lists
Given two sorted singly linked lists, they can be merged into one sorted list by comparing the head nodes repeatedly. A dummy head node simplifies the process. The merge is stable if the original relative order of equal elements is preserved. Time complexity is O(n+m), space O(1) (iterative) or O(n+m) (recursive stack).
7.4 Intersection point of two linked lists
Two singly linked lists may intersect at a common node. The problem is to find that intersection. One solution computes the lengths of both lists, advances the longer list by the difference, then moves both pointers in tandem until they meet. Another approach uses a hash set of nodes. Time is O(n+m), space O(1) for the length method, O(n) for the hash set.
7.5 Reverse a linked list in groups
Reversing a linked list in groups of size k means reversing the first k nodes, then the next k, and so on. If the last group has fewer than k nodes, it may be left as is (depending on the problem). This can be done recursively or iteratively with a dummy head. Time complexity is O(n), space O(n/k) for recursion stack or O(1) for iterative.
8 History and evolution
8.1 Early use in LISP (1950s)
The linked list concept originated with the LISP programming language developed by John McCarthy in the late 1950s. LISP used cons cells (a pair of pointers) as its fundamental building block, forming singly linked lists for symbolic computation. This design heavily influenced early data structure theory and functional programming.
8.2 Development of typed and safe linked lists
In the 1970s and 1980s, as typed languages such as Pascal and C became popular, linked list implementations became more structured with explicit type declarations. The introduction of generics (templates) in C++ (1990s) and Java (2004) allowed type‑safe linked lists without manual casting. Today, nearly all modern languages provide standard library linked‑list containers with built‑in safety features.
8.3 Modern garbage‑collected implementations
With the rise of garbage‑collected languages (Java, C#, Python, Go), linked list memory management is automated. Developers no longer need to manually free nodes, reducing memory‑leak risks. However, the overhead of garbage collection can affect performance in latency‑sensitive systems. Despite these changes, the underlying logical structure of linked lists remains the same as in the 1960s.