Introduction to Linked List Data Structure
In this article, you will understand what linked list are, what are various operations you can perform on them and how to implement it in C.
Data Structures offers a variety of ways to organize data and use it effectively. One such famous data structure is the Linked List. As the name suggests, linked list data structure are a collection of data elements in linear form.
Table of Content
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
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:
struct node{ int data; struct node *next;};
In Python we define a linked list using the below code:
class Node: def __init__(self, data): self.data = data self.next = None
How is Linked List Stored in the Memory?
The image on your right, shows a chunk of memory locations which range from 1 to 10. The highlighted
portion contains data. Remember that the nodes of a linked list need not be in consecutive memory locations. In our example, the nodes for the linked list are stored at addresses 1, 5, 7, 8, and 10.
In the diagram on the right, the variable HEAD is used to hold the address of the first node. Since HEAD = 1 in this case, the initial data ‘H’ is stored at address 1. The address of the next node is stored in the corresponding NEXT, which is 5. So we’ll go to address 5 to get the next data item.
E is the second data piece retrieved from address 5. We find the corresponding NEXT to go to the next node. We receive the next address, 7, from the item in the NEXT, and L as the data. This operation is repeated until we reach a place where the NEXT item contains -1 or NULL and this denotes the end of linked list.
Real-life Example of Linked-List Data Structure
Below are some of the example of linked list which you must have come across:
- The back and forward button on your browser to access previous and next URL.
- Your music playlist, when your play the next song or the last played track.
- The file browser on your system which allows you to go back to the previous directory.
- Instagram stories of your peers are added as Linked List. Each tap you make on the screen allows you to traverse through the list.
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
- Softwares having undo functionality
- Implementation of stacks & queues
- Implementation of Fibonacci Heap
Next, let us understand the different types of Linked Lists
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 elements stored in contiguous memory locations. | Collection of the list of data values stored in random order. |
| Elements of the arrays are independent of each other. | Elements present in Linked Lists are dependent on each other. |
| Has static size where the memory size is fixed and cannot be changed at the run time. | Has dynamic size where the memory size is not fixed and can be changed during run time. |
| Memory is allocated in the stack section. | Memory is allocated in the heap section. |
| Memory is allocated at the compile-time. | Memory is allocated at the run time. |
| Elements in the array can be accessed faster by their index. | Accessing elements is comparatively slower than arrays, as the search function has to traverse the list from the 1st element to find an element. |
| Arrays are comparatively easier to implement | Linked Lists are hard to implement as they are prone to memory leaks, segmentation faults, etc. |
| Memory utilization is inefficient as memory declared during the compile time can be left unused. | Memory utilization is optimized as the memory is allocated/deallocated based on the requirements during run time. |
| Complexity:Access an element – O(1)Insert an element at the beginning – O(n)Insert an element at the end – O(n) | Complexity:Access an element – O(n)Insert an element at the beginning – O(1)Insert an element at the end – O(n) |
| Arrays can be single/two/ multi-dimensional. | Linked Lists can be Singly/Doubly/Circular lists. |
Must Read: ArrayList vs LinkedList
Types of Linked List in Data Structure
The following are the three types of Linked Lists available:
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 traversal of data in a single direction.
Learn more on Traversing/ Searching/ Inserting/ Deleting in Singly Linked List
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 traverse forward and backward in this type of Linked List.
Learn more on Traversing/ Searching/ Inserting/ Deleting in Doubly Linked List
Circular Linked List
Circular Linked Lists traverse in the form of a circle. So, you can begin at any node and traverse 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 first 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 from 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 traversing 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 first 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 traverse each node of the list and while traversing 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 traversed, print the final 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
int ListLength(struct node *head){ struct node *current = head; int count = 0; while(current != NULL) { count++; current = current -> next; } return count;}
NOTE: Time Complexity: O(n), for scanning/ traversing 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 before the HEAD (at the beginning)
- Inserting a new node after 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 free memory is depleted, an OVERFLOW message is printed. Otherwise, if a free memory cell is available, we allocate space for the new node. Set its DATA part with the given VAL and the next part is initialized with the address of the first node of the list, which is stored in HEAD. Because the new node was inserted as the first 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.
// Declare a head pointer as NULLstruct node{ int data; struct node *next;};
struct node *head = NULL;
void addFirst(struct node **head, int val){ //create a new node struct 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 initialize a pointer variable PTR with HEAD. That is, PTR now points to the linked list’s first node. We traverse the linked list in the while loop to get to the last node. In Step 9, we modify the NEXT pointer of the final node to contain the address of the new node whenever we reach the last node. Remember that the new node’s NEXT field 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
void addLast(struct node **head, int val){ //create a new node struct 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 { struct node *lastNode = *head; //last node's next address will be NULL. while(lastNode->next != NULL) { lastNode = lastNode->next; }
//add the newNode at the end of the linked list lastNode->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 first node. Then we use another pointer variable, PREPTR, to hold the address of the node before PTR. PREPTR is initially initialized to PTR. PTR, PREPTR, and START are now all pointing to the first node in the linked list.
In the while loop, we traverse 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 first 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 before.
- 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 time 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 tree 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
Linked list are linear arrangement of data in the memory. Each node of a linked list consist of data and address which points to the next data node in the list. Unlike an array the data elements are not contiguous but are randomly spread in the memory. This helps in preventing memory wastage.
Where do we use doubly linked list?
It is used in navigation systems where both forward and backward navigation is required. A back and forward button is used by the browser to provide backward and forward navigation of visited web pages.
Why doubly linked list is known as two way list?
A doubly linked list has a pointer to both the next and previous node. This guarantees that the list can be traversed inu00a0both directions.
What is Circular Linked List?
A circular linked list is a type of linked list in which the initial and end nodes are linked to create a circle. In this case, the address of the last node is the same as the address of the first node.
Does Circular Linked List have a head node?
No, a circular linked list does not require a head node since there is no head. It does, however, need a reference to some node inside the list in order to access all of the entries.
Can a Circular Linked List have a null pointer?
No there is no NULL pointer in case of a circular linked list to mark the end. You can take any node in a Circular Linked List as a starting point. The entire list can then be traversed by starting from this one node.
Experienced AI and Machine Learning content creator with a passion for using data to solve real-world challenges. I specialize in Python, SQL, NLP, and Data Visualization. My goal is to make data science engaging an... Read Full Bio
Top Picks & New Arrivals
