Chapter 6
Linked Lists
CHAPTER OUTLINE
6.3 Operations on Linked Lists
6.4 Variations of Linked Lists
6.5 The Concept of Dummy Nodes
6.1 INTRODUCTION
An array is a very simple and extremely useful data structure. A large number of applications based on stacks and queues can be easily implemented with the help of arrays. Lists and tables have natural similarity with one- and two-dimensional arrays. Though the allocation of space is sequential in an array, the access to its elements is random. For a given index the element can be accessed in a time, independent of its location in the array.
However, there are many problems associated with this data structure. Some of the important problems are as follows:
- An array is a static data structure and, therefore, its size should be known in advance before its usage.
- If a list of data items is to be stored, then an array of approximate size is used, i.e., the array has to be large enough to hold the maximum amount of data one could logically expect. This is totally a guess work and can result in overflow or wastage of main memory.
- What if the number of elements in the list is not known in advance?
- Insertion or deletion operations in an array, except from the end, are a costly exercise. These operations require large number of shifting of elements in one direction or the other. This a very time consuming exercise.
The above problems can be dealt with the help of linked structures, discussed in the subsequent sections.
6.2 LINKED LISTS
Linked structures are a completely different way to represent a list of items. Each element of the list is made to point to the next element in the list as shown in Figure 6.1(a).
Fig. 6.1 Linked representation of a list
An element in the list is called a node. The node is a self-referential structure, having two parts: Data and Next as shown in Figure 6.1(b). The Data part contains the information about the element and the Next part contains a pointer to the next element or node in the list. For example, in Figure 6.1(a), a list consisting four names (“Preksha”, “Sagun”, “Bhawna”, and “Ridhi”) is represented using linked structures. Such a list is called linked list or a linear linked list or a singly linked list.
Linked list is a series of nodes. Each node has two parts: data and next. The data part contains the information about the node and the next part is a pointer that points to next node. The next of last node points to NULL.
It may be noted that the list is pointed by a pointer called ‘List’. Currently List is pointing to a node containing the name ‘Preksha’, the next part of which is pointing to ‘Sagun’, the next of which is pointing to ‘Bhawna’, and so on.
By convention, a node X means that the node is being pointed by a pointer X as shown in Figure 6.2. In an algorithm, the data part of X is written as DATA(X) and the next part is written as NEXT(X).
Fig. 6.2 A node called X
Let us now insert a new node containing data called ‘Samridhi’ between ‘Preksha’ and ‘Sagun’. This insertion operation can be carried out by the following steps:
Step
1. Get a node called ptr.
2. DATA (ptr) = ‘Samridhi‘
3. NEXT (ptr) = NEXT(List)
4. NEXT(List) = ptr
The third step means that the Next pointer of ptr should point to the same location that is currently being pointed by Next of List.
The effect of above steps (1–4) is shown in Figure 6.3.
Fig. 6.3 Insertion of a node in the linked list
It may be noted that the insertion operation is a very simple and easy operation in a linked list because, unlike arrays, no copying or shifting operations are required.
Similarly, it is easy to delete an element from a linked list. To delete Bhawna from the list given in Figure 6.3, we need only to redirect the next pointer of Sagun to point to Ridhi as shown in Figure 6.4. This can be done by the following the following steps:
Step
1. Point a pointer called ptr1 to the node containing the name ‘Bhawna’.
2. Point a pointer called ptr2 to the node containing the name ‘Sagun’.
3. Next (ptr2) = Next(ptr1)
4. Return ptr1
Fig. 6.4 Deletion of a node
The effect of the above code segment is shown in Figure 6.4.
From the above discussion, it is clear that unlike arrays, there is no longer a direct correspondence between the logical order of elements present in a list and the way the nodes are arranged physically in the linked list (see Figure 6.5).
Fig. 6.5 Logical versus physical order in a linked list
The physical order of the nodes shown in Figure 6.5 is “I My Love India” whereas the logical order is “I Love My India”. It is because of this feature that a linked list offers a very easy way of insertions and deletions in a list without the physical shifting of elements in the list. While manipulating a linked list, the programmer keeps in mind only the logical order of the elements in the list. Physically, how the nodes are stored in the memory is neither known to nor the concern of the programmer.
6.3 OPERATIONS ON LINKED LISTS
The linked list is a dynamic data structure. The following operations are associated with linked lists:
- Creation of a linked list
- Traversing a linked list
- Searching in a linked list
- Inserting a node in a linked list
- Deleting a node from a linked list
6.3.1 Creation of a Linked List
From the above discussion, we know that a node of a linked list is essentially a structure because it contains data of different types. In addition to the information part, it contains a pointer that can point to a node, i.e., to itself or to some other node. Such structures are called self-referential structures.
6.3.1.1 Self-referential Structures
When a member of a structure is declared as a pointer to the structure itself, then the structure is called self-referential structure. Consider the following declaration:
struct chain { int val;
struct chain *p;
};
The structure called ‘chain’ consists of two members: val and p. The member val is a variable of type int whereas the member p is a pointer to a structure of type chain. Thus, the structure chain has a member that can point to a structure of type chain or may be itself. This type of self-referencing structure can be viewed as shown in Figure 6.6.
Fig. 6.6 Self-referential structure chain
Since pointer p can point to a structure variable of type chain, we can connect two such structure variables, A and B, to obtain a linked structure as shown in Figure 6.7.
Fig. 6.7 Linked structure
The linked structure given in Figure 6.7 can be obtained by the following steps:
- Declare structure chain.
- Declare variables A and B of type chain.
- p(A) = B
These steps have been coded in the program segment given below:
struct chain { /* declare structure chain */
int val;
chain *p;
};
struct chain A, B; /* declare structure variables A and B */
A.p = &B; /* connect A to B*/
From Figure 6.7 and the above program segment, we observe that the pointer p of structure variable B is dangling, i.e., it is pointing to nowhere. Such pointer can be assigned to NULL, a constant indicating that there is no valid address in this pointer. The following statement will do the desired operation:
B.p = NULL;
The data elements in this linked structure can be assigned by the following state-ments:
A.val = 50;
B.val = 60;
The linked structure now looks like as shown in Figure 6.8.
Fig. 6.8 Value assignment to data elements
We can see that the members of structure B can be reached by the following two methods:
- From its variable name B through dot operator.
- From the pointer p of variable A because it is also pointing to the structure B. However, in this case the arrow operator (−>) is needed to access the field called val as shown below.
Consider the statements given below:
printf (“
the contents of member val of B = %d”, B.val);
printf (“
the contents of member val of B = %d”, A −> p.val);
Once the above statements are executed, the output would be:
The contents of member val of B = 60
The contents of member val of B = 60
The linked structures have great potential and can be used in numerous programming situations such as lists, trees, etc. The major advantage of linked structures is that the pointers can be used to allocate dynamic memory. Consider the following declaration:
struct chain *ptr;
The above statement declares a pointer called ptr, which can point to a structure of type chain [see Figure 6.9 (a)]. Lets us use ptr to take one such structure through dynamic allocation with the help of malloc() function of ‘C’. From Chapter 5, we know that the malloc() function needs the size of the memory that is desired by the programmer. Therefore, in the first step, given below, the size of the structure has been obtained and in the second step the memory of that size has been asked through malloc() function.
Fig. 6.9 Dynamic allocation of a structure
Size = sizeof (struct chain);
ptr = (struct student *) malloc (Size);
The effect of the above statements is shown in Figure 6.9 (b). It may be noted that the node pointed by ptr has no name. In fact all dynamic memory allocations are anonymous.
Let us now use self-referential structures to create a linked list of nodes of structure type given in Figure 6.10. While creating the linked list, the student data is read. The list is also travelled to print the data.
Fig. 6.10 The self-referential structure ‘student’
We will use the following self-referential structure for the purpose of creating a node of the linked list:
struct stud {
char name [15];
int roll;
struct stud*next;
};
The required linked list would be created by using three pointers—first, far, and back. The following algorithm would be employed to create the list:
Algorithm createLinkList()
{
Step
1. Take a new node in pointer called first.
2. Read first −> name and first −> roll.
3. Point back pointer to the same node being pointed by first, i.e., back = first.
4. Bring a new node in the pointer called far.
5. Read far −> name and far −> roll.
6. Connect next of back to far, i.e., back −> next = far.
7. Take back to far, i.e., back = far.
8. Repeat steps 4 to 7 till whole of the list is constructed.
9. Point next of far to NULL, i.e., far −> next = NULL.
10. Stop.
}
The effect of the above steps is shown in Figure 6.11.
Fig. 6.11 Creation of a linked list
The required program is given below:
#include <stdio.h>
#include <alloc.h>
struct student {
char name [15];
int roll;
struct student *next;
};
struct student *create(); /* Function that creates the linked list */
void dispList(struct student * First); /* Function to display linked list */
void main()
{
struct student *First;
First = create();
dispList(First);
}
struct student *create()
{
struct student * First,*Far, *back;
int N,i;
int Sz;
Sz = sizeof (struct student);
printf(“
Enter the number of students in the class”);
scanf(“%d”, &N);
if ( N == 0) return NULL; /* List is empty */
/* Take first node */
First = (struct student *) malloc (Sz);
/* Read the data of the first student */
printf (“
Enter the data”);
printf (“
Name: ”); fflush(stdin); gets(First->name);
printf (“
Roll: ”); scanf(“%d”, &First->roll);
First->next = NULL;
/* point back where First points */
back = First;
for (i =2; i <=N; i++)
{ /* Bring a new node in Far */
Far = (struct student *) malloc (Sz);
/* Read Data of next student */
printf (“
Name: ”); fflush(stdin); gets(Far->name);
printf (“
Roll: ”); scanf(“%d”, &Far->roll);
/* Connect Back to Far */
back->next = Far;
/* point back where Far points */
back = Far;
} /* Repeat the process */
Far->next = NULL;
return First; /* return the pointer to the linked list */
}
/* Print the created linked list */
void dispList(struct student *First)
{ struct student *Far;
Far = First; /* Point to the first node */
printf (“
The List is ….”);
while (Far != NULL)
{
printf (“ %s - %d, ”, Far->name, Far->roll);
/* Point to the next node */
Far = Far->next;
}
}
It may be noted that the next pointer of the last node of a linked list always points to NULL to indicate the end of the list. The pointer First points to the beginning of the list. The address of an in between node is not known and, therefore, whenever it is desired to access a particular node, the travel to that node has to start from the beginning.
6.3.2 Travelling a Linked List
Many a times, it is required to travel whole or a part of the list. For example, the operations such as counting of nodes, processing of information of some nodes, or printing of the list, etc. requires traversal of the list.
Consider the linked list shown in Figure 6.12. It is pointed by First. Let us travel this list for the purpose of counting the number of nodes in the list.
Fig. 6.12 The list pointed by First
Let us use a pointer ptr to travel the list. A variable called count would be used to count the number of nodes in the list. The travel stops when a NULL is encountered. The following algorithm called travelList() travels the given list pointed by First.
Algorithm travelList()
{
Step
1. if First == NULL then { print "List Empty”; Stop}
2. ptr = First; /* ptr points to the node being pointed by First */
3. count = 0;
4. while (ptr != Null)
{
4.1 count = count + 1;
4.2 ptr = NEXT(ptr);
}
5. print "The number of nodes =”, count;
6. End
In the above algorithm, step 4.2, given below, is worth noting:
ptr = NEXT(ptr)
The above statement says that let ptr point to the same location which is currently being pointed by NEXT of ptr. The effect of this statement on the list of Figure 6.12 is shown in Figure 6.13.
Fig. 6.13 Significance of the operation ptr = NEXT (ptr)
It may be noted that the step 4.2 takes the ptr to next node. Since this statement is within the scope of the while loop, ptr travels from the First to the NULL pointer, i.e., the last node of the list.
Example 1: Write a program that travels a linked list consisting of nodes of following struct type. While traveling, it counts the number of nodes in the list. Finally, the count is printed.
struct student {
char name [15];
int roll;.
struct student *next;
};
Solution: A linked list of nodes of student type would be created by using a function called create(). The nodes would be added to the list until the user enters a roll number less than or equal to 0, i.e., (roll <= 0). A function countNode() based on the algorithm travelList() would be used to travel and count the nodes in the list.
The required program is given below:
/* This program travels a linked list and counts the number of nodes */
#include <stdio.h>
#include <alloc.h>
struct student {
char name [15];
int roll;
struct student *next;
};
struct student *create();
int countNode(struct student *First);
void main()
{
int count;
struct student *First;
First = create();
count = countNode(First);
printf(“
The number of nodes = %d”, count);
}
/* This function creates a linked list */
struct student *create()
{
struct student *First, *Far, *back;
int i;
int Sz;
Sz = sizeof (struct student);
/* Take first node */
First = (struct student *) malloc (Sz);
/* Read the data of the first student */
printf (“
Enter the data of the first student”);
printf (“
Name: ”); fflush(stdin); gets(First->name);
printf (“
Roll: ”); scanf(“%d”, &First->roll);
First->next = NULL;
if (First->roll <=0){
printf (“
Nodes = 0”);
First = NULL;
exit(1);} /* Empty list*/
/* point back where First points */
back = Far = First;
while (Far->roll >0)
{ /* Bring a new node in Far */
Far = (struct student *) malloc (Sz);
/* Read Data of next student */
printf (“
Name: ”); fflush(stdin); gets(Far->name);
printf (“
Roll: ”); scanf(“%d”, &Far->roll);
if (Far->roll <=0) break; /* End of the list */
/* Connect Back to Far */
back->next = Far;
/* point back where Far points */
back = Far;
} /* repeat the process */
back->next = NULL;
return First;
}
/* Travel and count the number of nodes */
int countNode(struct student *First)
{
struct student *ptr;
int count;
count =0;
ptr = First; /* Point to the first node */
while (ptr != NULL)
{
count = count + 1;
/* Point to the next node */
ptr = ptr->next;
}
return count;
}
Example 2: Write a program that travels a linked list consisting of nodes of following struct type. As-sume that the number of students in the list is not known.
struct student {
char name [15];
int roll;
struct student *next;
};
While travelling the list of students, it is split into two sub-lists pointed by two pointers: front_half and back_half. The front_half points to the front half of the list and the back_half to the back half of the list. If the number of students is odd, the extra student should go into the front list.
Solution: The list of students would be created in the same fashion as done in Example 1. The number of nodes would be counted during the creation of the linked list itself. Assume that the linked list is being pointed by First. The following steps would be followed to split the list in the desired manner:
- Compute the middle of the list.
- Point front_half to First.
- Point another pointer Far to First. Let Far travel the list starting from the first and reach to the middle.
- Point back_half to the node that succeeds the middle of the list.
- Attach NULL to the next pointer of the middle node, now pointed by Far.
- Print the two lists, i.e., pointed by front_half and back_half.
The required program is given below:
/* This program travels a linked list and splits it into two halves */
#include <stdio.h>
#include <alloc.h>
struct student {
char name [15];
int roll;
struct student *next;
};
struct student * create (int *count);
struct student * split (struct student *First, int *count);
void dispList(struct student *First);
void main()
{ struct student *First,*front_half, *back_half;
int count;
First = create(&count);
if (count == 1)
{
printf (“
The list cannot be split”);
front_half = First;
}
else
{
front_half = First;
back_half = split (First, &count);
}
printf (“
The First Half…”);
dispList(front_half);
printf (“
The Second Half…”);
dispList(back_half);
}
struct student *create (int *count)
{
struct student *First, *Far, *back;
int Sz;
Sz = sizeof (struct student);
/* Take first node */
First = (struct student *) malloc (Sz);
/* Read the data of the first student */
printf (“
Enter the data of the first student”);
printf (“
Name: ”); fflush(stdin); gets(First->name);
printf (“
Roll: ”); scanf(“%d”, &First->roll);
First->next=NULL;
if (First->roll <=0){
printf (“
Nodes = 0”);
First = NULL;
exit(1);} /* Empty list*/
*count =1;
/* point back where First points */
back = Far = First;
while (Far->roll >0)
{ /* Bring a new node in Far */
Far = (struct student *) malloc (Sz);
/* Read Data of next student */
printf (“
Name: ”); fflush(stdin); gets(Far->name);
printf (“
Roll: ”); scanf(“%d”, &Far->roll);
if (Far->roll <=0) break; /* End of the list */
* count = *count + 1;
/* Connect back to Far */
back->next = Far;
/* point back where Far points */
back = Far;
} /* repeat the process */
back->next = NULL;
return First;
}
struct student *split (struct student *First, int *count)
{
struct student *Far,*back;
int middle,i;
Far = First; /* Point to the first node */
/* Split the list */
{
/* compute the middle */
if ( (*count % 2) == 0) middle = *count/2;
else middle = *count / 2 + 1;
/* Travel the list and split it */
for (i =1; i <= middle; i++)
{
back =Far;
Far = Far->next;
}
back->next = NULL;
return Far;
}
}
/* Print the list */
void dispList(struct student *First)
{
struct student *Far;
Far = First;
while (Far != NULL)
{
printf(“ %s, %d ”, Far->name, Far->roll);
Far = Far->next;
}
}
6.3.3 Searching a Linked List
Search is an operation in which an item is searched in the linked list. In fact, the list is travelled from the first node to the last node. If a visited node contains the item, then the search is successful and the travel immediately stops. This means that in the worst case, whole of the list would be travelled. An algorithm for searching an item ‘X’ in the list is given below.
In this algorithm a linked list, pointed by First, is travelled. While travelling, the data part of each visited node is compared with the item ‘X’. If the item is found, then the search stops otherwise the process continues till the end of the list (i.e., NULL) is encountered. A pointer ptr is used to visit the various nodes of the list.
Algorithm searchList()
{
Step
1. if Front == NULL {
print “List Empty”; exit();}
2. Read the item X
3. ptr = First;
4. flag = 0;
5. while (ptr != NULL)
{
5.1 if ( X== DATA (First) then { flag = 1; break; }
5.2. ptr = NEXT(ptr);
}
6. if (flag ==1) then print "Item found" else print "Item not found"
7. Stop
}
Example 3: Modify program of Example 1 such that the program searches the record of a student whose roll number is given by the user.
Solution: Instead of writing the code for creation and display of linked lists again and again, now onwards we would use the functions create() and dispList() developed in earlier programs. A new function based on algorithm searchList() would be written and used to search the record of a student.
The required program is given below:
/* This program searches an item in a linked list */
#include <stdio.h>
#include <alloc.h>
#include <process.h>
struct student {
char name [15];
int roll;
struct student *next;
};
struct student *create();
int searchList(struct student *First, int Roll);
void main()
{
struct student *First;
int Roll, result;
First =create();
printf (“
Enter the Roll of the student to be searched”);
scanf(“%d”, &Roll);
result = searchList(First, Roll);
if (result == 1)
printf (“
The Student found”);
else
printf (“
The Student not found”);
}
struct student *create() /* Any of the create() function designed in above examples can be used */
{
}
int searchList(struct student *First, int Roll)
{ struct student *Far;
int flag;
Far = First; /* Point to the first node */
flag =0;
while (Far != NULL)
{
if (Roll == Far->roll)
{
flag=1;
break;
}
/* Point to the next node */
Far = Far->next;
}
if (flag == 1) return 1;
else return 0;
}
6.3.4 Insertion in a Linked List
We have already appreciated that linked lists are most suitable and efficient data structures for insertion and deletion operations. The insertion of a node in a linked list involves the following three steps:
- Take a node. Store data into the node.
- Search the location in the list where the node is to be inserted.
- Insert the node.
The location where the node is to be inserted in a linked list can either be at the beginning or at any other arbitrary position in the list. An algorithm that inserts a node at the beginning of the list is given below:
In this algorithm, a node pointed by ptr is inserted in a linked list whose first node is pointed by the pointer First.
Algorithm insertAtHead()
{
Step
1. Take a node in ptr.
2. Read DATA(ptr).
3. If (First == NULL) then
{
3.1 First = ptr;
3.2 NEXT (First) = NULL;
}
else
{
3.1 NEXT(Ptr) = First;
3.2 First = ptr;
}
4. Stop
}
The list structure before and after the insertion operation is shown in Figure 6.14.
Fig. 6.14 Insertion at the beginning of a list
It may be noted that after the insertion operation, both First and ptr are pointing to first node of the list.
If it is desired to insert a node at arbitrary position in a linked list, then it can either be inserted after a node or before a node in the list. An algorithm for insertion of a node after a selected node in a linked list is below.
Let First be the pointer to the linked list. In this algorithm, a node is inserted after a node with data part equal to ‘val’. A pointer ‘ptr’ travels the list in such a way that each visited node is checked for data part equal to val. If such a node is found then the new node, pointed by a pointer called ‘nptr’, is inserted.
Algorithm insertAfter()
{
Step
1. ptr = First
2. while (ptr != NULL)
{
2.1 if (DATA (ptr) = val)
{ take a node in nptr;
Read DATA(nptr);
Next (nptr) = Next (ptr);
Next (ptr) = nptr;
break;
}
2.2 ptr = Next(ptr);
}
3. Stop
}
The list structure before and after the insertion operation is shown in Figure 6.15.
Fig. 6.15 Insertion after a selected node in the list
Example 4: Modify Example 3 such that after creation of a linked list of students, the program asks from the user to enter data for the student which is desired to be inserted into the list after a given node.
Solution: The required program is given below. It takes care of both the cases, i.e., it inserts the student as per his roll number in the list, which can be at the beginning or at any other location in the list.
/* This program inserts an item in a linked list */
#include <stdio.h>
#include <alloc.h>
#include <process.h>
struct student {
char name [15];
int roll;
struct student *next;
};
struct student *create();
struct student * insertList(struct student *First, int Roll, int *flag);
void dispList(struct student *First);
void main()
{
struct student *First;
int Roll, result;
First = create();
if (First != NULL) /* Insert in between */
{
printf (“
Enter the roll no. of the student”);
printf (“
after which the insertion is to be made :”);
scanf(“%d”, &Roll);
}
First = insertList(First, Roll, &result);
if (result == 1)
{printf (“
The list….”);
dispList(First);
}
else
printf (“
The place not found”);
}
struct student * create () /* Here any of the create() function designed in above examples can be used */
{
}
struct student* insertList(struct student *First, int Roll, int *flag)
{
struct student *ptr,*Far;
int Sz; /* Insert at the Head of the list */
if ((First == NULL) || (First->roll > Roll))
{
ptr = (struct student *) malloc (Sz);
/* Read Data of next student */
printf (“
Name: ”); fflush(stdin); gets(ptr->name);
printf (“
Roll: ”); scanf(“%d”, &ptr->roll);
ptr->next =First;
First = ptr;
*flag = 1; /* indicates that insertion was made*/
}
else
{ Far = First; /* Point to the first node */
*flag = 0;
while (Far != NULL)
{
if (Roll == Far->roll)
{
*flag=1;
break; /* The location of the insertion found*/
}
/* Point to the next node */
Far = Far->next;
}
if (*flag==1)
{
ptr = (struct student *) malloc (Sz);
/* Read Data of student for insertion */
printf(“
Enter the data of student”);
printf (“
Name: ”); fflush(stdin); gets(ptr->name);
printf (“
Roll: ”); scanf(“%d”, &ptr->roll);
ptr->next = Far->next; /* Insert node */
Far->next = ptr;
}
}
ptr = First;
return ptr;
}
void dispList(struct student *First) /* Here any of the dispList()
function designed in above examples can be used */
{
}
Note: It is easier to insert a node after a selected node in a linked list as only one pointer is needed to select the node. For example, in the above program, the Far pointer has been used to select the node after which the insertion is made.
However, if insertion is needed to be made before a selected node then it is cumbersome to insert node with only one pointer. The reason being that when the node is found before which the insertion is desired, there is no way to reach to its previous node and make the insertion. The easier and elegant solution is to use two pointers (Far and back) which move in tandem, i.e., the pointer Far is followed by back. When Far reaches the desired location, back points to its previous location as shown in Figure 6.16.
Fig. 6.16 Insertion before a given node in a linked list
An algorithm for insertion of data before a selected node in a linked list pointed by First is given below:
Algorithm insertBefore()
{
Far = First;
If (DATA(Far) ==’Val’) /* Check if the first node is the desired node */
{
take a new node in ptr;
Read DATA(ptr);
Next(ptr) = Far;
First = ptr;
Stop;
}
while (Far != NULL )
{
back = Far;
Far = Next(Far);
If (DATA(Far) ==’Val’) /* Check if the node is the desired node */
{
take a new node in ptr;
Read DATA(ptr);
Next(ptr) = Far;
Next(back) = ptr;
break;
}
}
}
Example 5: A sorted linked list of students in the order of their roll numbers is given. Write a program that asks from the user to enter data for a missing student which is desired to be inserted into the list at its proper place.
Solution: The sorted linked list of students in the order of their roll numbers would be created by using function create(), developed in the previous programs. The data of the student which is to be inserted is read and its proper location found, i.e., before the node whose roll number is greater than the roll number of this in coming student. The algorithm insertBefore() would be used for the desired insertion operation.
The required program is given below:
/* This program inserts a node in a linked list */
#include <stdio.h>
#include <alloc.h>
#include <process.h>
struct student {
char name [15];
int roll;
struct student *next;
};
struct student *create();
struct student * insertList(struct student *First, struct student newStud, int *flag);
void dispList(struct student *First);
void main()
{
struct student *First, stud;
int Roll, result;
First = create();
printf (“
Enter the data of the student which is to be inserted”);
scanf(“%s %d”, &stud.name, &stud.roll);
First = insertList(First, stud, &result);
if (result == 1)
{printf (“
The list.…”);
dispList(First);
}
else
printf (“
The place not found”);
}
struct student * create () /* Here any of the create() function designed in above examples can be used */
{
}
struct student* insertList(struct student *First, struct student newStud, int *flag)
{
struct student *ptr,*Far,*back;
int Sz; /* Insert at the Head of the list */
if ((First == NULL) || (First->roll > newStud.roll))
{
Far = (struct student *) malloc (Sz);
/* Read Data of next student */
strcpy(Far->name, newStud.name);
Far->roll = newStud.roll;
Far->next =First;
First = Far;
*flag =1; /* indicates that insertion was made*/
}
else
{ ptr =back = First; /* Point to the first node */
*flag =0;
while (ptr != NULL)
{
ptr = ptr->next;
if (newStud.roll > back->roll&& newStud.roll <ptr->roll)
{
*flag=1;
break; /* The location of the insertion found*/
}
back =ptr;
}
if (*flag==1)
{
Far = (struct student *) malloc (Sz);
/* Read Data of student for insertion */
strcpy(Far->name, newStud.name);
Far->roll = newStud.roll;
Far->next = ptr; /* Insert node */
back->next = Far;
}
}
ptr = First;
return ptr;
}
void dispList(struct student *First) /* Here any of the dispList() function designed in above examples can be used */
{
}
6.3.5 Deleting a Node from a Linked List
A delete operation involves the following two steps:
- Search the list for the node which is to be deleted.
- Delete the node.
The first step requires that two pointers in tandem be used to search the node needs to be deleted. After the search, one pointer points to the selected node and the other points to immediate previous node.
An algorithm for deletion of a node from a list pointed by First is given below. It uses two pointers, ptr and back, that travel the list in such a way that each visited node is checked. If it is the node to be deleted, then ptr points to this selected node and the pointer back points to its immediate previous node as shown in Figure 6.17.
Algorithm delNode()
{
1. if (DATA (First) = ’VAL’ /* Check if the starting node is the desired
one */
{
1.1 ptr = First;
1.2 First = Next (First);
1.3 Free(ptr);
1.4 Stop;
}
2. Back = First;
3. ptr = Next (First)
4. while (ptr != NULL)
{
4.1 if (DATA(ptr) = ’VAL’)
{
Next(Back) = Next (ptr); /* The node is deleted */
Free(ptr);
break;
}
4.2 back = ptr;
4.3 ptr = Next(ptr);
}
}
5. Stop
}
The list structure before and after the deletion operation is shown in Figure 6.17.
Example 6: A linked list of students in the order of their roll numbers is given. Write a program that asks from the user to enter roll number of the student which is desired to be deleted from the list.
Solution: The linked list of students in the order of their roll numbers would be created by using function create(), developed in the previous programs. The roll number of the student which is to be deleted is read and its proper location found. The algorithm delNode() would be used for the desired deletion operation.
The required program is given below:
/* This program deletes a node from a linked list */
#include <stdio.h>
#include <alloc.h>
#include <process.h>
struct student {
char name [15];
int roll;
struct student *next;
};
struct student *create();
struct student *delNode(struct student *First, int roll, int *flag);
void dispList(struct student *First);
void main()
{
struct student *First;
int Roll, result;
First = create();
printf (“
Enter the Roll of the student which is to be deleted”);
scanf(“ %d”, &Roll);
First = delNode(First, Roll, &result);
if (result == 1)
{printf (“
The list.…”);
dispList(First);
}
else
printf (“
The place not found”);
}
struct student *create () /* Here any of the create() function designed
in above examples can be used */
{
}
struct student* delNode(struct student *First, int Roll, int *flag)
{
struct student *ptr,*Far,*back;
int Sz;
if (First == NULL) { *flag=0; return First; }
/* delete from the Head of the list */
if (First->roll == Roll)
{
ptr = First;
First = First->next;
free(ptr);
*flag =1; /* indicates that deletion was made*/
}
else
{ ptr =back = First; /* Point to the first node */
*flag =0;
while (ptr != NULL)
{
ptr = ptr->next;
if (Roll == ptr->roll)
{
*flag=1;
break; /* The location of the deletion found*/
}
back =ptr;
}
if (*flag==1)
{ back->next =ptr->next;
free(ptr);
}
}
return First;
}
void dispList(struct student *First) /* Here any of the dispList() function designed in above examples can be used */
{
}
6.4 VARIATIONS OF LINKED LISTS
There are many limitations of a linear linked list. Some of them are as follows:
- The movement through the linked list is possible only in one direction, i.e., in the direction of the links.
- As discussed above, a pointer is needed to be pointed to a node before the node that needs to be deleted.
- Insertion or appending of a node at the end of the linked list can only be done after travelling whole of the list.
In order to overcome the limitations, many variations of linear or singly linked lists have been suggested in the literature. Some of the popular variations of linear linked lists are given in subsequent sections.
6.4.1 Circular Linked Lists
A circular linked list is a linked list in which the last node points to the node at the beginning of the list as shown in Figure 6.18. Thus, it forms a circle, i.e., there is no NULL pointer. In fact, every node has a successor.
Fig. 6.18 Circular linked list
The main advantage of the circular linked list is that from any node, in the list, one can reach to any other node. This was not possible in a linear linked list, i.e., there was no way of reaching to nodes preceding the current node.
A modified algorithm for creation of circular linked list is given below:
Algorithm createCirLinkList()
{
Step
1. Take a new node in pointer called first.
2. Read Data (First).
3. Point back pointer to the same node being pointed by first, i.e., back = first.
4. Bring a new node in the pointer called far.
5. Read Data (far).
6. Connect next of back to far, i.e., back −> next = far.
7. Take back to far, i.e., back = far.
8. Repeat steps 4 to 7 till whole of the list is constructed.
9. Point next of far to First, i.e., for next = First.
10. Stop.
}
Example 7: Write a function create() that creates a circular linked list of N students of following structure type:
struct student {
char name [15];
int roll;
struct student *next;
};
Solution: We have used the algorithm createCirLinkList() to write the required function which is given below:
struct student *create()
{
struct student * First, *Far, *back;
int N,i;
int Sz;
Sz = sizeof (struct student);
printf(“
Enter the number of students in the class”);
scanf(“%d”, &N);
if ( N==0) return NULL; /* List is empty */
/* Take first node */
First = (struct student *) malloc (Sz);
/* Read the data of the first student */
printf (“
Enter the data”);
printf (“
Name: ”); fflush(stdin); gets(First->name);
printf (“
Roll: ”); scanf(“%d”, &First->roll);
First->next = NULL;
/* point back where First points */
back = First;
for (i =2; i <=N; i++)
{ /* Bring a new node in Far */
Far = (struct student *) malloc (Sz);
/* Read Data of next student */
printf (“
Name: ”); fflush(stdin); gets(Far->name);
printf (“
Roll: ”); scanf(“%d”, &Far->roll);
/* Connect Back to Far */
back->next = Far;
/* point back where Far points */
back = Far;
} /* Repeat the process */
Far->next = First; /* Point the last pointer to the first node */
return First; /* return the pointer to the linked list */
}
Example 8: Write a program that travels a circular linked list consisting of nodes of following struct type. While travelling, it counts the number of nodes in the list. Finally, the count is printed.
struct student {
char name [15];
int roll;
struct student *next;
};
Solution: A circular linked list of nodes of student type would be created by using the function called create() developed in Example 7. The list would be travelled from the first node till we reach back to the first node. While travelling, the visited nodes would be counted. The required program is given below:
/* This program travels a circular linked list and counts the number of nodes */
#include <stdio.h>
#include <alloc.h>
struct student {
char name [15];
int roll;
struct student *next;
};
struct student *create();
int countNode(struct student * First);
void main()
{
int count;
struct student *First;
First = create();
count = countNode(First);
printf(“
The number of nodes = %d”, count);
}
struct student *create() /* Here the create() function of Example 7 can be used */
{
}
/* Travel and count the number of nodes */
int countNode(struct student * First)
{
struct student *ptr;
int count;
count =0;
ptr = First; /* Point to the first node */
do
{ count = count +1;
/* Point to the next node */
ptr = ptr->next;
}
while (ptr != First); /* The travel stops at the first node */
return count;
}
Note: The above representation of circular linked list (Figure 6.18) has a drawback as far as the insertion operation is concerned. Even if the node is to be added at the head of the list, the complete list will have to be travelled so that the last pointer is made to point to the new node. This operation ensures that the list remains circular after the insertion. It may be noted that this extra travel was not required in the case of linear linked list.
The above drawback of circular linked lists can be avoided by shifting the First pointer to the last node in the list as shown in Figure 6.19.
Fig. 6.19 Another representation of a circular linked list
It may be noted that by having this representation, both ends of the list can be accessed through the First. The First points to one end and the Next (First) points to another.
A node can be added at the head of the list by the following algorithm:
Algorithm insertHead()
{
Step
1. Take a new node in ptr.
2. Read DATA(ptr).
3. Next(ptr) = Next (First).
4. Next(First) = ptr.
}
The effect of the above algorithm is shown in Figure 6.20.
Fig. 6.20 Insertion of a node at the head of a circular linked list without travel
A node can be added at the tail (i.e., last) of the list by the following algorithm:
Algorithm insertTail()
{ Step
1. Take a new node in ptr.
2. Read DATA(ptr).
3. Next(ptr) = Next (First).
4. Next(First) = ptr.
5. First = ptr.
}
The effect of the above algorithm is shown in Figure 6.21.
Fig. 6.21 Insertion of a node at the tail of a circular linked list without travel
It may be noted that in both the cases of insertion (at the head and tail), no travel of the circular linked list was made. Therefore, the new representation has removed the drawback of the ordinary circular linked list. In fact, it offers the solution in the order of O(1).
6.4.2 Doubly Linked List
Another variation of linked list is a doubly linked list. It is a list in which each node contains two links: leftLink and rightLink. The leftLink of a node points to its preceding node and the rightLink points to the next node in the list (see Figure 6.22).
Fig. 6.22 Node of a doubly linked list
From Figure 6.22, it can be noticed that a node in the doubly linked list has the following three fields:
| (1) Data | : for the storage of information. |
| (2) leftLink | : pointer to the preceding node. |
| (3) rightLink | : pointer to the next node. |
The arrangement of nodes in a doubly linked list is shown in Figure 6.23.
Fig. 6.23 A doubly linked list
The algorithm for creation of doubly linked list is given below:
Algorithm createDList()
{
Step
1. Take a new node in pointer called First.
2. Point leftLink of first to NULL, i.e., first−>leftLink = NULL.
3. Read Data(First).
4. Point back pointer to the node being pointed by First, i.e., back = First.
5. Bring a new node in the pointer called Far.
6. Read Data(Far).
7. Connect rightLink of back to Far, i.e., back−>rightLink = Far.
8. Connect leftLink of Far to Back, i.e., Far−>leftLink = Back.
9. Take back to Far, i.e., back = Far.
10. Repeat steps 5 to 9 till whole of the list is constructed.
11. Point rightLink of far to NULL, i.e., far−> rightLink = NULL.
12. Stop.
}
Example 9: Write a program that uses a function create() to create a doubly linked list of N students of following structure type.
struct student {
char name [15];
int roll;
struct student *leftList, *rightList;
};
It travels the list in both directions, i.e., forward and backward. The data part of visited nodes is displayed.
Solution: We have used the algorithm createDList() to write the required program. Two functions— dispForward() and dispBackward()—are also written to travel the list in both the directions. The required program is given below:
/* This program creates a doubly linked list of students */
#include <stdio.h>
#include <alloc.h>
struct student {
char name [15];
int roll;
struct student *leftList,*rightList;
};
struct student *create();
void dispForward(struct student *First);
void dispBackward(struct student *First);
void main()
{
struct student *First;
First = create();
dispForward(First);
dispBackward(First);
}
struct student *create()
{
struct student * First,*Far, *back;
int N,i;
int Sz;
Sz = sizeof (struct student);
printf(“
Enter the number of students in the class”);
scanf(“%d”, &N);
if ( N==0) return NULL; /* List is empty */
/* Take first node */
First = (struct student *) malloc (Sz);
/* Read the data of the first student */
printf (“
Enter the data”);
printf (“
Name: ”); fflush(stdin); gets(First->name);
printf (“
Roll: ”); scanf(“%d”, &First->roll);
First->rightList = NULL;
First->leftList = NULL;
/* point back where First points */
back = First;
for (i =2; i <=N; i++)
{ /* Bring a new node in Far */
Far = (struct student *) malloc (Sz);
/* Read Data of next student */
printf (“
Name: ”); fflush(stdin); gets(Far->name);
printf (“
Roll: ”); scanf(“%d”, &Far->roll);
/* Connect Back to Far */
back->rightList = Far;
/* point back where Far points */
Far->leftList = back;
back = Far;
} /* Repeat the process */
Far->rightList = NULL;
return First;
}
/* Print the created linked in forward direction */
void dispForward(struct student *First)
{ struct student *Far;
Far = First; /* Point to the first node */
printf (“
The Forward List is ….”);
while (Far != NULL)
{
printf (“ %s - %d, ”,Far->name, Far->roll);
/* Point to the next node */
Far = Far->rightList;
}
}
/* Print the created linked in backward direction */
void dispBackward(struct student * First)
{ struct student *Far;
Far = First; /* Point to the first node */
while (Far->rightList != NULL)
{ /* Travel to the last node */
Far = Far->rightList;
}
printf (“
The Back word List is ….”);
while (Far != NULL) /* Travel the list in backward direction*/
{
printf (“ %s - %d, ”,Far->name, Far->roll);
/* Point to the next node */
Far = Far->leftList;
}
}
Consider the doubly linked list given in Figure 6.24.
Fig. 6.24 The left of right and right of left is the same node
The following relations hold good for the pointer ptr:
- ptr ≡ ptr −> leftLink −> rightLink
- ptr ≡ ptr −> rightLink −> leftLink
The first relation indicates that the rightLink of leftLink of ptr is pointing to the same node being pointed by ptr. Similarly, the second relation indicates that the leftLink of rightLink of ptr is pointing to the same node being pointed by ptr.
The above relations help us to insert node in a doubly linked list. The discussion on this aspect is given in Section 6.4.2.1.
6.4.2.1 Insertion in Doubly Linked List
Insertion of a node X before a node pointed by ptr can be done by the following program segment:
- X −> rightLink = ptr −> leftLink −> rightLink;
- ptr −> leftLink −> rightLink = X;
- X −> leftLink = ptr −> leftLink;
- ptr −> leftLink =X;
The effect of the above program segment is shown in Figure 6.25. The above four operations have been labelled as 1–4 in Figure 6.25.
Fig. 6.25 Insertion of node X before a node pointed by ptr
Similarly, insertion of a node X after a node pointed by ptr can be done by the following program segment:
- X −>leftLink = ptr −>rightLink −>leftLink;
- ptr −>rightLink −>leftLink = X;
- X −>rightLink = ptr −>rightLink;
- Ptr −>rightLink =X;
The effect of the above program segment is shown in Figure 6.26. The above four operations have been labeled as 1–4 in Figure 6.26.
Fig. 6.26 Insertion of node X after a node pointed by ptr
6.4.2.2 Deletion in Doubly Linked List
Deletion of a node pointed by ptr can be done by the following program segment:
- ptr −> left −> right = ptr −> right;
- ptr −> right −> left = ptr −> left;
- free(ptr);
The effect of the above program segment is shown in Figure 6.27. The above three operations have been labeled as 1–3 in Figure 6.27.
Fig. 6.27 Deletion of a node pointed by ptr
Note: During insertion or deletion of a node, the leftLink and rightLink pointers are appropriately fixed so that they point to the correct node in the list.
From Figures 6.23 to 6.27, it may be observed that the doubly linked list has the following advantages over the singly linked list:
- With the help of rightLink, the list can be traversed in forward direction.
- With the help of leftLink, the list can be traversed in backward direction.
- Insertion after or before a node is easy as compared to singly linked list.
- Deletion of a node is also very easy as compared to singly linked list.
It is left as an exercise for the readers to implement the insertion and deletion operations using ‘C’.
6.5 THE CONCEPT OF DUMMY NODES
The linked list and its variants, discussed above, have a major drawback. Every algorithm has to take care of special cases. For instance, besides a normal operation, an algorithm has to make sure that it works for the following exceptional or boundary cases:
- the empty list
- on the head element of the list
- on the last element of the list
The above situation occurs when a node in a linked list has no predecessor or a successor. For example, the first node in a linked list has no predecessor and, therefore, insertion or deletion at the end requires a special case. Similarly, an empty circular linked list will not be circular. Same is the case with doubly linked list.
The above anomalous situation can be resolved with the help of a dummy node. The dummy node is a head or front node which is purposefully left blank. The First pointer always points to the dummy node as shown in Figure 6.28.
Fig. 6.28 Linked list with a dummy node
It may be noted that the list shown in Figure 6.28 represents a list of integers (25, 37, 68 …). The dummy node does not contain any value. It may be further noted that first node of the list (containing 25) is also having dummy node as its predecessor and, therefore, insertion at the head of the node can be done in a normal fashion as done in algorithm insertAfter() of section 6.3.4.
Similarly, dummy nodes can also be used for circular and doubly linked lists as shown in Figure 6.29.
Fig. 6.29 Circular and doubly linked lists with dummy nodes
Note: With the inclusion of a dummy node, an algorithm does not have to check for special or exceptional cases such as existence of empty list or insertion/deletion at the head of the list and the like. Thus, the algorithm becomes easy and applicable to all situations.
Some programmers employ the dummy node to store useful information such as number of elements in the list or the name of the group or set to which the elements belong to. For example, the list shown in Figure 6.28 can be modified so that the dummy node contains information about number of elements present in the list (3 in this case). The modified list is given in Figure 6.30.
Fig. 6.30 Dummy node contains important information
Many programmers use a dummy node called a trailer node at the tail end so that each node in the list has a successor.
Another benefit of dummy node is that an empty circular linked list is also circular in nature. Same is the case with doubly linked list as shown in Figure 6.31.
Fig. 6.31 Comparison of empty lists with and without dummy nodes
It may be noted that with the help of dummy nodes, the basic nature of linked lists remains intact.
6.6 LINKED STACKS
We know that a stack is a LIFO (last in first out) data structure. Earlier in the book, the stack was implemented using an array. Though the array implementation was efficient but a considerable amount of storage space was wasted in the form of unutilized locations of the array. For example, let us assume that at a given time, there are five elements in a stack. If the stack is implemented using 20 locations, then 15 locations out of 20 are being wasted.
A solution to this problem is dynamic storage allocation, i.e., implement stack using linked lists. Since a stack involves frequent additions and deletions at one end called ‘Top’, the linked list is definitely a better choice from the point of implementation.
Obviously, the structure of the node in a linked stack will also be self-referential. The arrangement of nodes is shown in Figure 6.32. It may be noted that its one end is being pointed by a pointer called Top and the other end is pointing to NULL.
Fig. 6.32 A linked stack
An algorithm for pushing an element on to the stack is given below. In this algorithm, a node pointed by ptr is pushed onto the stack.
Algorithm Push()
{
Step
1. Take a new node in ptr;
2. Read DATA(ptr);
3. Next (ptr) = Top;
4. Top = ptr;
}
The structure of linked stack after a push operation is shown in Figure 6.33.
Fig. 6.33 Linked stack after a PUSH operation
An algorithm for popping an element from the stack is given below. In this algorithm, a node from the Top of the stack is removed. The removed node is pointed by ptr.
Algorithm POP()
{
Step
1. if (Top = NULL) then prompt ’stack empty’; Stop
2. ptr = Top
3. Top = Next (Top);
4. return DATA(ptr)
5. Free ptr
}
The structure of linked stack after a POP operation is shown in Figure 6.34.
Fig. 6.34 Linked stack after a POP operation
Example 10: Write a menu driven program that simulates a linked stack for integer data items.
Solution: The algorithms Push() and POP() developed in this section would be used to write the program that simulates a linked stack for integer data items. Each node of the linked stack would be of following structure type:
struct node
{
int item;
struct node * next;
};
The required program is given below:
/* This program simulates a linked stack for integer data items */
#include <stdio.h>
#include <alloc.h>
#include <conio.h>
struct node
{
int item;
struct node *next;
};
struct node *push (struct node *Top, int item);
struct node *pop (struct node *Top, int * item);
void dispStack(struct node *Top);
void main ()
{
int item, choice;
struct node *Top;
Top = NULL;
do
{ clrscr();
printf (“
Menu ”);
printf (“
Push 1”);
printf (“
Pop 2”);
printf (“
Display 3”);
printf (“
Quit 4”);
printf (“
Enter Choice: ”);
scanf (“%d”, &choice);
switch (choice)
{
case 1: printf (“
Enter the integer item to be pushed:”);
scanf (“%d”, &item);
Top = push (Top, item);
break;
case 2: if (Top == NULL)
{ printf (“
Stack empty”);
break;
}
Top = pop (Top, &item);
printf (“
The popped item = %d”, item);
break;
case 3: dispStack(Top);
break;
}
printf (“
press any key”); getch();
}
while (choice != 4);
}
struct node * push (struct node *Top, int item)
{
struct node *ptr;
int size;
size = sizeof (struct node);
ptr = (struct node *) malloc (size);
ptr->item = item;
ptr->next = Top;
Top = ptr;
return Top;
}
struct node *pop (struct node *Top, int *item)
{
struct node *ptr;
if (Top == NULL) return NULL;
ptr = Top;
Top = Top->next;
*item = ptr->item;
free (ptr);
return Top;
}
void dispStack(struct node *Top)
{
if (Top == NULL)
printf (“
Stack Empty”);
else
{
printf (“
The Stack is: ”);
while (Top != NULL)
{
printf (“ %d ”, Top->item);
Top =Top->next;
}
}
}
6.7 LINKED QUEUES
We know that a queue is a FIFO (first in first out) data structure. Since this data structure also involves deletions and additions at front end and rear end respectively, a linked list is definitely a better choice from the point of implementation.
A linked queue will have the same node structure as in the case of a stack as shown in Figure 6.35. Two pointers called Front and Rear would keep track of the front and rear end of the queue.
Fig. 6.35 A linked queue
An algorithm for adding an element on to the queue is given below. In this algorithm, a node pointed by ptr is added into the queue.
Algorithm AddQueue()
{
Step
1. Take a new node in ptr;
2. Read DATA(ptr);
3. Next (ptr) = Next (Rear);
4. Next(Rear) = ptr;
5. Rear = ptr;
}
The structure of linked queue after addition operation is shown in Figure 6.36.
Fig. 6.36 The linked queue after an addition operation
An algorithm for deleting an element from the linked queue is given below. In this algorithm, a node from the front of the queue is removed.
Algorithm delQueue()
{
Step
1. if (Front == Rear) then prompt ’Queue empty’; Stop
2. ptr = Front;
3. Front = Next (Front);
4. Free ptr 5. return DATA(Front)
}
The structure of linked queue after a deletion operation is shown in Figure 6.37.
Fig. 6.37 The linked queue after a deletion operation
It may be noted that the Front always points to a blank node, i.e., which does not contain any data. Thus, when the queue is empty then both Front and Rear point to a blank node.
Example 11: Write a menu-driven program that simulates a linked queue for integer data items.
Solution: The algorithms AddQueue() and delQueue() developed in this section would be used to write the program that simulates a linked queue for integer data items. Each node of the linked queue would be of following structure type:
struct node
{
int item;
struct node * next;
};
The required program is given below:
/* This program simulates a linked queue for integer data items */
#include <stdio.h>
#include <alloc.h>
#include <conio.h>
struct node
{
int item;
struct node *next;
};
struct node *addQ (struct node *Rear,struct node *Front, int item);
struct node *delQ (struct node *Rear,struct node *Front, int *item);
void dispQ(struct node *Rear,struct node *Front);
void main ()
{
int item, choice, size;
struct node *Front, *Rear;
size = sizeof (struct node);
Front = (struct node *) malloc (size);
Front->item = −9999; /* dummy node */
Front->next = NULL;
Rear = Front; /* Initialize Queue to empty */
do
{ clrscr();
printf (“
Menu ”);
printf (“
Add 1”);
printf (“
Delete 2”);
printf (“
Display 3”);
printf (“
Quit 4”);
printf (“
Enter Choice : ”);
scanf (“%d”, &choice);
switch (choice)
{
case 1: printf (“
Enter the integer item to be added:”);
scanf (“%d”, &item);
Rear = addQ (Rear, Front, item);
break;
case 2: if (Front == Rear)
{
printf (“
Queue empty”);
break;
}
Front =delQ (Rear, Front, &item);
printf (“
The deleted item = %d”, item);
break;
case 3: dispQ(Rear, Front);
break;
}
printf (“
press any key”); getch();
}
while (choice != 4);
}
struct node * addQ (struct node *Rear, struct node *Front, int item)
{
int size;
struct node *ptr;
size = sizeof (struct node);
ptr = (struct node *) malloc (size);
ptr->item = item;
ptr->next = Rear->next;
Rear->next = ptr;
Rear = ptr;
return ptr;
}
struct node * delQ (struct node *Rear, struct node *Front, int * item)
{
struct node *ptr;
ptr = Front;
Front = Front->next;
*item = Front->item;
Front->item = −9999; /* The dummy node */
free (ptr);
return Front;
}
void dispQ(struct node *Rear, struct node *Front)
{
if (Front == Rear)
printf (“
The queue empty”);
else
{ printf (“
The queue is… ”);
do
{
Front = Front->next;
printf(“ %d ”, Front->item);
}
while (Front != Rear);
}
}
6.8 COMPARISON OF SEQUENTIAL AND LINKED STORAGE
A list can be stored in a one-dimensional array and in a linked list as well. The choice of data structure depends upon the problem at hand and the type of operations to be performed on the data. A summarized comparison of sequential and linked storage is given below:
- Unlike arrays, the linked list is a dynamic data structure. The linked list implementation adds the elements to the list by getting the memory allocated dynamically. Therefore, the number of elements present in the linked list is limited only by the memory available to the operating system. We can say that the limitation of arrays has been effectively handled by the linked list implementation.
- Linked lists store the elements in non-contiguous locations. The nodes are independent of each other.
- Linked lists are useful for storing elements in the order of insertion and subsequent traversal in that order.
- However, the linked lists occupy more space than the arrays because each node contains an extra pointer besides the information.
- Compared to arrays, linked lists are slow in many ways. The dynamic memory is allocated through a system call to operating system making the processing very slow. Moreover, every element is referred to through an extra reference made through a pointer thereby making the processing of linked list further slow.
- Access to an element in a linked list is purely sequential whereas an element in array can be accessed through its index. Thus, arrays are faster in accessing an element.
- Nevertheless, a linked list offers a very easy way of insertions and deletions in a list without the physical shifting of elements in the list.
- Without moving the nodes, the elements of the list can be reordered by simply changing the pointers.
6.9 SOLVED PROBLEMS
Problem1: Write an algorithm which travels a linked list pointed by List. It travels the list in such a way that it reverses the links of the visited nodes, i.e., at the end the list becomes reversed.
Solution: An algorithm called revLink() is given below. In this algorithm, a linked list pointed by the pointer List is travelled with the help of three pointers back, Ahead, and ptr. During the travel, the direction of link of each visited node is reversed, i.e., it points to its immediate preceding node. At the end, the pointer List is made to point to the last node as shown in Figure 6.38.
Fig. 6.38 Reversal of links of a linked list
Algorithm revLink()
{
Step
1. if (List == NULL) return List;
2. ptr = List;
3. back = List;
4. Ahead = next(ptr);
5. next (List) = NULL;
6. while (Ahead != NULL) repeat steps 7 to 10
7. ptr = Ahead;
8. Ahead = next(Ahead)
9. next (ptr) = back; /* reverse the link */
10. back = ptr;
11. List = ptr;
12. Stop;
}
Problem 2: Write a program which travels a linked list pointed by List. It travels the list in such a way that it reverses the links of the visited nodes, i.e., at the end the list becomes reversed and its contents are displayed.
Solution: The algorithm revLink() developed in Problem 1 is used to write the given program that reverses a linked list of students pointed by a pointer called List. The required function is given below:
/* This function reverses the links of a linked list of students */
#include <stdio.h>
#include <alloc.h>
struct student {
char name [15];
int roll;
struct student *next;
};
struct student *create();
struct student *revLink(struct student *List);
void dispList(struct student *First);
void main()
{
struct student *First;
First = create();
First = revLink(First);
dispList(First);
}
struct student *create()
{
struct student *First,*Far, *back;
int N, i;
int Sz;
Sz = sizeof (struct student);
printf(“
Enter the number of students in the class”);
scanf(“%d”, &N);
if ( N==0) return NULL; /* List is empty */
/* Take first node */
First = (struct student *) malloc (Sz);
/* Read the data of the first student */
printf (“
Enter the data”);
printf (“
Name: ”); fflush(stdin); gets(First- >name);
printf (“
Roll: ”); scanf(“%d”, &First->roll);
First->next = NULL;
/* point back where First points */
back = First;
for (i =2; i <=N; i++)
{ /* Bring a new node in Far */
Far = (struct student *) malloc (Sz);
/* Read Data of next student */
printf (“
Name: ”); fflush(stdin); gets(Far->name);
printf (“
Roll: ”); scanf(“%d”, &Far->roll);
/* Connect Back to Far */
back->next = Far;
/* point back where Far points */
back = Far;
} /* repeat the process */
Far->next = NULL;
return First;
}
struct student *revLink( struct student *List) /* The function that reverses
the list */
{
struct student *back, *ptr, *ahead;
if (List == NULL)
{
printf (“
The list is empty”);
return NULL;
}
ptr = List;
back = List;
ahead = ptr->next;
List->next = NULL;
while (ahead != NULL)
{
ptr = ahead;
ahead = ahead->next; ptr->next = back; /* Connect the pointer to preceding node*/
back = ptr;
}
List = ptr;
return List;
}
/* Print the created linked list */
void dispList(struct student *First)
{ struct student *Far;
Far = First; /* Point to the first node */
printf (“
The List is ….”);
while (Far != NULL)
{
printf (“ %s - %d, ”,Far->name, Far->roll);
/* Point to the next node */
Far = Far->next;
}
}
Problem 3: Write a program that adds two polynomials Pol1 and Pol2, represented as linked lists of terms, and gives a third polynomial Pol3 such that Pol3 = Pol1 + Pol2.
Solution: We will use the following structure for the term of a polynomial:
As done in Chapter 3, the polynomials will be added by merging the two linked lists. The required program is given below:
/* This program adds two polynomials represented as linked lists pointed by two pointers pol1 and pol2 and gives a third polynomial pointed by a third pointer pol3 */
# include <stdio.h>
struct term
{
int coef;
int exp;
struct term *next;
};
struct term * create_pol();
void main()
{
struct term *pol1,*pol2,*pol3, *ptr1,*ptr2,*ptr3, *back, *bring, *ptr;
int size;
size = sizeof (struct term);
printf (“
Polynomial 1”);
pol1 = create_pol();
printf (“
Polynomial 2”);
pol2 = create_pol();
ptr1=pol1;
ptr2=pol2;
ptr3 =pol3=NULL;
while (ptr1 != NULL && ptr2 != NULL) /* Add Polynomials by merging */
{ if ( ptr1->exp > ptr2->exp)
{
if (pol3 == NULL)
{
pol3 = (struct term *) malloc(size);
pol3->coef=ptr1->coef;
pol3->exp=ptr1->exp;
ptr3=pol3;
ptr1= ptr1->next;
ptr3->next = NULL;
}
else
{
bring =(struct term *) malloc(size);
bring->coef=ptr1->coef;
bring->exp=ptr1->exp;
ptr3->next =bring;
ptr3=bring;
ptr1=ptr1->next;
ptr3->next =NULL;
}
}
else
{
if ( ptr1->exp < ptr2->exp)
{
if (pol3 == NULL)
{
pol3 = (struct term *) malloc(size);
pol3->coef=ptr2->coef;
pol3->exp=ptr2->exp;
ptr3=pol3;
ptr2= ptr2->next;
ptr3->next = NULL;
}
else
{
bring =(struct term *) malloc(size);
bring->coef=ptr2->coef;
bring->exp=ptr2->exp;
ptr3->next =bring;
ptr3=bring;
ptr2=ptr2->next;
ptr3->next =NULL;
}
}
else
{
if (pol3 == NULL)
{
pol3 = (struct term *) malloc(size);
pol3->coef=ptr1->coef+ptr2->coef;
pol3->exp=ptr2->exp;
ptr3=pol3;
ptr2= ptr2->next;
ptr1=ptr1->next;
ptr3->next = NULL;
}
else
{
bring =(struct term *) malloc(size);
bring->coef=ptr1->coef+ptr2->coef;
bring->exp=ptr2->exp;
ptr3->next =bring;
ptr3=bring;
ptr2=ptr2->next;
ptr1=ptr1->next;
ptr3->next =NULL;
}
}
}
}
/* while */
/* Append rest of the Polynomial */
if (ptr2->next ==NULL) ptr3->next = ptr1;
if (ptr1->next ==NULL) ptr3->next = ptr2;
/* Print the Final Polynomial */
ptr = pol3;
printf (“
Final Polynomial …”);
while (ptr != NULL)
{
printf (“%d ^ %d ”, ptr->coef, ptr->exp);
if (ptr->exp !=0) printf (“+”);
ptr = ptr->next;
}
}
/* Read the terms of a polynomoial and create the linked list */
struct term * create_pol()
{
int size;
struct term *first, *back, *bring;
size = sizeof(struct term);
first = (struct term *) malloc(size);
printf (“
input Polynomial term by term. Last term with exp =0”);
printf (“
Enter a term - coef exp”);
scanf (“%d %d”, &first->coef, &first->exp);
first->next = NULL;
back = first;
while (back->exp != 0)
{
bring = (struct term *) malloc(size);
printf (“
Enter a term - coef exp”);
scanf (“%d %d”, &bring->coef, &bring->exp);
back->next = bring;
back=bring;
}
back->next = NULL;
return first;
}
EXERCISES
- What is a linear linked list?
- What is the need for a linked list? On what account, linked lists are better than arrays?
- Write a program that takes a linked list pointed by List and traverses it in such a manner that after the travel the links of visited nodes become reversed.
- Write a program to create a linked list and remove all the duplicate elements of the list.
- What is a circular linked list? What are its advantages over linear linked list? Write a program/ algorithm to insert a node at desired position in a circular linked list.
- Write a program that takes two ordered linked lists as input and merges them into single ordered linked list.
- What is a doubly linked list? Write program/algorithm for showing the following operations on a doubly linked list:
- Create
- Insert
- Delete
- What are the advantages of doubly linked list over singly linked list?
- Write the program that inserts a node in a linked list after a given node.
- Write the program that inserts a node in a linked list before a given node.
- Write a program that deletes a given node from a linked list.
- Write a function that deletes an element from a doubly linked list.
- Implement a stack (LIFO) using singly linked list.
- Write a program to implement a queue (FIFO) using singly linked list.
- How do you detect a loop in a singly linked list? Write a ‘C’ program for the same.
- How do you find the middle of a linked list without counting the nodes? Write a ‘C’ program for the same.
- Write a ‘C’ program that takes two lists List1 and List2 and compare them. The program should return the following:
−1 : if List1 is smaller than List2 0 : if List1 is equal to List2 1 : if List1 is greater than List2 - Write a function that returns the nth node from the end of a linked list.
- Write a program to create a new linear linked list by selecting alternate element of a given linear linked list.
- Write an algorithm to search an element from a given linear linked list.
- Explain the merits and demerits of static and dynamic memory allocation techniques.
- Define a header linked list and explain its utility.