In this section of the tutorial, we will discuss the use of Linked List in Data Structure and its implementation in programs.
Now let’s move on further to the introduction of Linked List in Data Structure.
What is Linked List in Data Structure?
A linked list is a list on which we can perform different operations, such as fetching, insertions, changes, and deletion, that can be done anywhere in the list. It can be implemented at the beginning, middle, or at the end of the list.
- Linked lists can be used to perform different operations of the data present inside it.
- Linked list can be used to process data, search the desired data, insert or remove data from the list.
- The application of Linked List in Data Structure is maintaining a list or records, searching the list, traversal, and modifying the list as per the requirement.
Now we will learn how we can implement Linked List in Data Structure.
Linked List Implementation
To implement a list, we need two different structures, a head node and data node, as shown in the diagram below.
Linked List Structure
Head Node
A head node is used to store the head pointer and other data about the list. A node is a part of the list.
Below is an example of a head node.
list count head end list
- The node containing the data about the list is called metadata.
- It contains the data about the data in the list.
- For example, the head structure containing the metadata: count, an integer that contains the number of nodes present in the list.
Data Node
The data node contains the data type used in the application. Below is an example of a data node.
data key field1 field2 field3 field4 ... fieldN end data
- The data type should be tailored to the created application.
- Here, we also include a key field for the applications that will operate searching the list by key.
Now we will learn about the different operations that can be carried out on Linked List.
Linked List Operations
As we have discussed earlier that in a linked list we can perform different operations, such as fetching, insertions, changes, and deletion, that can be done anywhere in the list. It can be implemented at the beginning, middle, or at the end of the list. Below is a table that contains a list of different operations that can be operated on a Linked List.
Linked List Operations |
Create List |
Insert Node |
Delete Node |
List Search |
Retrieve Node |
Empty List |
Full List |
List Count |
Traverse List |
Destroy List |
Create List
Create List is used to allocate the head and initializes the metadata for the list. Below is an illustrated diagram to define the use of create list operation on Linked List.
Algorithm of Create List
Algorithm createList (list) 1 allocate (list) 2 set list head to null 3 set list count to 0 end createList
Insert Node
Insert Node is used to add data to a list. Only the logical predessor is needed to insert a node into the list. There are however three steps to insert a node into a list:
- Memory allocation of the new node and moving data to the node.
- Pointing the new node to its successor.
- Pointing the new node’s predecessor to the new node.
We can add the node at different points in the list when the predecessor pointer is null. So we either add to an empty list or at the beginning of the list. And if the predecessor is not null, we can add in the middle of the list of at the end of the list.
Below is an illustrated diagram to define the use of insert node operation on Linked List.
Delete Node
Delete Node is used to remove a node from the list by changing various link pointers and then physically deleting the node from the dynamic memory.
Depending upon whether the head is a null pointer or not, similar to the case of Insert Node, we can also remove a node from the beginning, middle or from the end of the list. Now, to carry this out, we have two situations here: delete first node and delete any node.
Below is an illustrated diagram to define the use of delete node operation on Linked List.
List Search
List Search is used by several other algorithms to search for data present in the list. To retrieve data, we need to search the list and find the data. To carry out this operation, we need to use a sequential search that will return the location of the data that we are searching for.
Below is an illustrated diagram to define the use of list search operation on Linked List.
Retrieve Node
Retrieve Node is used to search and locate the data in the list. If the data are found in the list, it moves the data to the output area and returns true. If the data are not found, it returns false.
Algorithm of Retrieve Node
Algorithm retrieveNode (list, key, dataOut) 1 set found to searchList (list, pPre, pLoc, key) 2 if (found) 1 move pLoc data to dataOut 3 end if 4 return found end retrieveNode
Empty List
Empty List is used to specify the processing logic on data being present in the list. It returns a simple Boolean indicating the presence or absence of data in the list.
Algorithm of Empty List
Algorithm emtpyList (list) 1 if (list count equal 0) 1 return true 2 else 1 return false end emptyList
Full List
It seems the same as the empty list, but it works the opposite way. It is used to test how much the memory is left in the dynamic memory.
Algorithm of Full List
Algorithm fullList (list) 1 if (memory full) 1 return true 2 else 2 return false 3 end if 4 return true end fullList
List Count
List Count is used to return the count of number of nodes present in the list. It is useful because the calling module has no direct access to the list structure.
Algorithm of List Count
Algorithm listCount (list) 1 return (list count) end listCount
- Here, the algorithm returns the integer representing number of nodes in list.
- list is metadata structure to a valid list.
- The algorithm returns the count for number of nodes in list.
Traverse List
Traverse List is used to traverse a list from the first node while examining each node in succession until the last node. Traverse List is used in an application that requires the entire list to be processed.
Below is an illustrated diagram to define the use of traverse list operation on Linked List.
Destroy List
Destroy List is used to destroy the list when it is no longer needed. It deletes any nodes present in the list and recycles the memory. Then it sets the metadata to null.
Algorithm of Destroy List
Algorithm destroyList (pList) 1 loop (not at end of list) 1 set list head to successor node 2 release memory to heap 2 end loop 3 set list pos to null 4 set list count to 0 end destroyList
Program example to demonstrate the implementation of some Linked List Operations
Code:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void insert_begin ();
void insert_end ();
void insert_general();
void delete_begin();
void delete_end();
void delete_general();
void list_search();
int main()
{
void insert_begin ();
void insert_end ();
void insert_general();
void delete_begin();
void delete_end();
void delete_general();
void list_search();
return 0;
}
void insert_begin()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nData Overflow");
}
else
{
printf("\nEnter data value: \n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode Inserted.");
}
}
void insert_end()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nData Overflow");
}
else
{
printf("\nEnter value: \n");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
printf("\nNode Inserted.");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode Inserted.");
}
}
}
void insert_general()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nData Overflow");
}
else
{
printf("\nEnter data value: ");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter preceding location: ");
scanf("\n%d",&loc);
temp=head;
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\nInsertion Failed\n");
return;
}
}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode Inserted.");
}
}
void delete_begin()
{
struct node *ptr;
if(head == NULL)
{
printf("\nEmpty List\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode at the beginning is deleted.\n");
}
}
void delete_end()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nEmpty List");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly Node of the list\n");
}
else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nNode at the end is deleted.\n");
}
}
void delete_general()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter preceding location: \n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
if(ptr == NULL)
{
printf("\nDeletion Failed");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nNode Deleted at location %d in the list.",loc+1);
}
void list_search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter data to be search: \n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("Data is found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("Data not found.\n");
}
}
}
In the next section of the tutorial, we will discuss the different types of Linked List in Data Structure such as, Doubly Linked List, Circular Linked List, and Circular Doubly List and their implementation in programs that will be used thoroughly in this Data Structure tutorial.
