Data Structures using „C‟ - Linked Lists

Data Structures using „C‟ Unit 5

Unit 5 Linked Lists
Structure:
5.0 Introduction
5.1 Linear list
5.2 Linked list
5.2.1 Typical basic linked-list operations
5.2.2 Singly-Linked Lists
Self Assessment Questions
5.3 Circular singly linked list
5.3.1 Insert a node at the front end
5.3.2 Insert a node at the rear end
5.3.3 Delete a node from the front end
5.3.4 Delete a node from the rear end
Self Assessment Questions
5.4 Doubly linked lists
5.4.1 Insert a node at the front end
5.4.2 Insert a node at the rear end
5.4.3 Delete a node from the front end
Self Assessment Questions
5.5 Summary
5.6 Terminal Questions
5.0 Introduction
List is an aggregate of data in a useful order for example numbers 1, 2, 3, 4, 5. simple data structure such as arrays, sequential mapping, have the property that successive nodes of the data object are stored a fixed distance apart. These sequential storage schemes proved adequate given the functions one wished to perform (access to an arbitrary node in a table, insertion or deletion of nodes within a stack or queue).
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 136
The sequential property of linear list is basic to its definition and use. The simple linear list structure array is found almost in any programming language.
Functions defined to operate on a list :
 insert : insert a new entry into a list
 delete : delete an entry from list
 length : compute length of a list
 next : return the next element in a list
 search : search if an element is in a list
Objectives
At the end of this unit, you will be able to understand the:
 Introduction of Linear list
 Different types of Linked List and its Operations.
 Implementation of Singly-Linked Lists in C
 Implementation of Circular singly linked list in C
 Implementation of Doubly linked lists in C
5.1 Linear list
A linear list is a sequence of n>= 0 nodes x[1], x[2], x[3]…….x[n] whose essential structural properties involve only the relative positions between items as they appear in a line. The only thing we care about in such structures are the facts that, if n>0, x[1] is the first node and x[n] is the last one. If 1<k<n, the kth node x[k] is preced by x[k-1] and followed by x[k+1].
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 137
List
Linear lists can be divided in two categories:
In a restricted list, data can only be added or deleted at the ends of a structure and processing is restricted to operations at the end of the lists. Two restricted list structures are First in First Out (FIFO) Stacks and Last In First Out (LIFO) Queue.
There are four operations performed on linear lists,
1. Insertion
2. Deletion
3. Retrieval
4. Traversal.
The first three apply to all lists. List traversal is not applicable to restricted lists.
Depending on the type of linear list, an insertion can be made at the beginning of the list, or at the end of the lists. While there are no restrictions on inserting data into random lists, Computers data generally insert data at the end of lists. The few applications where random lists are used are found
1
2
3
4
5
Linear Lists
Restricted
LIFO
FIFO
General
Random General
Ordered
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 138
either in data gathering applications, or in which the applications require randomness such as simulation studies or games. When inserting data into ordered lists, the data must be inserted so that the ordering is maintained. This may require data at the beginning, end of the list, or middle of the list. In case of inserting in middle inserting, search algorithm is used.
Deletion from general list requires that the list be searched for the data to be deleted. Any sequential search can be used to locate data. Once the data is located, it is removed from the list.
List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the lists.
List traversal is a special case of retrieval in which all the elements are retrieved in a sequence. List traversal requires a looping algorithm rather than a search. Each execution processes one element in the list. The loop terminates when all elements have been processed.
5.2 Linked list
A linked-list is a collection of records, called nodes, each containing at least one field (member) that gives the location of the next node in the list. In the simplest case, each node contains two members; a ‘data member’ (the value of the list item) and a ‘link member’ (a value locating the next node).
The linked list is a very flexible dynamic data structure. It is a low-level structure upon which high-level data structures can be built.
5.2.1 Typical basic linked-list operations
 Create : Makes a new linked list
 Insert : Puts a new node in its place in the list. (Can be coded to take place at the beginning of the list, or at the end of the list or based on seeking to target value).
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 139
 Remove : Remove a node from the list.
 Traverse : this function allow user to visit each node in the list. (The
purpose of the visit is defined by the list user, and it is certain to vary
from application to application).
 isEmpty : This function returns a true/false indication of whether or not
there are any nodes in the list.
 isFull : This function returns a true/false indication of whether or not the
list is full. ( When the data structure is static, this operation may perform
a test. In the typical dynamic list, it simply returns false).
5.2.2 Singly-Linked Lists
The singly-linked list is the most basic of all the linked data structures. A
singly-linked list is simply a sequence of dynamically allocated objects, each
of which refers to its successor in the list. Despite this obvious simplicity
there are myriad implementation variations. Figure shows several of the
most common singly-linked list variants.
The basic singly-linked list is shown in Figure (a). Each element of the list
refers to its successor and the last element contains the null reference. One
variable, labeled head in Figure (a), is used to keep track of the list.
Figure: Singly linked list variations
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 140
The basic singly-linked list is inefficient in those cases when we wish to add elements to both ends of the list. While it is easy to add elements at the head of the list, to add elements at the other end (the tail) we need to locate the last element. If the basic singly- linked list is used, the entire list needs to be traversed figure : Singly linked list variations in order to find its tail.
Figure (b) shows a way in which to make adding elements to the tail of a list more efficient. The solution uses a second variable, tail, which refers to the last element of the list. Of course, this time efficiency comes at the cost of the additional space used to store the variable tail.
The singly-linked list labeled (c) in Figure illustrates two common programming tricks. There is an extra element at the head of the list called a sentinel. This element is never used to hold data and it is always present. The principal advantage of using a sentinel is that it simplifies the programming of certain operations. For example, since there is always a sentinel standing guard, we never need to modify the head variable. Of course, the disadvantage of a sentinel such as that shown in (c) is that extra space is required, and the sentinel needs to be created when the list is initialized.
The list (c) is also a circular list. Instead of using a null reference to demarcate the end of the list, the last element of the list refers to the sentinel. The advantage of this programming trick is that insertion at the head of the list, insertion at the tail of the list, and insertion at an arbitrary position of the list are all identical operations.
Of course, it is also possible to make a circular, singly-linked list that does not use a sentinel. Figure (d) shows a variation in which a single variable is used to keep track of the list, but this time the variable, tail refers to the last element of the list. Since the list is circular in this case, the first element follows the last element of the list. Therefore, it is relatively simple to insert
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 141
both at the head and at the tail of this list. This variation minimizes the
storage required, at the expense of a little extra time for certain operations.
Figure illustrates how the empty list (i.e., the list containing no list elements)
is represented for each of the variations given in Figure. Notice that the
sentinel is always present in list variant (c). On the other hand, in the list
variants which do not use a sentinel, the null reference is used to indicate
the empty list.
Empty singly-linked lists.
In the following sections, we will present the implementation details of a
generic singly- linked list. We have chosen to present variation (b)-the one
which uses ahead and a tail - since is supports append and preapend
operations efficiently.
Example 1 : Illustrate the Singly Linked list operations using Pointers.
# Singly Linked List using Pointers
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define NewNode (Node *)malloc( sizeof(Node))
typedef struct node
{
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 142
int item;
struct node *next;
}Node;
Node * Create(Node *);
void Display(Node *);
int Count(Node *);
Node* Insert(Node *);
Node * Delete{Node *);
void Search(Node*);
void main( )
{
Node *ptr=NULL,*start=NULL;
int ch,cnt;
start=Create( start );
Display(start),
do
{
printf("\n Singly Linked List Operations \n");
printf(" 1-> Count\n");
printf("2-> Display\n");
printf("3-> Insert\n");
printf("4-> Delete\n");
printf("5-> Search\ n");
printf("\nenter w. choice \n").
scanf("%d",&ch);
switch( ch)
{
case 1 :
printf("\nNo of Nodes = %d\n",Count (start));
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 143
break;
case 2:
Display(start);
break;
case 3:
start= Insert( start) ;
break;
case 4:
start=Delete(start);
break;
case 5:
Search(start);
break;
default:
printf("Invalid Selection \n");
break;
}
}while(ch!=0);
}
Node * Create(Node *s)
{
Node *tmp=NULL, *t1 =NULL;
int num;
t1-=s;
do
{
printf("\nEnter the element\n");
scanf("% d",&num);
if(num!=-99)
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 144
{
tmp= New Node;
tmp->item=num;
tmp->next= NULL;
if( s== NULL )
s=t1=tmp;
else
{
tl->next=tmp;
tl =tl->next.
}
}
else
printf("Linked List Created Successfully \n");
}while(num!=-99);
return(s);
}
void Display(Node *s )
{
if(s== NULL )
printf("MT Linked List \n");
else
{
while(s!=NULL)
{
printf("%5d",s->item);
s=s->next;
}
printf("\n ");
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 145
}
}
int Count(Node *s )
{
int total= 0;
while(s'=NULL)
{
total++;
s=s->next. ,
}
return(total);
}
Node * Insert(Node *s)
{
Node *t1 =NULL, *tmp=NewNode;
int pos;
printf(“Enter the position to be inserted \n.);
scanf(“% d.,&pos );
if(pos>0 && pos<=Count(s)+ 1)
{
printf("Enter the element to be inserted \n”);
scanf("%d",&tmp->item)
printf(“enter the name \n”); scanf(“%C”,name);
if(pos==l)
{
tmp->next=s;
s=tmp;
}
else
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 146
{
t1=s;
while(pos>2)
{
t1 =t1->next;
pos--;
}
tmp->next=t1->next;
t1->next=tmp;}
}
else
printf("Invalid position \n");
return(s);
}
Node * Delete(Node *s)
{
Node *t1 =s, *tmp=NULL;
int pos;
printf("Enter the position, to be deleted \n");
scanf(“% d",&pos);
if(pos>0 && pos<=Count(s))
{
if(pos== 1 )
{
s=s->next.
free(tl);
}
else
{
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 147
while(pos>2)
{
t1=t1->next.
pos--;
}
tmp=t l->next;
t l->next=tmp->next;
free(tmp);
}
}
else
printf(“Invalid Position \n");
retum(s);
}
void Search(Node *s)
{
int ele;
int f1ag=0;
printf("ente the element to be searched\n");
scanf("%d",& ele);
if(s!=NULL)
{
while(s!=NULL)
{
if( s->item==ele )
{
printf("\n% d is present \n",ele);
flag= 1 ;
}
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 148
s=s->next;
}
if(flag=0)
printf("Element Not Found \n");
}
else
printf("List is MT, Key element can't be searched\n");
}
Self Assessment Questions :
1. Discuss the linked list with its operation.
2. Explain the basic singly linked list with neat diagram.
5.3 Circular singly linked list
In the linked lists discussed so far in earlier sections, the link field of the last
node contained a NULL pointer. In this section, we discuss linear lists again
with slight modification by storing address of the first node in the link field of
the last node. The resulting list is called a circular singly linked list or a
circular list. The pictorial representation of a circular list is shown in
following figure.
The circular lists have some advantages over singly linked lists that are not
circular. In a singly linked list given the address of any node x, only those
nodes which follow x are reachable but, the nodes that precede x are not
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 149
reachable. To reach the nodes that precede x, it is required to preserve a pointer variable say first which contain the address of the first node before traversing. But in circular lists if the address of any node x is known, one can traverse the entire list from that node and so all nodes are reachable.
So, in a circular linked list, the search for the predecessor of the node x can be initiated from x itself and there is no need of a pointer variable that points to the first node of the list. The disadvantage of these circular lists is that when proper care is not taken it is possible that we may end up in an infinite loop unless proper care is taken to detect the end of the list.
Since the list is circular, any node can be considered as the first node and its predecessor is considered as a last node. The following two conventions can be used:
1. A pointer variable first can be used to designate the starting point of the list. Using this approach, to get the address of the last node, the entire list has to be traversed from the first node.
2. In the second technique, a pointer variable last can be used to designate the last node and the node that follow last, can be designated as the first node of the list. So, we use the second approach in our discussions for convenience.
Note: Whatever operations are possible using singly linked lists, all those operations can be performed using circular lists also. A circular list can be used as a stack, queue or a deque. The basic operations required to implement these data structures are insert_ front, insert_ rear, delete_ front, delete_ rear and display. Let us implement these functions one by one.
5.3.1 Insert a node at the front end
Consider the list shown in following fig. (a). The list contains 4 nodes and a pointer variable last contains address of the last node.
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 150
Step 1: To insert an item 50 at the front of the list, obtain a free node temp
from the availability list and store the item in info field as shown in dotted
lines in above fig. (b). This can be accomplished using the following
statements
temp = getnode( );
temp->info = item;
Step 2: Copy the address of the first node(i.e., last->link) into link field of
newly obtained node temp and the statement to accomplish this task is
temp->link = last->link;
Step 3: Establish a link between the newly created node temp and the last
node. This is achieved by copying the address of the node temp into link
field of last node. The corresponding code for this is
last->link = temp;
Now, an item is successfully inserted at the front of the list. All these steps
have been designed by assuming that the list is already existing. If the list is
empty, make temp itself as the last node and establish a link between the
first node and the last node. Repeatedly insert the items using the above
procedure to create a list. The C function to insert an item at the front of the
circular linked list is shown in below example.
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 151
Example 1: Function to insert an item at the front end of the list.
NODE insert_ front (int item, NODE last)
{
NODE temp;
temp = getnode( ); /* Create a new node to be inserted */
temp->info = item;
if (last = = NULL) /* Make temp as the first node */
last = temp;
else temp->link = last->link;
last->link = temp; /* link last node to first node */
return last; /* Return the last node */
}
5.3.2 Insert a node at the rear end
Consider the list shown in below fig. (a). This list contains 4 nodes and last is a pointer variable that contains the address of the last node.
Figure to insert at the rear end
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 152
Let us insert the item 80 at the end of this list. After successfully inserting 80, the list shown in fig.(c) is obtained. Following steps shown below to insert an item at the rear end of the list.
Step 1: Obtain a free node temp from the availability list and store the item in info field as shown in dotted lines in fig. (b). This can be accomplished using the following statements
temp = getnode( );
temp->info = item;
Step 2: Copy the address of the first node(i.e., last->link) into link field of newly obtained node temp and the statement to accomplish this task is
temp->link = last->link; .
Step 3: Establish a link between the newly created node temp and the last node. This is achieved by copying the address of the node temp into link field of last node. The corresponding code for this is
last->link = temp;
Step 4: The new node is made as the last node using the statement:
return temp; /* make new node as the last node */
These steps have been designed by assuming the list is already existing. If the list is empty make temp itself as the-first node as well as the last node. The C function for this is shown in below example.
Example : Function to insert an item at the rear end of the list
NODE insert_ rear (int item, NODE last)
{
NODE temp;
temp = getnode( ); /* Create a new node to be inserted */
temp->info = item;
if ( last == NULL) /* Make temp as the first node */
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 153
last = temp;
else /*Insert at the rear end */
temp->link = last->link;
last->link = temp; /* link last node to first node */
return temp; /* Make the new node as the last node */
}
Note: Compare the functions insert_ front( ) and insert_ rear( ). All
statements in both the functions are same except that in insert_
front( )function, address of last node is returned and in the function insert_
rear( ) address of the new node is returned.
5.3.3 Delete a node from the front end
Consider the list shown in below figure. This list contains 5 nodes and last is
a pointer variable that contains the address of the last node.
Figure to delete an item from the front end
To delete the front node (see the sequence of numbers 1,2,3 shown in
above fig. ), the steps to be followed are
Step 1: first = last->link; /* obtain address of the first node */
Step 2: last->link = first->link; /* link the last node and new first node
*/ Step 3: printf ("The item deleted is %d\n", first->info);
Freenode (first); /*delete the old first node */
Now, the node identified as first node is deleted. These steps have been
designed by assuming the list is already existing. If there is only one node,
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 154
delete that node and assign NULL to last indicating the list is empty. The code corresponding to this is can be
/* If there is only one node, delete it */
if ( last->link = = last )
{
printf ("The item deleted is %d\n", last->info);
freenode(last);
last = NULL;
return last;
}
All these steps designed so far have to be executed provided the list is not empty. If the list is empty, display the appropriate message. The complete code to delete an item from the front end is shown in below example.
Example : Function to delete an item from the front end
NODE delete_ front(NODE last)
{
NODE temp, first;
if ( last = = NULL )
{
printf("List is empty\n");
return NULL;
}
if ( last->link = = last) /* Only one node is present */
{
printf("The item deleted is %d\n", last->info);
freenode (last);
return NULL;
}
/* List contains more than one node */
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 155
first = last->link; /* obtain node to be deleted */
last->link = last->link; /*Store new first node in link of last */
printf ("The item deleted is %d\n", first->info);
freenode (first); /* delete the old first node */
return last;
}
5.3.4 Delete a node from the rear end
To delete a node from the rear end, it is required to obtain the address of the predecessor of the node to be deleted. Consider the list shown in fig. where the pointer variable last contains the, address of the last node.
Figure to delete a node from the rear end
To delete the node pointed to by last, the steps to be followed are:
Step 1: Obtain the address of the predecessor of the node to be deleted. This can be accomplished by traversing from the first node till the link field of a node contains address of the last node. The code corresponding to this is
prev = last->link;
while ( prev->link != last )
{
prev = prev->link;
}
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 156
Step 2: The first node and the last but one node (i.e., prev) are linked. This can be accomplished using the statement
prev->link ='last->link;
Step 3: The last node can be deleted using the statement
freenode (last);
After executing these statements, return the node pointed to by prev as the new last node using the statement
return(prev);
All these steps have been designed by assuming that the list is already existing. If there is only one node, delete that node and assign NULL to the pointer variable last indicating that the list is empty. If the list is empty in the beginning display the appropriate message. The C function to delete an item from the rear end of circular list is shown in below example.
Example : Function to delete an item from the rear end
NODE delete_ rear (NODE last)
{
NODE prev;
if ( last = = NULL )
{
printf("List is empty\n");
return NULL; }
if ( last->link = = last) /* Only one node is present */
{
printf("The item deleted is %d\n", last->info);
freenode(last);
return NULL;
}
/* Obtain address of previous node */
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 157
prev = last->link;
while( prev->link != last )
{
prev = prev->link;
}
prev->link = last->link; /* prev node is made the last node */
printf("The item deleted is %d\n", last->info);
freenode(last); /* delete the old last node */
return prev; /* return the new last node */
}
The C function to display the contents of circular list is shown in below example and the reader is required to understand how the function is working.
Example: Function to display the contents of the circular queue
void display(NODE last)
{
NODE temp;
if ( last == NULL)
{
printf("List is empty\n");
return;
}
printf("Contents of the list is\n ");
for (temp = last->link; temp != last; temp = temp->link)
printf("%d ",temp->info);
printf("%d\n", temp->info);
}
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 158
 The C program to implement deque using circular linked list is shown in below example
Example : Program to implement deque using circular list
#include <stdio.h>
#include <alloc.h>
#include <process.h>
struct node
{
int info;
struct node *link;
};
typedef struct node* NODE;
/* function to get anode from the availability list */
/* function to return node to availability list */
/* function to insert an item at the front end */
/* function to insert an item at the rear end */
/* function to delete an item from the front end */
/* function to delete an item from the rear end */
/* function to display the contents of the list */
void main( )
{
NODE last;
int choice, item;
last = NULL;
for (;;)
{
printf(" 1 : Insert_ Front 2: Insert_ Rear\n ");
printf("3 :Delete_ Front 4: Delete_ Rear\n ");
printf("5: Display 6: Exit\n");
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 159
printf("Enter the choice\n");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%d", &item);
last = insert_ front (item, last);
break;
case 2:
printf("Enter the item to be inserted\n");
scanf("%d", &item);
last = insert_ rear (item, last);
break;
case 3:
last = delete_ front(last);
break;
case 4:
last = delete_ rear(last); break;
case 5:
display(last);
break;
default:
exit(0);
}
}
}
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 160
Note: Some of the disadvantages of singly linked lists/circular lists are:
1. Using singly linked lists and circular lists it is not possible to traverse the
list backwards.
2. To find the predecessor, it is required to traverse the list from the first
node in case of singly linked list. In case of circular list, the predecessor
can be obtained by traversing the whole list from the node specified. For
example, if the position of the current node is 15, to find the position of
node 14, the whole list has to be traversed.
All these disadvantages can be overcome by using doubly linked lists.
Self Assessment Questions :
1. Explain the Circular singly linked list with neat diagram.
2. Explain the steps to insert a node at the rear end in circular singly linked
list.
3. Explain the steps to delete the node pointed to by last.
5.4 Doubly linked lists
Figure Doubly linked lists
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 161
In singly linked lists (including circular lists), each node contains the address of the next node. If there is one more field which contains the address of the previous node, it is possible to obtain the address of the predecessor of a node specified. Using such lists, it is possible to traverse the list in forward and backward directions. A list where both forward and backward traversal is possible
should have two link fields. The link field, which contains address of the left node is called left link denoted by llink and the link field which contains the address of the right node is called right link and is denoted by rlink. Such a list where each node has two links is called a doubly linked list or a two way list.
The list can be traversed from the first node whose address is stored in a pointer variable first, to the last node in the forward direction. It can also be traversed from the last node whose address is stored in a pointer variable last, to the first node in backward direction. The pictorial representation of a doubly linked list is shown in above figure.
In the doubly linked list shown in figure (a) the link field of the leftmost node and link field of rightmost node points to NULL. The list shown in fig. (b) is a doubly linked circular list. In this list, the left link of the left most node contains address of the right most node and the right link of the right most node contains address of the left most node. The list shown in fig. (c), is a doubly linked circular list with a header node. In this type of list, the left link of a header node contains address of the last node and right link of last node contains address of the header node. An empty list with a header node can be represented as shown in fig.(d), where the left link and right link of a header node points to itself.
All those problems that can be solved using singly linked lists can be solved using doubly linked lists. It is left to the reader to implement all the problems
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 162
solved so far, using doubly linked lists and doubly linked circular list. Given
any problem let us implement them using doubly linked lists and with a
header node. Using a header node, problems can be solved very easily and
effectively.
5.4.1 Insert a node at the front end
Consider the list shown in below fig. To insert a node pointed to by temp at
the front of the list, address of the first node i.e., pointed to by cur should be
known. This can be accomplished by using the statement
cur = head->rlink;
The node pointed to by temp can be easily inserted between header node
and the node pointed to by cur (follow the dotted lines). This can be
accomplished by using the following statements.
head->rlink = temp;
temp->llink =head;
temp->rlink = cur;
cur->llink = temp;
Figure to insert a node at the front end
The C function to insert at the front of a doubly linked circular list with a
header node is shown in below example.
Example : Function to insert a node at the front end of the list
NODE insert_ front (int item, NODE head)
{
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 163
NODE temp, cur;
/* Node to be inserted */
temp = getnode( );
temp->info = item;
/* obtain address of first node */
cur = head->rlink;
/* Insert between header node and first node */,
head->rlink = temp;
temp->llink = head;
temp->rlink = cur;
cur->llink = temp;
/* return the header node */
return head;
}
5.4.2 Insert a node at the rear end
To insert a node at the rear end of the list, consider the list shown in fig.
and try to write the corresponding code. After writing the code compare this
with the function insert_ front ( ). Note that the two functions are same
except that llink and rlink have been exchanged. The reader should know
the simplicity of the code using the header node. The C function to insert an
item at the rear end of the list is shown in example.
Figure to insert a node at the rear end
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 164
Example : Function to insert an item at the rear end
NODE insert_ rear(int item, NODE head)
{
NODE temp, cur;
/* Node to be inserted */
temp = getnode ( );
temp->info = item;
/* obtain address of the last node */
cur = head->llink;
/* Insert at the end of the list */
head->llink = temp;
temp->rlink = head;
temp->llink = cur;
cur->rlink = temp;
/* return the header node */
return head;
}
5.4.3 Delete a node from the front end
Consider the list shown in below fig. Find the address of the first node to be
deleted using the statement:
cur = head->rlink;
Also obtain the successor of the node to be deleted using the statement:
next = cur->rlink;
Figure to delete a node at the front end
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 165
Once the addresses of the node to be deleted, its predecessor and successor are known, following the sequence of numbers shown in above fig. the node at the front end can be deleted. The steps to be followed are shown below.
Step 1, 2: Establish a link between the header node and successor of the node to be deleted i.e., next in both directions. This can be accomplished using the statement
head ->rlink = next;
next->llink = head;
Step 3: Once these statements are executed, the node to be deleted i.e., cur is isolated and it can be deleted. The corresponding statements are:
printf("The item deleted is %d\n", cur->info);
freenode(cur);
Finally return the address of the header node. Note that all these steps have been designed by assuming list is already existing. If list is empty display the appropriate message. The C function to delete an item from the front end of the list is shown in below example.
Example: Function to delete a node from the front end
NODE delete_ front (NODE head)
{
NODE cur, next;
if ( head->rlink = = head)
{
printf("Deque is empty\n");
return head;
}
cur = head->rlink; /* first bode is known */
next = cur->rlink; /* second node which will be the first node*/
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 166
/* adjust pointers and delete the node */
head->rlink = next;
next->llink = head;
printf("The node to be deleted is %d\n", cur->info);
freenode(cur);
return head;
}
Example : Program to implement insert at front/rear/before/after a node, to delete front/rear/based on item/all nodes etc.
# include<studio.h>
# include < alloc.h>
# include < process.h>
struct nodded
{
int info;
struct node * llink;
struct node* rlink;
};
typedefs struct node * NODE;
/* function to insert at the front end */
/* function to insert at the rear end*/
/* function to delete the first node */
/* function to display the contents of the list */
void display (NODE head)
{
NODE temp;
if(head->rlink = = head )
{
priritf("Deqye is empty\n");
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 167
return;
}
printf("Contents of the deque is\n");
for(temp = head->rlink; temp != head; temp = temp->rlink)
printf("%d ",temp->info);
printf ("\n");
}
void main( )
{
NODE head;
int choice, item;
head = getnode();
head->rlink = head;
head->llink = head;
for (;;)
{
printf(" 1 : Insert_ front 2: Insert_ rear\n ");
printf("3: Delete_ front 4: Delete_ rear\n");
printf("5: Display ");
printf("6: Exit\n");
printf("Enter the choice\n");
scanf(" %d " ,&choice );
switch(choice)
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%d",& item);
head = insert_ front(item, head);
break;
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 168
case 2:
printf("Enter the item to be inserted\n");
scanf("%d",& item);
head = insert_ rear(item, head);
break;
case 3:
head = delete_ front(head);
break;
case 4:
head = delete_ rear(head);
break;
case 5:
display(head);
break;
default; exit(0);
}
}
}
Self Assessment Questions:
1. Discuss the doubly linked list with neat diagram.
2. Write C function to insert a node at the front end of the list.
3. Write a steps to delete a node from the front end with neat diagram.
5.5 Summary
In this unit discussed the various types of list and its operations. The sequential property of linear list is basic to its definition and use. The simple linear list structure array is found almost in any programming language. The linked list is a very flexible dynamic data structure. It is a low-level structure upon which high-level data structures can be built. In this unit discussed the
Data Structures using „C‟ Unit 5
Sikkim Manipal University Page No.: 169
various linked list operation implementation using C for Circular singly linked list, Doubly linked list.
5.6 Terminal Questions
1. What is List ? Discuss the functions defined to operate on List.
2. Explain the typical basic operated on linked list.
3. Explain the singly linked list with neat diagram.
4. Illustrate the „C‟ program for singly link list operators using points.
5. Write note on Circular Singly Linked List.
6. Explain Insert/Delete a node at the rear, front end from circular singly linked list.
7. Write „C‟ program to implement deque using circular linked list.
8. Explain the doubly linked list with neat diagram.
9. Explain the operation of insert and delete a node from the doubly linked list.