Linked List in Data Structure: Types, Operations, Examples
A linked list stores data in nodes joined by pointers. Learn the four types, insertion, deletion, search and sorting with tested Python and JavaScript, time complexity against arrays, and five classic interview problems.
A linked list is a type of data structure in which elements are connected to each other through links or pointers. Each element (called a node) has two parts - the data and a link pointing to the next node.
Definition: A linked list is a type of linear data structure that occurs when the data elements do not reside in consecutive memory regions. A linked list's components are connected using pointers (entities that lead to the next member).

Okay! So, it’s highly likely that many of you didn’t get that. And we don’t want that. Our aim is to put it out in a layman's way so even beginners could understand what exactly is a linked list.
So, let’s break it down -
“A type of data structure”
What is a data structure?
A data structure is how we store and organize data so we can perform different operations on it easily.
Does it have types?
Yes, data structures are of different types depending on what form we need the data to be stored in, and how we perform any operation on it.
A linked list stores data in a linear sequence (How data is stored) using pointers, and these pointers allow us to add or remove elements without restructuring the whole thing (how are we operating on it).
An array is one similar data structure that has elements in a linear order, the only difference being - the array uses indices to assign positions while a linked list uses links that point to the next element/node. (Yes! We will understand the difference in detail later).
Here’s a better way to understand a linked list-
Think of a train! It has numerous bogies connected to each other. If we have to add a new bogie X somewhere in the middle of two bogies, say L and R, we can simply disconnect L and R and add the new one in the middle. Now L will be connected to X, and X will be connected to R.
This kind of insertion wouldn’t be possible in an array-like setup where you’d have to shift all bogies to make space for a new one.
You must have played those treasure hunt games where you have to solve a puzzle to get the clue that directs you to the next steps in the hunt and so on.
A linked list works in a similar fashion where a node has the reference link to the next node in the list.
Why do we need linked lists?
We need linked lists for the various advantages listed below,
- A linked list is a linear data structure that dynamically stores a group of data segments.
- These data segments are represented by nodes, which are connected by links or pointers.
- Each node has information stored in a linked list and a reference to the location of its subsequent node.
- The final node has null in its second field, which marks the end of the list

- A linked list's size can be increased or decreased as needed.
- It allocates memory only for the nodes you create, but every node also stores a pointer, so it uses more memory per element than an array.
The question is fairly simple - If we have a linear data structure in arrays, why do we even need linked lists?
Because, in an array, it’s much more difficult to insert or add an element. Even in a dynamic array, all the other elements would have to shift in order to make space if we have to add an element at the start of the index.
Also, there is a possibility that you’d need to allocate more memory space to the array before inserting an element.
This is where linked lists find their significance-

Remember, a linked list maintains its order using pointers, so inserting or removing a node only means changing a couple of pointers. (You still have to walk the list to find the position, unless you already hold the node.)
Since the position of a node is stored in the pointer of the previous node, the nodes don’t necessarily have to be consecutive. They can be stored anywhere in memory and still be connected through the links.
Representation of linked lists
We can visualize a linked list as a chain of nodes; where every node contains a data field and a reference link to the next node in the list.
The first node in the sequence is termed as ‘head’. And we can identify the last node as the one which points to ‘Null’.
Each node consists of -
- A data field
- Reference to the next node
Structure of a node in C language-
struct node
{
int data;
struct node *next;
};Let’s make a simple linked list with three items to understand this better.
/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* Assign data values */
one->data = 1;
two->data = 2;
three->data=3;
/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;
/* Save address of first node in head */
head = one;Here's how it'll look-
The same node in Python, with the three-item list built and walked from the head. Reading every node from the head to the null at the end is called traversal:
class Node:
def __init__(self, value):
self.value = value
self.next = None # pointer to the next node (None marks the end)
head = Node(1) # build the list 1 -> 2 -> 3
head.next = Node(2)
head.next.next = Node(3)
def to_list(head): # traversal: visit every node, starting at the head
values, node = [], head
while node:
values.append(node.value)
node = node.next
return values
print(to_list(head)) # [1, 2, 3]
Operations in a linked list
Following are the various operations to perform the required action on a linked list:
- Traversal - To access each element of the linked list.
- Insertion - To add/insert a new node to the list.
- Deletion - To remove an existing node from the list.
- Search - To find a node in the list.
- Sort - To sort the nodes.
Now, let’s look at each of these operations separately-
Insertion
It’s more than a one-step activity. First, we create a node with the same structure and specify the location where we’ll insert it.

Suppose, we have to insert Node B between the two nodes A and C.
The new Node B will point to Node C.
NodeB.next - Node C
Now, Node A should point to Node B
NodeA.next — NodeB

Doing this will place the new node in the middle of the two nodes; as we wanted.
If we have to insert a node at the beginning of the list; the new node should point to the Head (First).
Similarly, if we have to insert a node at the end; the last node should be made to point to the new node, and the new node should be pointing to ‘Null’.
In Python, building on the Node class above. Inserting at the head or after a node you already hold takes a constant number of steps, while inserting at the tail means walking to the end first:
def push_front(head, value): # insert at the head: O(1)
node = Node(value)
node.next = head # the new node points at the old first node
return node # and becomes the new head
def insert_after(prev_node, value): # insert after a node you already hold: O(1)
node = Node(value)
node.next = prev_node.next # step 1: B points to C
prev_node.next = node # step 2: A points to B
def append(head, value): # insert at the tail: O(n), because we walk to the end
node = Node(value)
if head is None:
return node
last = head
while last.next:
last = last.next
last.next = node
return head
head = push_front(head, 0)
insert_after(head.next, 15) # after the node holding 1
head = append(head, 4)
print(to_list(head)) # [0, 1, 15, 2, 3, 4]
Deletion
Just like insertion, deletion is also a multi-step process.
First, we track the node to be removed, by using searching algorithms.
Once, it’s located, we’ll change the reference link of the previous node to the node that is next to our target node.
In this case, Node A will now point to Node C.
NodeA.next - NodeC
Once, the link pointing to the target node is removed, we'll also remove the link from Node B to Node C.
Now, Node B should point to ‘Null’.
Node B.next — Null
Now we can either keep it in memory or deallocate memory and eliminate Node B.
To delete a node from the beginning, we’ll simply direct the ‘head’ to the second node in the list.
In case of deleting the last node, the second last element will be directed to point to Null.
In Python, deleting the first node that holds a given value. The loop is the search, and the single line that skips the node is the deletion:
def delete(head, value): # remove the first node holding value: O(n)
if head is None:
return None
if head.value == value: # deleting the head: just move the head
return head.next
node = head
while node.next:
if node.next.value == value:
node.next = node.next.next # A now points to C, so B is skipped
return head
node = node.next
return head
head = delete(head, 15)
print(to_list(head)) # [0, 1, 2, 3, 4]
Search
We search for a node on a linked list using a loop. Suppose, we have to find Node X on a list.
- First, we’ll assign the ‘Head’ as the ‘Current’ node.
- Then, we’ll use a loop until the ‘Current’ node is ‘Null’ since the last element points to ‘Null’.
- In each repetition, we’ll check if the key of the node is equal to ‘Node X’. If the key matches this item, return true, else return false.
In Python, returning the index of the match (or -1) instead of true or false:
def search(head, value): # index of the first match, or -1: O(n)
node, index = head, 0
while node:
if node.value == value:
return index
node = node.next
index += 1
return -1
print(search(head, 2), search(head, 9)) # 2 -1
Search takes O(n) time, because in the worst case it looks at every node. Unlike a sorted array, a linked list cannot use binary search, since it has no way to jump to the middle.
Sort
Simple sorts such as bubble sort and insertion sort work on a linked list, but they take O(n²) time. Wikipedia describes merge sort as often the best choice for sorting a linked list: it needs only sequential access, takes O(n log n) time, and merging two sorted lists is just a matter of relinking nodes.
Here is merge sort on the 7, 5, 4, 6 example, in Python:
def merge(a, b): # merge two sorted lists into one sorted list
dummy = Node(None)
tail = dummy
while a and b:
if a.value <= b.value:
tail.next = a
a = a.next
else:
tail.next = b
b = b.next
tail = tail.next
tail.next = a if a else b
return dummy.next
def merge_sort(head): # O(n log n)
if head is None or head.next is None:
return head
slow, fast = head, head.next # find the middle with two pointers
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = None # cut the list in two
return merge(merge_sort(head), merge_sort(second))
unsorted = None
for v in [7, 5, 4, 6]:
unsorted = append(unsorted, v)
print(to_list(unsorted)) # [7, 5, 4, 6]
print(to_list(merge_sort(unsorted))) # [4, 5, 6, 7]
The same operations in JavaScript
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() { this.head = null; }
pushFront(value) { // O(1)
const node = new Node(value);
node.next = this.head;
this.head = node;
}
append(value) { // O(n): walk to the last node
const node = new Node(value);
if (!this.head) { this.head = node; return; }
let last = this.head;
while (last.next) last = last.next;
last.next = node;
}
delete(value) { // O(n): remove the first node holding value
if (!this.head) return false;
if (this.head.value === value) { this.head = this.head.next; return true; }
let node = this.head;
while (node.next) {
if (node.next.value === value) { node.next = node.next.next; return true; }
node = node.next;
}
return false;
}
toArray() {
const out = [];
for (let node = this.head; node; node = node.next) out.push(node.value);
return out;
}
}
const list = new LinkedList();
list.append(2);
list.append(3);
list.pushFront(1);
console.log(list.toArray().join(" ")); // 1 2 3
list.delete(2);
console.log(list.toArray().join(" ")); // 1 3
Types of linked lists
Here is how the four types differ before the details:
| Type | Pointers per node | Direction | The last node points to |
|---|---|---|---|
| Singly linked list | Next | Forward only | Null |
| Doubly linked list | Next and previous | Both ways | Null |
| Circular linked list | Next | Forward only, round and round | The first node |
| Doubly circular linked list | Next and previous | Both ways, round and round | The first node (and the first points back to the last) |
There are 4 key types of linked lists-
Singly linked list
Till now we have talked about singly linked lists. It is the most commonly used linked list containing two parts- the data field, and the reference pointer to the next element.
It is the most basic linked list, with each node containing some data and a reference to the subsequent node of the same data type.

In a singly linked list, only forward traversal is possible; as it has only one pointer that points to the next node. For the same reason, it is also termed a ‘one-way chain’.
Doubly linked list
A doubly linked list contains two pointers- one pointing forward and the other one pointing back to the previous node.
A doubly linked list, also known as a two-way linked list, is an advanced version of linked list that carries a pointer to both the following and earlier nodes in the chain.

That was simple guessing by the name, wasn’t it?
So in total, a doubly-linked list contains three parts, including, of course, the data part.
Let’s say we have three nodes - 1,2, and 3 with addresses A, B, and C respectively. They will be represented in a doubly-linked list as-
The front node has a ‘Null’ value in the address part which shows the previous node’s address.
A doubly-linked list allows us to traverse in both directions.
Circular linked list
It’s a type of linked list in which the very last node is connected to the first node, thus forming a circular loop.
A circular linked list is one in which the end node carries a pointer to the list's initial node.

A circular linked list has no null at the end, so you can keep walking around the loop. In a singly circular list you can only go forward; a doubly circular list (below) lets you go both ways.
Doubly circular linked list
It combines the features of both circular linked lists and doubly linked lists.

The nodes have two pointers for the next and previous node, and the last node points to the first node making it a circular doubly linked list.
This type of linked list doesn’t have ‘Null’ in any of the nodes. Both the first and the last nodes contain addresses of each other.
Because it has no end and can be walked in both directions, a circular doubly linked list reaches the last node from the first in one step.
Applications of linked lists
In programming
Implementing stacks and queues
Linked lists are used to implement the stack data structure and the queue data structure. How?
As a stack follows the Last In First Out principle, every PUSH operation will be INSERT_IN_BEGINNING and every POP operation will be DELETE_IN_BEGINNING in the linked list.
And, in the First In First Out structure of a queue, we’ll maintain two pointers - the head pointing to the start of the linked list, and the tail pointing to the end of the linked list. Every PUSH operation will be INSERT_IN_END and every POP operation will be DELETE_IN_BEGINNING.
Implementing graphs
The graph data structure can also be implemented using the adjacency list representation.
It can be depicted as an array of linked lists where lists store the adjacent vertices.
Polynomial manipulation
A polynomial, in mathematics, is a collection of different terms, comprising coefficients, variables, and exponents. They’re not supported as a data type by most languages. However, linked lists can represent polynomials with ease.
How?
Each polynomial term takes up a node in the linked list. It is also made sure that the terms are arranged in the decreasing order of exponents for better efficiency.
Each node would consist of 3 parts-
Let’s say we have-
4x^4 + 11x^3 - 2x^2 + 1
Here, 4, 11, -2 and 1 are the coefficients, and 4, 3, 2 and 0 are the exponents.
To represent 4 terms, we’ll need a linked list with 4 nodes.
Representing polynomials this way allows us to perform various mathematical operations easily.
Dynamic memory allocation
As we know that nodes of a linked list are not stored in contiguous memory locations, but instead created dynamically at runtime. So, linked lists can be helpful in dynamic memory allocation where we don't know the exact number of elements we’re going to use.
Hash tables (chaining)
When two keys land in the same bucket of a hash map, the bucket can hold them as a linked list. This technique is called chaining.
In real life
Having a significant role in programming, linked lists certainly have many real-life applications. Let's look at a few of them -
In web browsers
While moving through web pages, you have both options available - to either move to the next page or the previous page. A doubly linked list is a natural way to model this.
In music players
Similarly, we can switch to the next and the previous song in a music player using links between songs. We can also play songs either from the starting or the end of the playlist.
In image viewer
The next and the previous photos are linked, and we can easily access them by using the previous and next buttons.
In operating systems
An operating system can keep its list of processes in a doubly linked list, which makes it cheap to move a process from one queue to another.
In Multiplayer games
A circular linked list suits turn-taking: after the last player, the turn goes back to the first, so a game can cycle through its players in a loop.
Linked list vs Array
Arrays can be considered the default type in almost all programming languages, due to their wide usage.
But there are many use-cases where using arrays isn’t the ideal solution. Like when we don’t know the number of elements to be stored, or when we know that we’d need to do a lot of insertions and deletions later. In such cases, we need an advanced data structure like a linked list. Of course, just like arrays, linked lists have their own limitations too.
With that being said, let’s look at the key differences between an array and a linked list-
Accessing an element
Arrays support random access which means you can access any element directly using their index, like arr[0] for accessing the 1st element, arr[3] for the 4th element, and so on.
Whereas, only sequential access is possible in a linked list; you have to sequentially traverse the entire list up to that element.
Insertion and Deletion
Due to the fixed and consecutive memory locations in an array, insertion and deletion operations take more time.
Meanwhile, new elements can be stored anywhere in the memory of a linked list. We just need to store the address of the new node in the previous node, so that it points to the newly added node.
Memory Allocation
Memory is allocated while declaring the array, at compile time. It’s also called static memory allocation.
Whereas, linked lists support dynamic memory allocation. Memory can be allocated at runtime while adding a new node.

Know the differences between arrays and linked lists in detail here.
Time complexity: linked list vs array
| Operation | Linked list | Array | Dynamic array |
|---|---|---|---|
| Access by index | O(n) | O(1) | O(1) |
| Insert or delete at the beginning | O(1) | Not possible (fixed size) | O(n) |
| Insert or delete at the end | O(1) if you keep a pointer to the last node, otherwise O(n) | Not possible (fixed size) | O(1) amortized |
| Insert or delete in the middle | O(n) to find the spot, then O(1) | Not possible (fixed size) | O(n) |
| Extra memory | A pointer per node | None | Spare capacity |
The table follows the comparison in Wikipedia's linked list article. Two details are worth remembering. Inserting into a linked list is O(1) only once you hold the node: finding the position still takes a walk from the head. And arrays have better cache locality, because their elements sit side by side in memory.
When to use a linked list (and when not to)
| Situation | Linked list? | Why |
|---|---|---|
| You add or remove items at the head a lot, as in a stack | Yes | Both are O(1) with no shifting |
| You build a queue and keep head and tail pointers | Yes | Enqueue at the tail and dequeue at the head, both O(1) |
| You already hold a pointer to the node you want to remove | Yes, a doubly linked list | Deleting a known node takes a constant number of steps |
| You need the element at index i quickly | No | Use an array: index access is O(1) |
| You loop over the data often and memory is tight | No | Arrays are compact and cache friendly, and a linked list adds a pointer per element |
For a longer comparison, see array vs linked list: when to use what.
Linked list interview problems
Most linked list questions are solved with one of two tricks: a dummy node in front of the list, or two pointers moving at different speeds.
| Problem | Approach in one line |
|---|---|
| Reverse a linked list | Walk the list and point each node back at the one before it, keeping the next node in a variable first (or recurse, see the recursion guide). |
| Detect a cycle | Move one pointer one step and another two steps at a time. If they ever meet, the list has a cycle. |
| Find the middle node | Move a fast pointer two steps for every one step of a slow pointer. When the fast one reaches the end, the slow one is in the middle. |
| Merge two sorted lists | Use a dummy node and a tail pointer, and keep attaching the smaller front node of the two lists. |
| Remove the nth node from the end | Start two pointers n nodes apart and move both. When the front one reaches the end, the back one is just before the node to remove. |
The first one in Python, using the to_list helper from above:
def reverse(head):
prev = None
current = head
while current:
nxt = current.next # remember the rest of the list
current.next = prev # point this node backwards
prev = current # step forward
current = nxt
return prev # the old tail is the new head
print(to_list(reverse(head))) # [4, 3, 2, 1, 0]
Final thoughts
A linked list trades fast random access for cheap insertion and deletion. Every node stores its data and a pointer to the next node, so growing or shrinking the list means changing a few pointers. The same idea sits underneath stacks, queues, hash table chains and graph adjacency lists.
If you want to learn data structures and algorithms from scratch, this article is a good place to start. After linked lists, a natural next step is the tree data structure, where each node can point to more than one next node.
Cheers!
FAQs
What is a linked list in data structure?
A linked list is a linear data structure made of nodes. Each node stores a value and a pointer to the next node, and the last node points to null. The nodes do not need to sit next to each other in memory.
How do linked lists store information?
Each node holds the data and a reference to the next node, and the list itself is just a pointer to the first node, the head. The order comes from the pointers, not from where the nodes are in memory, so the list grows one node at a time.
What is the difference between an array and a linked list?
An array stores elements side by side and reaches any index in O(1) time, but inserting in the middle means shifting elements. A linked list reaches the nth element in O(n) time, but inserting or deleting a node you hold only changes pointers.
What are the types of linked lists?
There are four: singly linked (one next pointer), doubly linked (next and previous pointers), circular (the last node points to the first) and doubly circular (both ideas combined). Each is shown with a diagram above.
What is the time complexity of linked list operations?
Access and search take O(n). Insertion and deletion at the head take O(1), and at the tail O(1) if you keep a tail pointer. Insertion or deletion after a node you already hold is O(1), but finding that node takes O(n).