Introduction to Linked Lists
Linked list is a linear data structure that contains sequence of elements such that
each element links to its next element in the sequence. Each element in a linked list
is called as "Node and each node need not be stored in contiguous memory
locations.
A linked list is a sequence of data structures, which are connected together via
links. A linked list is a way to store a collection of elements. Like an array these
can be character or integers. Each element in a linked list is stored in the form of
a node.
Linked List is a very commonly used linear data structure which consists of group
of nodes in a sequence.
Each node holds its own data and the address of the next node hence forming a
chain like structure.
Linked Lists are used to create trees and graphs.
Node:
A node is a collection of two sub-elements or parts. A data part that stores the element and
a next part that stores the link to the next node.
Linked List:
A linked list is formed when many such nodes are linked together to form a chain.
Each node points to the next node present in the order. The first node is always
used as a reference to traverse the list and is called HEAD. The last node points
to NULL.
Advantages of Linked Lists
They are a dynamic in nature which allocates the memory when required.
Insertion and deletion operations can be easily implemented.
Stacks and queues can be easily executed.
Linked List reduces the access time.
Disadvantages of Linked Lists
The memory is wasted as pointers require extra memory for storage.
No element can be accessed randomly; it has to access each node sequentially.
Reverse Traversing is difficult in linked list.
Applications of Linked Lists
Linked lists are used to implement stacks, queues, graphs, etc.
Linked lists let you insert elements at the beginning and end of the list.
In Linked Lists we don't need to know the size in advance.
Types of Linked Lists
There are 3 different implementations of Linked List available, they are:
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
Let's know more about them and how they are different from each other.
Singly Linked List
Singly linked lists contain nodes which have a data part as well as an address
part i.e. next, which points to the next node in the sequence of nodes.
The operations we can perform on singly linked lists
are insertion, deletion and traversal.
The formal definition of a single linked list is as follows...
Single linked list is a sequence of elements in which every element has link to its next
element in the sequence.
Doubly Linked List
In a single linked list, every node has link to its next node in the sequence. So, we
can traverse from one node to other node only in one direction and we can not
traverse back. We can solve this kind of problem by using double linked list.
Double linked list can be defined as follows...
Double linked list is a sequence of elements in which every element has links
to its previous element and next element in the sequence.
In a doubly linked list, each node contains a data part and two addresses, one for
the previous node and one for the next node.
Circular Linked List
In circular linked list the last node of the list holds the address of the first node
hence forming a circular chain.
In single linked list, every node points to its next node in the sequence and the last
node points NULL. But in circular linked list, every node points to its next node in
the sequence but the last node points to the first node in the list.
Circular linked list is a sequence of elements in which every element has link
to its next element in the sequence and the last element has a link to the first
element in the sequence.
That means circular linked list is similar to the single linked list except that the last
node points to the first node in the list
We will learn about all the 3 types of linked list, one by one, in the next tutorials. So click
on Nextbutton, let's learn more about linked lists.
Difference between Array and Linked List
Both Linked List and Array are used to store linear data of similar type, but an
array consumes contiguous memory locations allocated at compile time, i.e. at the
time of declaration of array, while for a linked list, memory is assigned as and
when data is added to it, which means at runtime.
This is the basic and the most important difference between a linked list and an
array. In the section below, we will discuss this in details along with highlighting
other differences.
Array is a data type which is widely implemented as a default type, in almost all
the modern programming languages, and is used to store data of similar type.
But there are many use cases, like the one where we don't know the quantity of
data to be stored, for which advanced data structures are required, and one such
data structure is linked list.
Let's understand how array is different from Linked list.
ARRAY LINKED LIST
Array is a collection of elements of Linked List is an ordered collection of elements,
similar data type. which are connected to each other using
pointers.
Array supports Random Access, Linked List supports Sequential Access, which
which means elements can be means to access any element/node in a linked
accessed directly using their index, list, we have to sequentially traverse the
like arr[0] for 1st element, arr[6] for complete linked list, upto that element.
7th element etc.
To access nth element of a linked list, time
Hence, accessing elements in an complexity is O(n).
array is fast with a constant time
complexity of O(1).
In an array, elements are stored In a linked list, new elements can be stored
in contiguous memory location or anywhere in the memory.
consecutive manner in the memory.
Address of the memory location allocated to the
new element is stored in the previous node of
linked list, hence formaing a link between the
two nodes/elements.
In array, Insertion and In case of linked list, a new element is stored at
Deletionoperation takes more time, the first free and available memory location,
as the memory locations are with only a single overhead step of storing the
consecutive and fixed. address of memory location in the previous node
of linked list.
Insertion and Deletion operations are fast in
linked list.
Memory is allocated as soon as the Memory is allocated at runtime, as and when a
array is declared, at compile time. new node is added. It's also known as Dynamic
It's also known as Static Memory Memory Allocation.
Allocation.
In array, each element is In case of a linked list, each node/element points
independent and can be accessed to the next, previous, or maybe both nodes.
using it's index value.
Array can single dimensional, two Linked list can
dimensional or multidimensional be Linear(Singly), Doubly or Circularlinked
list.
Size of the array must be specified at Size of a Linked list is variable. It grows at
time of array decalaration. runtime, as more nodes are added to it.
Array gets memory allocated in Whereas, linked list gets memory allocated
the Stacksection. in Heapsection.
Below we have a pictorial representation showing how consecutive memory
locations are allocated for array, while in case of linked list random memory
locations are assigned to nodes, but each node is connected to its next node
using pointer.
On the left, we have Array and on the right, we have Linked List.
Basic Operations
Following are the basic operations supported by a list.
Insertion − add an element at the beginning of the list.
Deletion − delete an element at the beginning of the list.
Display − displaying complete list.
Search − search an element using given key.
Delete − delete an element using given key.
Operations on Single Linked List
The following operations are performed on a Single Linked List
Insertion
Deletion
Display
Before we implement actual operations, first we need to setup empty list. First
perform the following steps before implementing actual operations.
Step 1 - Include all the header files which are used in the program.
Step 2 - Declare all the user defined functions.
Step 3 - Define a Node structure with two members data and next
Step 4 - Define a Node pointer 'head' and set it to NULL.
Step 5 - Implement the main method by displaying operations menu and
make suitable function calls in the main method to perform user selected
operation.
Declaring a Linked list:
In C language, a linked list can be implemented using structure and pointers.
struct LinkedList{
int data;
struct LinkedList *next;
};
The above definition is used to create every node in the list. The data field
stores the element and the next is a pointer to store the address of the next node.
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void printList(struct Node *n)
{
while (n != NULL)
{
printf(" %d ", n->data);
n = n->next;
}
}
Void main()
{
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
//struct Node* cur=NULL;
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
printList(head);
//printf("elmnts");
//for(cur=head;cur!=NULL;cur=cur->link)
//{ printf("%d\n",cur->data); }
return 0;
}
Insertion
In a single linked list, the insertion operation can be performed in three ways. They
are as follows...
1. Inserting At Beginning of the list
2. Inserting At End of the list
3. Inserting At Specific location in the list
Inserting At Beginning of the list
We can use the following steps to insert a new node at beginning of the single
linked list...
Step 1 - Create a newNode with given value.
Step 2 - Check whether list is Empty (head == NULL)
Step 3 - If it is Empty then,
set newNode→next = NULL and head = newNode.
Step 4 - If it is Not Empty then,
set newNode→next = head and head = newNode.
Inserting At End of the list
We can use the following steps to insert a new node at end of the single linked
list...
Step 1 - Create a newNode with given value and newNode →
next as NULL.
Step 2 - Check whether list is Empty (head == NULL).
Step 3 - If it is Empty then, set head = newNode.
Step 4 - If it is Not Empty then, define a node pointer temp and initialize
with head.
Step 5 - Keep moving the temp to its next node until it reaches to the last
node in the list (until temp → next is equal to NULL).
Step 6 - Set temp → next = newNode.
Inserting At Specific location in the list (After a Node)
We can use the following steps to insert a new node after a node in the single
linked list...
Step 1 - Create a newNode with given value.
Step 2 - Check whether list is Empty (head == NULL)
Step 3 - If it is Empty then, set newNode →
next = NULL and head = newNode.
Step 4 - If it is Not Empty then, define a node pointer temp and initialize
with head.
Step 5 - Keep moving the temp to its next node until it reaches to the node
after which we want to insert the newNode (until temp1 → data is equal
to location, here location is the node value after which we want to insert the
newNode).
Step 6 - Every time check whether temp is reached to last node or not. If it
is reached to last node then display 'Given node is not found in the list!!!
Insertion not possible!!!' and terminate the function. Otherwise move
the temp to next node.
Step 7 - Finally, Set 'newNode → next = temp → next' and 'temp →
next = newNode'
Deletion
In a single linked list, the deletion operation can be performed in three ways. They
are as follows...
1. Deleting from Beginning of the list
2. Deleting from End of the list
3. Deleting a Specific Node
Deleting from Beginning of the list
We can use the following steps to delete a node from beginning of the single linked
list...
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not
possible' and terminate the function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize
with head.
Step 4 - Check whether list is having only one node (temp →
next == NULL)
Step 5 - If it is TRUE then set head = NULL and
delete temp (Setting Empty list conditions)
Step 6 - If it is FALSE then set head = temp → next, and delete temp.
Deleting from End of the list
We can use the following steps to delete a node from end of the single linked list...
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not
possible' and terminate the function.
Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and
'temp2' and initialize 'temp1' with head.
Step 4 - Check whether list has only one Node (temp1 → next == NULL)
Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And
terminate the function. (Setting Empty list condition)
Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its
next node. Repeat the same until it reaches to the last node in the list.
(until temp1 → next == NULL)
Step 7 - Finally, Set temp2 → next = NULL and delete temp1.
Deleting a Specific Node from the list
We can use the following steps to delete a specific node from the single linked
list...
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not
possible' and terminate the function.
Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and
'temp2' and initialize 'temp1' with head.
Step 4 - Keep moving the temp1 until it reaches to the exact node to be
deleted or to the last node. And every time set 'temp2 = temp1' before
moving the 'temp1' to its next node.
Step 5 - If it is reached to the last node then display 'Given node not found
in the list! Deletion not possible!!!'. And terminate the function.
Step 6 - If it is reached to the exact node which we want to delete, then
check whether list is having only one node or not
Step 7 - If list has only one node and that is the node to be deleted, then
set head = NULL and delete temp1 (free(temp1)).
Step 8 - If list contains multiple nodes, then check whether temp1 is the first
node in the list (temp1 == head).
Step 9 - If temp1 is the first node then move the head to the next node
(head = head → next) and delete temp1.
Step 10 - If temp1 is not first node then check whether it is last node in the
list (temp1 → next == NULL).
Step 11 - If temp1 is last node then set temp2 → next = NULL and
delete temp1 (free(temp1)).
Step 12 - If temp1 is not first node and not last node then set temp2 →
next = temp1 → next and delete temp1 (free(temp1)).
Displaying a Single Linked List
We can use the following steps to display the elements of a single linked list...
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!!' and terminate the
function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize
with head.
Step 4 - Keep displaying temp → data with an arrow (--->)
until temp reaches to the last node
Step 5 - Finally display temp → data with arrow pointing to NULL (temp
→ data ---> NULL).
Insertion Operation
Insertion is a three step process −
Create a new Link with provided data.
Point New Link to old First Link.
Point First Link to this New Link.
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->data = data;
//point it to old first node
link->next = head;
//point first to new first node
head = link;
}
Deletion Operation
Deletion is a two step process −
Get the Link pointed by First Link as Temp Link.
Point First Link to Temp Link's Next Link.
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//mark next to first link as first
head = head->next;
//return the deleted link
return tempLink;
Navigation Operation
Navigation is a recursive step process and is basis of many operations like
search, delete etc. −
Get the Link pointed by First Link as Current Link.
Check if Current Link is not null and display it.
Point Current Link to Next Link of Current Link and move to above step.
Note −
//display the list
void printList(){
struct node *ptr = head;
printf("\n[ ");
//start from the beginning
while(ptr != NULL){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
printf(" ]");
Advanced Operations
Following are the advanced operations specified for a list.
Sort − sorting a list based on a particular order.
Reverse − reversing a linked list.
Sort Operation
We've used bubble sort to sort a list.
void sort(){
int i, j, k, tempKey, tempData ;
struct node *current;
struct node *next;
int size = length();
k = size ;
for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head ;
next = head->next ;
for ( j = 1 ; j < k ; j++ ) {
if ( current->data > next->data ) {
tempData = current->data ;
current->data = next->data;
next->data = tempData ;
tempKey = current->key;
current->key = next->key;
next->key = tempKey;
current = current->next;
next = next->next;
Reverse Operation
Following code demonstrate reversing a single linked list.
void reverse(struct node** head_ref) {
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
*head_ref = prev;
