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.
Dinesh Thakur holds an B.C.A, MCDBA, MCSD certifications. Dinesh authors the hugely popular