A linked list is a linear data structure made up of nodes connected through links. In a traditional singly linked list, every node stores a data value and a pointer to the next node. The nodes do not need to occupy consecutive memory locations; the links maintain their logical order.
Linked lists are useful when a program needs a collection whose logical size can change during execution and when insertion or deletion can be performed by changing links rather than shifting a complete block of elements. The trade-off is that linked lists do not provide the constant-time indexed access available in an array.
This page focuses on the ideas that are important for understanding linked lists: node structure, pointers, memory representation, traversal, insertion, deletion, searching, the major linked-list variants, complexity and practical applications. The examples use C because pointers and dynamic memory make the structure easy to see.
A linked list is a sequence of nodes in which each node contains data and information
needed to reach another node. In a singly linked list, the first node is reached
through a pointer called head, and the last node points to
NULL.
HEAD
|
v
+------+------+
| 10 | o---|----+
+------+------+
|
v
+------+------+
| 20 | o---|----+
+------+------+
|
v
+------+------+
| 30 | NULL |
+------+------+
The list above contains three data values. The important point is that the
sequence 10 → 20 → 30 comes from the links between nodes rather than
from numeric indexes.
A node is the basic building block of a linked list. For a singly linked list, the node contains a data field and one next pointer.
struct Node
{
int data;
struct Node *next;
};
The pointer member is what allows independently allocated nodes to form one logical sequence.
struct Node *newNode = malloc(sizeof(struct Node));
if (newNode != NULL)
{
newNode->data = 10;
newNode->next = NULL;
}
When memory is obtained with malloc(), a C program should check the
returned pointer before using it. Dynamically allocated nodes should also be
released with free() when they are no longer required.
Linked-list nodes can exist at different memory addresses. The next pointer stores the address needed to move from one node to the next.
Address Data Next 1000 10 2500 2500 20 4100 4100 30 NULL HEAD = 1000 10 --------> 20 --------> 30 --------> NULL
The addresses in this illustration are examples only. They show the important idea: the logical sequence is created by pointers, not by assuming that the nodes are adjacent in memory.
An array normally keeps its elements in contiguous storage, which makes indexed access efficient. A linked list instead follows pointers from node to node. This gives flexibility in how nodes are allocated, but it also introduces pointer storage and removes direct indexed access.
The choice between an array and a linked list depends on the operations required by the application. If frequent access by position is important, an array may be more suitable. If nodes are frequently inserted or removed at known positions, a linked structure can be useful.
| Requirement | Array | Linked List |
|---|---|---|
| Access by index | Typically O(1) | Typically O(n) |
| Insert after a known node | May require shifting | Can be O(1) |
| Delete after a known predecessor | May require shifting | Can be O(1) |
| Memory organization | Contiguous elements | Nodes connected by pointers |
| Extra per-element link | No next pointer | Required |
The phrase “insertion is O(1)” must be interpreted carefully. In a linked list, changing the links can be O(1) when the correct node or predecessor is already known. Finding that location may still require O(n) traversal.
The main types differ in the number and direction of links between nodes.
| Type | Links | Traversal | Important Property |
|---|---|---|---|
| Singly Linked List | Next | Forward | Simple and uses less link storage |
| Doubly Linked List | Previous + Next | Both directions | Supports backward movement |
| Circular Linked List | Next | Forward in a cycle | Last node points to first |
| Circular Doubly Linked List | Previous + Next | Both directions | Both ends are connected cyclically |
A singly linked list has one link per node. The link points to the next node, so the list can be traversed from the head toward the end.
HEAD | v [10 | next] -> [20 | next] -> [30 | NULL]
Traversal means visiting the nodes one by one. The following function prints every
value until it reaches NULL.
void printList(struct Node *head)
{
struct Node *current = head;
while (current != NULL)
{
printf("%d ", current->data);
current = current->next;
}
}
If the list contains 10 → 20 → 30, the output is:
10 20 30
Traversal takes O(n) time because each node may need to be visited.
Insertion adds a new node to the list. The exact pointer changes depend on where the new node is placed.
To insert a node before the current head, first make the new node point to the current head and then move the head pointer to the new node.
Before: HEAD -> 10 -> 20 -> 30 -> NULL Insert 5 After: HEAD -> 5 -> 10 -> 20 -> 30 -> NULL
newNode->next = head; head = newNode;
Once the new node already exists, this pointer update is O(1).
Suppose current points to the node containing 20. To insert 25 after
that node, the new node must first point to the old successor.
Before: 10 -> 20 -> 30 -> NULL newNode->data = 25; newNode->next = current->next; current->next = newNode; After: 10 -> 20 -> 25 -> 30 -> NULL
The two link changes are constant-time once current is known.
In a singly linked list without a tail pointer, insertion at the end normally requires traversal until the last node is found.
Before: 10 -> 20 -> 30 -> NULL Insert 40 After: 10 -> 20 -> 30 -> 40 -> NULL
Without a maintained tail pointer, finding the last node is O(n). With a suitable tail pointer, appending can be performed in O(1), provided the implementation updates that pointer correctly.
Deletion removes a node and reconnects the remaining nodes. The implementation must also release dynamically allocated memory when appropriate.
Before: HEAD -> 10 -> 20 -> 30 -> NULL head = head->next; After: HEAD -> 20 -> 30 -> NULL
After saving the old head when necessary, its memory can be released with
free(). The link update itself is O(1).
If previous points to the node before the node being deleted, the
successor can be bypassed.
10 -> 20 -> 30 -> 40 -> NULL Delete 30 10 -> 20 --------> 40 -> NULL
struct Node *temp = previous->next; previous->next = temp->next; free(temp);
The link change is O(1) after the predecessor has been found.
In a singly linked list, the predecessor of the last node is needed to disconnect the final node. Without a tail and predecessor structure, finding it normally requires O(n) traversal.
A singly linked list does not support direct indexing like an array. To search for a value, the program normally starts at the head and compares each node.
int search(struct Node *head, int target)
{
struct Node *current = head;
int position = 0;
while (current != NULL)
{
if (current->data == target)
return position;
current = current->next;
position++;
}
return -1;
}
For an unsorted list, the worst-case search time is O(n). The
function above returns the first matching position or -1 if the
value is not found.
Updating a value has two parts: reaching the required node and changing its data. If the node pointer is already available, changing the value is O(1). If the program knows only a position, it must first traverse the list.
Before: 10 -> 20 -> 30 -> NULL Change 20 to 25 After: 10 -> 25 -> 30 -> NULL
current->data = 25;
A doubly linked list stores two links in every node: one to the next node and one to the previous node.
NULL <- [prev | 10 | next] <-> [prev | 20 | next] <-> [prev | 30 | next] -> NULL
The extra previous pointer allows the program to move backward as well as forward. This is useful when navigation in both directions is part of the problem.
struct DNode
{
int data;
struct DNode *prev;
struct DNode *next;
};
In a singly linked list, moving from a node to its predecessor is not directly possible. A doubly linked list stores that relationship explicitly. The benefit is easier bidirectional navigation, while the cost is an additional pointer and more link updates during insertion and deletion.
In a circular singly linked list, the final node points back to
the first node instead of pointing to NULL.
+-----------------------+
| |
v |
10 -> 20 -> 30 -> 40 ----------+
^
|
HEAD
Because there is no NULL terminator at the end, traversal must use a condition that recognizes when the program has returned to the starting node.
struct Node *current = head;
if (current != NULL)
{
do
{
printf("%d ", current->data);
current = current->next;
}
while (current != head);
}
Circular lists are useful when the data naturally repeats in a cycle, such as turn-based or round-robin processing.
A circular doubly linked list combines two ideas: every node has previous and next links, and the structure wraps around from the last node to the first.
<-------------------+
| |
v |
10 <-> 20 <-> 30 <---+
^ |
+-------------------+
This representation supports movement in both directions while maintaining a cycle. It is more flexible than a singly linked list, but it also requires more pointer storage and more careful link maintenance.
| Operation | Singly Linked List | Condition |
|---|---|---|
| Access by position | O(n) | Nodes must be traversed from the head. |
| Search | O(n) | Unsorted list, worst case. |
| Insert at beginning | O(1) | Head is available. |
| Insert after known node | O(1) | Target node is already known. |
| Insert at end | O(n) | Without a maintained tail pointer. |
| Delete beginning | O(1) | Head is available. |
| Delete after known predecessor | O(1) | Predecessor is already known. |
| Delete end | O(n) | In a basic singly linked list. |
Complexity depends on what information the implementation maintains. For example, a tail pointer can make appending easier, while a doubly linked list can make some deletion and backward-navigation tasks more direct.
Linked lists are useful when the relationships between elements are more important than direct indexed access.
A linked list can provide dynamically allocated nodes for stack or queue implementations. The exact operations depend on which end of the list is used.
An adjacency-list representation can use linked structures to store the neighbors of each vertex. This is especially useful when a graph is sparse and the number of connections varies between vertices.
A doubly linked structure is a useful conceptual model for moving backward and forward through a sequence of states or pages.
A linked structure can represent a sequence in which the application moves from one item to another. A circular variant is useful when the sequence should repeat.
A circular linked list naturally represents repeated movement through a collection of participants or tasks.
These are examples of where the structure fits the problem; the actual implementation used by a production system may use arrays, specialized containers or other data structures depending on performance requirements.
current->data when current is NULL.The following complete example creates three nodes, connects them, prints the list, and finally releases the allocated memory.
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
int main()
{
struct Node *head = malloc(sizeof(struct Node));
struct Node *second = malloc(sizeof(struct Node));
struct Node *third = malloc(sizeof(struct Node));
if (head == NULL || second == NULL || third == NULL)
{
free(head);
free(second);
free(third);
return 1;
}
head->data = 10;
head->next = second;
second->data = 20;
second->next = third;
third->data = 30;
third->next = NULL;
struct Node *current = head;
while (current != NULL)
{
printf("%d ", current->data);
current = current->next;
}
free(third);
free(second);
free(head);
return 0;
}
Output:
10 20 30
This small program demonstrates the complete lifecycle of a simple list: allocation, initialization, connection, traversal and cleanup.
| Feature | Array | Linked List |
|---|---|---|
| Access | Direct indexing | Sequential traversal |
| Typical indexed access | O(1) | O(n) |
| Insertion at beginning | May require shifting | O(1) with head pointer |
| Deletion after known predecessor | May require shifting | O(1) |
| Extra link fields | No | Yes |
| Memory layout | Contiguous | Nodes connected through links |
A linked list is a sequence of nodes connected through links. A singly linked list stores a data value and a pointer to the next node.
A node is one element of a linked list. In a singly linked list it contains data and a next pointer.
The head is the pointer or reference used to identify the first node of the list.
Nodes are reached by following links, so the program normally has to traverse from the head until it reaches the required position.
For an unsorted linked list, the worst-case search time is O(n).
Insertion can be O(1) when the correct insertion location, such as a predecessor node, is already known. Finding that location may require O(n).
A singly linked list has a next link, while a doubly linked list has both previous and next links.
In a circular list, the final node links back to the first node instead of storing NULL as its next link.
Dynamically allocated nodes must be checked when created and released when no longer required. Otherwise the program can encounter allocation failures or memory leaks.
A linked-list implementation can impose a limit, but the defining feature of the usual dynamic implementation is that nodes are allocated individually as needed.
A linked list represents a sequence through connections between nodes rather than through array indexes. Its main strengths are flexible node allocation and the ability to insert or remove nodes by changing links when the relevant location is known. Its main trade-offs are sequential access, pointer overhead and greater memory-management complexity.
Students should be comfortable with the node structure, head pointer, traversal, insertion, deletion and searching before moving to doubly and circular linked lists. These concepts provide a strong foundation for studying stacks, queues, graphs and other data structures.