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.

Linked list
A linked list is much like those treasure hunts you played as a kid, where you must follow clues connected to the other to reach the final destination.

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).

Linked list diagram: Node A, Node B and Node C each hold data and a next pointer. The head points to Node A and Node C points to NULL

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.

Example of a linked list- train

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
Singly linked list: each node holds data and a pointer to the next node, and the last node points to null
  • 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-

Insertion in array vs linked list
Insertion in array vs linked list

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-

A linked list of three nodes holding 1, 2 and 3, with the head pointing to the first node and the last node pointing to NULL

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.

Linked list with nodes A and C and a new node B, ready to be inserted between them

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

Insertion step 1: the new node B points to node C


Now, Node A should point to Node B

NodeA.next — NodeB

Insertion step 2: node A points to the new node B

Doing this will place the new node in the middle of the two nodes; as we wanted.

After insertion: A points to B and B points to C

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.

Deletion step 1: node A points directly to node C, skipping node B

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

Deletion step 2: node B points to null and is removed from the list

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]

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:

TypePointers per nodeDirectionThe last node points to
Singly linked listNextForward onlyNull
Doubly linked listNext and previousBoth waysNull
Circular linked listNextForward only, round and roundThe first node
Doubly circular linked listNext and previousBoth ways, round and roundThe 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.

Singly linked list: nodes with a data field and a next pointer, one-way chain ending in null

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.

Doubly linked list: each node has a previous pointer, a data field and a next pointer

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-

Doubly linked list


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.

Circular linked list: the last node points back to the first 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.

Circular linked list


Doubly circular linked list

It combines the features of both circular linked lists and doubly linked lists.

Doubly circular linked list: each node has previous and next pointers, and the first and last nodes point to each other

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.

Doubly circular linked list


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.

Adjacency list of a graph: an array with one linked list of neighbouring vertices per vertex
Image Credits: Coding Ninjas


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-

Polynomial representation


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.

Array vs linked list

Know the differences between arrays and linked lists in detail here.

Time complexity: linked list vs array

OperationLinked listArrayDynamic array
Access by indexO(n)O(1)O(1)
Insert or delete at the beginningO(1)Not possible (fixed size)O(n)
Insert or delete at the endO(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 middleO(n) to find the spot, then O(1)Not possible (fixed size)O(n)
Extra memoryA pointer per nodeNoneSpare 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)

SituationLinked list?Why
You add or remove items at the head a lot, as in a stackYesBoth are O(1) with no shifting
You build a queue and keep head and tail pointersYesEnqueue at the tail and dequeue at the head, both O(1)
You already hold a pointer to the node you want to removeYes, a doubly linked listDeleting a known node takes a constant number of steps
You need the element at index i quicklyNoUse an array: index access is O(1)
You loop over the data often and memory is tightNoArrays 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.

ProblemApproach in one line
Reverse a linked listWalk 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 cycleMove one pointer one step and another two steps at a time. If they ever meet, the list has a cycle.
Find the middle nodeMove 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 listsUse a dummy node and a tail pointer, and keep attaching the smaller front node of the two lists.
Remove the nth node from the endStart 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).

×

Our Courses

Practice-Based Learning Tracks, Supercharged By A.I.