Introduction to Linked List Data Structure
Linked list data structure are a collection of data elements in linear form.
What is Linked List Data Structure?
A linked list is a linear data structure used for storing collections of data in the form of
nodes. Each node in a linked list store two elements – data and address of next node.
Properties of Linked List
The linked list starts with a HEAD which denotes the starting point or the memory location of first
node.
Linked list ends with the last node pointing to NULL value.
Unlike array the elements are not stored in contiguous memory locations, but are stored in
random location.
Random allocation of memory location helps to add any number of elements to the lined list.
Linked List does not waste memory space.
Representation of Linked List
A linked list is a chain of nodes, and each node has the following parts:
Data – Stores the information
Next – Stores the address to next node
Creating a Linked List
In C language we define a linked list using the below code:
st ruct node
{
int data;
st ruct node *next;
};
A few of the most popular applications of Linked Lists are:
Hash tables & Graphs
To maintain a directory of names
Represent sparse matrices Dynamic
memory allocation
Sof twares having undo f unctionality
Implementation of stacks & queues
Implementation of Fibonacci Heap
Arrays vs Linked List
Arrays & Linked Lists, as we understand, are two popular data structures to organize data.
Both of them are efficient in their own ways, but there are some differences that you must
know to choose the right type of data structure for applications.
Arrays Linked Lists
Collection of similar types of data
Collection of the list of data values stored in
elements stored in contiguous memory
random order.
locations.
Elements of the arrays are Elements present in Linked Lists are dependent on
independent of each other. each other.
Has static size where the memory size is
Has dynamic size where the memory size is not f
f ixed and cannot be changed at the run
ixed and can be changed during run time.
time.
Memory is allocated in the stack
Memory is allocated in the heap section.
section.
Memory is allocated at the compile-
Memory is allocated at the run time.
time.
Accessing elements is comparatively slower than
Elements in the array can be accessed f
arrays, as the search f unction has to traverse the list
aster by their index.
f rom the 1st element to f ind an element.
Arrays are comparatively easier to Linked Lists are hard to implement as they are prone to
implement memory leaks, segmentation f aults, etc.
Memory utilization is inef f icient as Memory utilization is optimized as the memory is
memory declared during the compile allocated/deallocated based on the requirements during
time can be lef t unused. run time.
Complexity:Access an element –
Complexity:Access an element – O(n)Insert an
O(1)Insert an element at the beginning
element at the beginning – O(1)Insert an element at
– O(n)Insert an element at the end –
the end – O(n)
O(n)
Arrays can be single/two/ multi-
Linked Lists can be Singly/Doubly/Circular lists.
dimensional.
Types of Linked List in Data Structure
The following are the three types of Linked Lists available:
Singly Linked List
Doubly Linked List
Circular Linked List
Singly Linked List
In general, linked list means a Singly Linked Lists. Every node contains some data and a
pointer to the address of the next node of the same data type in sequence.
NOTE: Singly Linked Lists are unidirectional. i.e. allows the t raversal of data in a single
direction.
Doubly Linked List
As the name suggests, the Doubly Linked List are two-way linked lists containing pointers to
the previous and the next node in the sequence. So, as you can refer to below, you can t
raverse forward and backward in this type of Linked List.
Circular Linked List
Circular Linked Lists t raverse in the form of a circle. So, you can begin at any node and t
raverse the list in either the forward or backward direction until you reach the same node
again. The last node of the Circular Linked List contains the pointer to the f irst node of the
list . Hence, there is no start or endpoint of this type of list .
Note: A Circular Linked List can be Singly if the next pointer of the last
Learn more on Traversing/ Searching/ Inserting/ Deleting in Circular Linked List
Basic Operations on a List
Traversing a Linked List
Inserting an item in the Linked List
Deleting an item f rom the Linked List
Traversing a Linked List
Traversing a linked list simply means accessing the nodes of the linked list in order to perform
some processing on them.
For t raversing the linked list , we will make use of another pointer variable ‘PTR‘ which points
to the node that is currently being accessed. Before we proceed let’s understand the algorithm
behind it .
Algorithm:
Step 1: [INITIALIZE] SET PTR = HEAD
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Apply Process to PTR DATA
Step 4: SET PTR = PTR NEXT
[END OF LOOP]
Step 5: EXIT
In this algorithm,
Step 1: Initialize PTR with the starting address of HEAD. So now, PTR points to the f irst node of the
linked list.
Step 2: Execute a loop which is repeated till PTR processes the last node or it encounters NULL.
Step 3, Print the current node pointed by PTR.
Step 4, Move to the next node by making the PTR variable point to the address of NEXT node
Counting the elements in a Linked List
Let’s understand it better with an example of Counting the elements in a linked list.
To count the elements in a list , we will t raverse each node of the list and while t
raversing every individual node, increment the counter value by 1. Once we reach NULL, that
is, when all the nodes of the linked list have been t raversed, print the f inal value of the
counter.
Algorithm:
Step 1: [INITIALIZE] SET COUNT = 0 Step
2: [INITIALIZE] SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR != NULL Step 4:
SET=+ 1
Step 5: SET PTR = PTR NEXT [END
OF LOOP]
Step 6: PRINT COUNT
Step 7: EXIT
Implementation of Counting the elements of Linked List in C
Copy code
int List Length(struct node *head)
{
st ruct node *current = head; int count = 0;
while(current != NULL)
{
count++;
current = current -> next;
}
return count;
}
NOTE: Time Complexity: O(n), for scanning/ t raversing the list of size n
Inserting an element in a Linked List
Inserting an element in a linked list has three cases:
Inserting a new node bef ore the HEAD (at the beginning)
Inserting a new node af ter the last node (at the end) Inserting a
new node in the middle (random location)
Inserting a Node in the beginning of the Linked List
In this case a new node is inserted before the current HEAD node. We need to modify only
one pointer – New node next pointer. This can be done in following two steps:
Update the next pointer of the new node to point to the current HEAD.
Update the HEAD pointer to point to the new node.
Algorithm to insert a new node in the beginning of the Linked List
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL - > NEXT
Step 4: SET NEW_NODE - > DATA = VAL Step
5: SET NEW_NODE - > NEXT = HEAD Step 6:
SET START = NEW_NODE
Step 7: EXIT
Step 1 involves checking if memory is available for the new node. If the f ree memory is
depleted, an OVERFLOW message is printed. Otherwise, if a f ree memory cell is available,
we allocate space for the new node. Set its DATA part with the given VAL and the next part
is init ialized with the address of the f irst node of the list , which is stored in HEAD. Because
the new node was inserted as the f irst node in the list , it is now known as the HEAD node,
and the HEAD pointer variable now contains the address of the NEW NODE.
Let’s implement this insertion operation in C.
Copy code
// Declare a head pointer as NULL
st ruct node
{
int data;
st ruct node *next;
};
st ruct node *head = NULL;
void addFirst(struct node **head, int val)
{
//create a new node
st ruct node *newNode = malloc(sizeof(struct node));
newNode->data = val;
//make new node points to the head node
newNode->next = *head;
//make new node as head
*head = newNode;
}
NOTE: Time Complexity: O(1), for inserting an element at the beginning of linked list
Inserting a Node at the end of the Linked List
In this case, we need to modify two pointers – last node next pointer and new node next
pointer
New node next pointer points to NULL.
Last nodes next pointer points to the new node.
Algorithm to insert a new node at the end of the Linked List
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 1
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL - > NEXT
Step 4: SET NEW_NODE - > DATA = VAL Step
5: SET NEW_NODE - > NEXT = NULL Step 6:
SET PTR = HEAD
Step 7: Repeat Step 8 while PTR NEXT != NULL
Step 8: SET PTR = PTR- >NEXT
[END OF LOOP]
Step 9: SET PTR - > NEXT = NEW_NODE Step
10: EXIT
In Step 6, we init ialize a pointer variable PTR with HEAD. That is, PTR now points to the
linked list ’s f irst node. We t raverse the linked list in the while loop to get to the last node. In
Step 9, we modify the NEXT pointer of the f inal node to contain the address of the new node
whenever we reach the last node. Remember that the new node’s NEXT f ield includes NULL,
indicating the end of the linked list .
Let’s implement adding a new node at the end of Linked List in C Programming
Copy code
void addLast(struct node **head, int val)
{
//create a new node
st ruct node *newNode = malloc(sizeof(struct node));
newNode->data = val;
newNode->next = NULL;
//if head is NULL, it is an empty list
if (*head == NULL)
*head = newNode;
//Otherwise, find the last node and add the newNode
else
{
st ruct node *last Node = *head;
//last node's next address will be NULL.
while(last Node->next != NULL)
{
last Node = last Node->next;
}
//add the newNode at the end of the linked list
last Node->next = newNode;
}
}
NOTE: Time Complexity of inserting an element at the end of the linked list is O(n).
Inserting a Node in the middle of the Linked List
Let’s say we are given a position to insert the new node, so in this case we would have to
modify two next pointers.
If we want to add an element at position 3, then we need to traverse 2 nodes to insert a new node.
New node will point to the next node of the position where we want to add this node
Position nodes next pointer now points to the new node.
Algorithm to insert a new node in the middle of the Linked List
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET NEW_NODE = AVAIL Step
3: SET AVAIL = AVAIL NEXT
Step 4: SET NEW_NODE - > DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PREPTR - > DATA != NUM Step
8: SET PREPTR = PTR
Step 9: SET PTR = PTR NEXT [END
OF LOOP]
Step 10 : PREPTR NEXT = NEW_NODE Step
11: SET NEW_NODE NEXT = PTR Step 12:
EXIT
In Step 5, we establish a pointer variable PTR with START. That is, PTR now points to the
linked list ’s f irst node. Then we use another pointer variable, PREPTR, to hold the address of
the node before PTR. PREPTR is init ially init ialized to PTR. PTR, PREPTR, and START are
now all pointing to the f irst node in the linked list .
In the while loop, we t raverse the linked list until we reach the node with the value NUM.
We need to go to this node since the new node will be added after it . When we reach this
node, we modify the NEXT pointers in Steps 10 and 11.
Deleting an item from the Linked List
Similar to insertion deleting also has three cases:
Deleting the f irst node Deleting
the last node Deleting an
intermediate node
Deleting the First Node
First node of the linked list can be removed in the following two steps:
Create a temporary node pointing the head
Move the head node pointer to the next node and delete the temporary node.
Deleting the Last Node
Traverse the list and while traversing maintain the previous node address. By the time we reach the end
of list, we will have two pointers – one pointing to tail node and other pointing to the node bef ore.
Update previous nodes next pointer with NULL.
Delete the tail node
Time Complexity of Linked List Operations
Linked Lists provide an optimized way to insert, delete, and update the information along
with storing the data, at the cost of extra space required for storing the address of the next
node. The t ime and space complexities of Linked Lists are as follows:
Average Scenario Worst Scenario
Search O(n) O(n)
Insertion O(1) O(1)
Deletion O(1) O(1)
Now that you know what Linked Lists are and their types, let us understand their various
operations. With this, we end this article on Introduction to Linked Lists and how to
implement it . We hope you found it informative. Now you can practice our popular linked list
questions asked in interview. In our next article we will learn about the t ree data structure.
Have you recently completed any online course/certification? Tell us what liked or disliked in
the course. It might help others to choose a right course for them.
Click here to submit its review with Shiksha Online.
FAQs
What is linked list in data structure
Where do we use doubly linked list?
Why doubly linked list is known as two way list?
What is Circular Linked List?
Does Circular Linked List have a head node?
Can a Circular Linked List have a null pointer?
