A linked list is called so because each of items in the list is a part of a structure, which is linked to the structure containing the next item. This type of list is called a linked list since it can be considered as a list whose order is given by links from one item to the next. [Read more…] about What is Linked Lists
Short Note on Single Linked List
A singly linked list is a linked list in which each node contains only one link field pointing the next node in the list.
Each node is divided in two parts.
1. data field.
2. pointer.
For Example: –
Node structure
The data field contains the data elements that have to be stored in the list. The pointer will point the next node in the list.
The operations done on a list are: –
1 Insertion
2 Deletion
Insertion
Insertion in the head node
To insert a node in the head node, just change the pointer field of the new node to point to the head node. Let the new node be ‘Temp’ and the head node be ‘Head’, then the insertion is
Temp ? data = X;
Head ? next = head
Insertion in the middle node
To insert in the middle node we need to change two pointers. Let the new node be ‘Temp’ and the present node is ‘Present’ and, the next node to the present node is ‘future’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Temp? data = X
Present ? next = temp
Temp ? next = future
Insertion in the last node
To insert an element in the last position just change the pointer field of the present last node to point to the new node, then set the pointer field of the new node to NULL. Let the new node be ‘Temp’ and the present node is ‘Present’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Present ? next =Temp
Temp ? next =null
Temp ? data = X
Deletion
Deletion in the head node
To delete a node in the head node, just point the head node as the second node. Let the head node be ‘Head’, and then the deletion is
Head ? next = head
Deletion in the middle node
To delete a node in the middle we need to change two pointers. Let the node to be deleted is ‘Temp’ and the node previous to the node to be deleted is ‘Present’ and, the next node to the present node is ‘future’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Present ? next = future
Deletion in the last node
To delete an element in the last position just change the pointer field of the previous node to the last to null. Let the last node be ‘Temp’ and the previous node is ‘Present’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Previous ? next =NULL
Short Note on Singly Circular Linked List
The advantage of using Circular Linked List is the last null pointer is replaced and the pointer field of the last node points to the first node, due to this circular arrangement the traversing become quite easier.
The insertion and deletion in the first and middle are same as singly linked list except the last node.
Insertion
Insertion in the last node
To insert a node in the last position, insert the new node after the current last node, and then change the pointer field of the new node to point to the first node. Let the last node be last, the new node to be inserted to be new, the first node in the list to be first. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Last ? next = new
New ? next =first
Deletion
Deletion in the last node
To delete a node in the last position, change the pointer field of the previous node to the current last to point the first node. Let the last node be last, the previous node to the current last node to be pre, the first node in the list to be first. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the deletion is
Prev ? next = first
What is Linked lists? How Many Type of Link List
A linked list can be viewed as a group of items, each of which points to the item in its neighbourhood. An item in a linked list is known as a node. A node contains a data part and one or two pointer part which contains the address of the neighbouring nodes in the list.
Linked list is a data structure that supports dynamic memory allocation and hence it solves the problems of using an array.
Types of linked lists
The different types of linked lists include:
1. Singly linked lists
2. Circular linked lists
3 Doubly linked lists
Simple/Singly Linked Lists
In singly linked lists, each node contains a data part and an address part. The address part of the node points to the next node in the list.
Node Structure of a linked list
An example of a singly linked list can be pictured as shown below. Note that each node is pictured as a box, while each pointer is drawn as an arrow. A NULL pointer is used to mark the end of the list.
The head pointer points to the first node in a linked list If head is NULL, the linked list is empty
A head pointer to a list
Possible Operations on a singly linked list
.Insertion: Elements are added at any position in a linked list by linking nodes.
Deletion: Elements are deleted at any position in a linked list by altering the links of the adjacent nodes.
Searching or Iterating through the list to display items.
To insert or delete items from any position of the list, we need to traverse the list starting from its root till we get the item that we are looking for.
Implementation of a singly linked list
Creating a linked list
A node in a linked list is usually a structure in C and can be declared as
struct Node
{
int info;
Node *next;
}; //end struct
A node is dynamically allocated as follows:
Node *p;
p = new Node;
For creating the list, the following code can be used:
do
{
Current_node = malloc (sizeof (node) );
Current_node->info=input_value;
Current_node->next=NULL;
if(root_node==NULL) // the first node in the list
root_node=Current_node;
else
previous_node->next=Current_node;
previous_node=Current_node;
scanf(“%d”,&input_value);
} while(x!=-999);
The above given code will create the list by taking values until the user inputs -999.
Inserting an element
After getting the position and element which needs to be inserted, the following code can be used to insert an element to the list
if(position==1||root_node==NULL)
{
Current_node->next=root_node;
Root_node=Current_node;
}
else
{
counter=2;
temp_node=root_node;
while((counter<position) &&(temp_node!=NULL))
{
counter++;
temp_node=temp_node->next;
}
Current_node->next=temp_node->next;
temp_node->next=Current_node;
}
The following figure illustrates how a node is inserted at an intermediate position in the list.
The following figure illustrates how a node is inserted at the beginning of the list.
Deleting an element
After getting the element to be removed, the following code can be used to remove the particular element.
temp_node=root_node;
if ( root_node != NULL )
if ( temp_node->info == input_element )
{
root_node=root_node->next;
return;
}
While ( temp_node != NULL && temp_node->next->info !=
input_element )
temp_node = temp_node->next;
if ( temp->next != NULL )
{
delete_node = temp_node->next;
temp_node->next=delete_node->next;
free ( delete_node ) ;
}
The following figures illustrate the deletion of an intermediate node and the deletion of the first node from the list.
To display the elements of the list
temp_node = root_node;
while(temp_node != NULL)
{
printf(“%d\t”, temp_node->info);
temp_node = temp_node->next;
}
The following figure illustrates the above piece of code.
The effect of the assignment temp_node = temp_node->next
Efficiency and advantages of Linked Lists
Although arrays require same number of comparisons, the advantage lies in the fact that no items need to be moved after insertion or deletion.
As opposed to fixed size of arrays, linked lists use exactly as much memory as is needed.
Individual nodes need not be contiguous in memory.
What is Doubly Linked List
A more sophisticated kind of linked list is a doubly-linked list or a two-way linked list. In a doubly linked list, each node has two links: one pointing to the previous node and one pointing to the next node.
Node structure
Implementation of a doubly linked list
Adding an element to the list
To add the first node
first_node->next = NULL;
first_node->data = input_element;
first_node->prev = NULL;
To add a node at the position specified
Temp_node = *first_node;
for ( counter = 0 ; counter<position-1 ; counter++ )
{
Temp_node = Temp_node->next;
}
new_node->next = temp_node->next;
temp_node->next->new_node;
new_node->prev = temp_node->next->prev;
temp_node->next->prev = new_node;
Deleting a particular element from the list
Temp_node = *first_node;
If ( temp_node->data = = input_element )
First_node = first_node->next;
else
{
while ( temp_node != NULL && temp_node->next->data !=
input_element)
temp_node = temp_node -> next;
delete_node=temp_node->next;
temp_node->next=delete_node->next;
delete_node->next->prev=temp_node;
free(delete_node);
}
What is Circular Linked Lists
In a circularly-linked list, the first and final nodes are linked together. In another words, circularlylinked lists can be seen as having no beginning or end. To traverse a circular linked list, begin at any node and follow the list in either direction until you return to the original node.
This type of list is most useful in cases where you have one object in a list and wish to see all other objects in the list. The pointer pointing to the whole list is usually called the end pointer.
What is Singly-circularly-linked list
In a singly-circularly-linked list, each node has one link, similar to an ordinary singly-linked list, except that the link of the last node points back to the first node. As in a singly-linked list, new nodes can only be efficiently inserted after a node we already have a reference to.
For this reason, it’s usual to retain a reference to only the last element in a singly-circularly-linked list, as this allows quick insertion at the beginning, and also allows access to the first node through the last node’s next pointer. The following figure shows a singly circularly linked list.
What is Doubly-circularly-linked list
In a doubly-circularly-linked list, each node has two links, similar to a doubly-linked list, except that the previous link of the first node points to the last node and the next link of the last node points to the first node. As in doubly-linked lists, insertions and removals can be done at any point with access to any nearby node.
Circularly-linked list vs. linearly-linked list
Circularly linked lists are useful to traverse an entire list starting at any point. In a linear linked list, it is required to know the head pointer to traverse the entire list. The linear linked list cannot be traversed completely with the help of an intermediate pointer.
Access to any element in a doubly circularly linked list is much easier than in a linearly linked list since the particular element can be approached in two directions. For example to access an element present in the fourth node of a circularly linked list having five elements, it is enough to start from the last node and traverse the list in the reverse direction to get the value in the fourth node.
Implementation of a circular linked list:
Creating the list
while (input_element != -999)
{
new_node=(struct node *) malloc (size);
new_node->info=input_element;
if ( root_node==NULL )
root_node=new_node;
else
( *last_node )->next=new_node;
(*last_node)=new_node;
scanf(“%d”,&input_element);
}
if(root!=NULL)
new->next=root;
return root;
Inserting elements into the list
After getting the position and value to be inserted, the following code can be followed:
new_node=(struct node *)malloc(sizeof(struct node));
new_node-> info=input_element;
if((position==1)||((*root_node)==NULL))
{
new_node->next =*root_node;
*root_node = new_node;
if((*last_node)!=NULL)
(*last_node)->next=*root_node;
else
*last_node=*start_node;
}
else
{
temp_node=*root_node;
counter=2;
while ( (counter<position) && (temp_node->next !=
(*root_node) ) )
{
temp_node=temp_node->next;
++counter;
}
if(temp_node->next==(*root_node))
*last_node=new_node;
new_node->next=temp_node->next;
temp_node->next=new_node;
}
Deleting an element from the list
After getting the element to be deleted, the following code can be used:
If(*front_node != NULL)
{
printf(“The item deleted is %d”,(*front_node->info));
If (*front_node == *rear_node)
{
*front_node = *rear_node = NULL;
}
else
{
*front_node = *front_node->next;
*rear_node->link = *front_node;
}
}