Linked list is representation of a linear list in which elements are stored in non-contiguous memory locations. Each element can be accessed indirectly using pointers.
A linked list is stored in non-contiguous memory locations. Each element in a linked list is called a node, and each node contains two parts: the data part, which stores the actual value of the element, and the pointer part, which stores the address of the next node in the list. The first node in the list is called the head, and the last node points to null, indicating the end of the list.

The nodes are linked in one way in the above linked list, which is callout singly linked list. However, there are several variants of linked list that link the nodes in different ways.
- Doubly linked list: Each node contains a pointer to both the next and the previous node in the list. This allows for more efficient traversal in both directions, but requires more memory for the additional pointer.
- Circular linked list: The last node in the list points back to the head node, forming a circular structure. This allows for continuous traversal of the list without reaching the end.
All elements in a linked list can be of different data types, because each node contains a pointer to the next node, allowing for a flexible structure.
The time complexities of common operations in an array are as follows (
- Structural operations:
- Initialise a linked list with initial values:
; - Destroy a linked list:
; - Clear a linked list:
; - Check if the linked list is empty:
; - Get the length of the linked list:
.
- Initialise a linked list with initial values:
- Element access operations:
- Get an element by its index:
; - Search for an element by its value:
; - Traverse all elements with a specific operation on each element (such as printing):
.
- Get an element by its index:
- Element modification operations:
- Update the value of an element by its index:
; - Insert a new element at a specific index:
;- Append an element to the end of the list:
; - Prepend an element to the beginning of the list:
;
- Append an element to the end of the list:
- Delete an element from a specific index:
;- Delete the last element of the list:
; - Delete the first element of the list:
.
- Delete the last element of the list:
- Update the value of an element by its index:
- Sorting the elements:
on average for efficient algorithms like mergesort; for simpler algorithms like bubble sort and insertion sort.
Since linked lists are stored in non-contiguous memory locations, we cannot directly access an element by its index. Instead, we need to traverse the list from the head node to the desired index, which takes linear time in the worst case, resulting in a time complexity of
Pros:
- Dynamic size: Linked lists can grow and shrink in size as needed, while arrays have a fixed size.
- Memory efficiency: Linked lists can be more memory efficient than arrays when the number of elements is not known in advance, as they do not require pre-allocation of memory.
Cons:
- Slower access time: Accessing an element in a linked list takes linear time in the worst case, while accessing an element in an array takes constant time.
- More memory overhead: Each node in a linked list requires additional memory for storing the pointer to the next node, which can lead to increased memory usage compared to arrays.
C and C++ do not have a built-in linked list data type, but a linked list can be implemented using structures and pointers.
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a node in the linked list
struct Node {
int data;
struct Node* next;
};Python does not have a built-in linked list data type, but a linked list can be implemented using classes and references.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")