Site pages
Current course
Participants
General
Module - 1 C Language Fundamentals
Module-2 Decision Making, Looping and Functions
Module 3 – Array, Structure and Pointers
Module-4 Data Structures
22 March - 28 March
Module 6. User define Functions, String Functions,...
Module 7. Passing arguments and returning values
Module 8. Recursion, scope and visibility of a var...
Module 9. Structures and union.
Module- 10 Pointers, Stacks, Push/Pop operations.
Lesson -14 Linked List
14.1 Introduction
United we stand, divided we fall! This has been proved many numbers of times. More united and connected we are, more is the flexibility and scalability. Same is true with linked list. This is perhaps one data structure that has been used at more number of places in computing than you can count. But, beware, they are not simple. But the flexibility and performance they offer is worth the pain of learning them.
For storing similar data in memory we can use either an array or a linked list. Arrays are simple to understand and elements of an array are easily accessible. But arrays suffer from the following limitations:
Arrays have a fixed dimension. Once the size of an array is decided it cannot be increased or decreased during execution. For example, if we construct an array of 100 elements and then try to stuff more than 100 elements in it, our program may crash. On the other hand, if we use only 10 elements then the space for balance 90 elements goes waste.
Array elements are always stored in contiguous memory locations. At times it might so happen that enough contiguous locations might not be available for the array that we are trying. to create. Even though the total space requirement of the array can be met through a combination of non-contiguous blocks of memory, we would still not be allowed to create the array.
Operations like insertion of a new element in an array or deletion of an existing element from the array are pretty tedious. This is because during insertion or deletion each element after the specified position has to be shifted one position to the right (in case of insertion) or one position to the left (in case of deletion).
Linked list overcomes all these disadvantages. A linked list can grow and shrink in size during its lifetime. In other words, there is no maximum size of a linked list. The second advantage of linked lists is that, as nodes (elements) are stored at different memory locations it hardly happens that. we fall short of memory when required. The third advantage is that, unlike arrays, while inserting or deleting the nodes of the linked list, shifting of nodes is not required.
14.2 What Is a Linked List
Linked list is a very common data structure often used to store similar data in memory. While the elements of an array occupy contiguous memory locations, those of a linked list are not constrained to be stored in adjacent locations. The individual elements are stored "somewhere" in memory, rather like a family dispersed, but still bound together. The order of the elements is maintained by explicit links between them. For instance, the integer number can be stored in a linked list as shown in figure 14.1.
Figure 14.1 – Linked list
Observe that the linked list is a collection of elements called nodes, each of which stores two items of information first is an element of the list and second is a link. A link is a pointer or an address that indicates explicitly the location of the node containing the successor of the list element. In Figure14.1, the arrows represent the links. The data part of each node consists of the marks obtained by a student and the link part is a pointer to the next node. The NULL in the last node indicates that this is the last node in the list.
14.3 Operations on Linked List
There are several operations that we can think of performing on linked list. The following program shows how to build a linked list by adding new nodes at the beginning, at the end or in the middle of the linked list. It also contains a function display() which displays all the nodes present in the linked list and a function del() which can delete any node in the linked list. Go through the program carefully, a step a time.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
/* structure containing a data part and link part */
struct node
{
int data ;
struct node * link ;
} ;
void append ( struct node **, int ) ;
void addatbeg ( struct node **, int ) ;
void addafter ( struct node *, int, int ) ;
void display ( struct node * ) ;
int count ( struct node * ) ;
void delete ( struct node **, int ) ;
void main( )
{
struct node *p ;
p = NULL ; /* empty linked list */
printf ( "\nNo. of elements in the Linked List = %d", count ( p ) ) ;
append ( &p, 14 ) ;
append ( &p, 30 ) ;
append ( &p, 25 ) ;
append ( &p, 42 ) ;
append ( &p, 17 ) ;
display ( p ) ;
addatbeg ( &p, 999 ) ;
addatbeg ( &p, 888 ) ;
addatbeg ( &p, 777 ) ;
display ( p ) ;
addafter ( p, 7, 0 ) ;
addafter ( p, 2, 1 ) ;
addafter ( p, 5, 99 ) ;
display ( p ) ;
printf ( "\nNo. of elements in the Linked List = %d", count ( p ) ) ;
delete ( &p, 99 ) ;
delete ( &p, 1 ) ;
delete ( &p, 10 ) ;
display ( p ) ;
printf ( "\nNo. of elements in the Linked List = %d", count ( p ) ) ;
}
/* adds a node at the end of a linked list */
void append ( struct node **q, int num )
{
struct node *temp, *r ;
if ( *q == NULL ) /* if the list is empty, create first node */
{
temp = malloc ( sizeof ( struct node ) ) ;
temp -> data = num ;
temp -> link = NULL ;
*q = temp ;
}
else
{
temp = *q ;
/* go to last node */
while ( temp -> link != NULL )
temp = temp -> link ;
/* add node at the end */
r = malloc ( sizeof ( struct node ) ) ;
r -> data = num ;
r -> link = NULL ;
temp -> link = r ;
}
}
/* adds a new node at the beginning of the linked list */
void addatbeg ( struct node **q, int num )
{
struct node *temp ;
/* add new node */
temp = malloc ( sizeof ( struct node ) ) ;
temp -> data = num ;
temp -> link = *q ;
*q = temp ;
}
/* adds a new node after the specified number of nodes */
void addafter ( struct node *q, int loc, int num )
{
struct node *temp, *r ;
int i ;
temp = q ;
/* skip to desired portion */
for ( i = 0 ; i < loc ; i++ )
{
temp = temp -> link ;
/* if end of linked list is encountered */
if ( temp == NULL )
{
printf ( "\nThere are less than %d elements in list", loc ) ;
return ;
}
}
/* insert new node */
r = malloc ( sizeof ( struct node ) ) ;
r -> data = num ;
r -> link = temp -> link ;
temp -> link = r ;
}
/* displays the contents of the linked list */
void display ( struct node *q )
{
printf ( "\n" ) ;
/* traverse the entire linked list */
while ( q != NULL )
{
printf ( "%d ", q -> data ) ;
q = q -> link ;
}
}
/* counts the number of nodes present in the linked list */
int count ( struct node * q )
{
int c = 0 ;
/* traverse the entire linked list */
while ( q != NULL )
{
q = q -> link ;
c++ ;
}
return c ;
}
/* deletes the specified node from the linked list */
void delete ( struct node **q, int num )
{
struct node *old, *temp ;
temp = *q ;
while ( temp != NULL )
{
if ( temp -> data == num )
{
/* if node to be deleted is the first node in the linked list */
if ( temp == *q )
*q = temp -> link ;
/* deletes the intermediate nodes in the linked list */
else
old -> link = temp -> link ;
/* free the memory occupied by the node */
free ( temp ) ;
return ;
}
/* traverse the linked list till the last node is reached */
else
{
old = temp ; /* old points to the previous node */
temp = temp -> link ; /* go to the next node */
}
}
printf ( "\nElement %d not found", num ) ;
}
Output:
14 30 25 42 17
777 888 999 14 30 25 42 17
777 888 999 1 14 30 99 25 42 17 0
No. of elements in the Linked List = 11
Element 10 not found
777 888 999 14 30 25 42 17 0
No. of elements in the Linked List = 9
To begin with we have defined a structure for a node. It contains a data part and a link part. The variable p has been declared as pointer to a node. We have used this pointer as pointer to the first node in the linked list. No matter how many nodes get added to the linked list, p would continue to pointer to the first node in the list. When no node has been added to the list, p has been set to NULL to indicate that the list is empty.
The append( ) function has to deal with two situations:
The node is being added to an empty list.
The node is being added at the end of an existing list.
In the first case, the condition
if ( *q == NULL)
gets satisfied. Hence, space is allocated for the node using malloc( ). Data and the link part of.this node are set up using the statements.
temp à data = num ;
temp à link = NULL;
Lastly, p is made to point to this node, since the first node has been added to the list and p must always point to the first node. Note that *q is nothing but equal to p.
In the other case, when the linked list is not empty, the condition
if ( *q == NULL)
would fail, since *q (i.e. p is non-NULL). Now temp is made to point to the first node in the list through the statement .
temp = *q;.
Then using temp we have traversed through the entire linked list using the statements
while (temp -> link != NULL)
temp = temp -> link;
The position of the pointers before and after traversing the linked list is shown in following figure.
Each time through the loop the statement temp = temp à link makes temp point to the next node in the list. When temp reaches the last node the condition temp à link != NULL would fail. Once outside the loop we allocate space for the new node through the statement
r =( struet node *) malloc ( sizeof ( struct node ) ) ;
Once the space has been allocated for the new node its data part is stuffed with num and the link part with NULL. Note that this node is now going to be the last Node in the list.
All that now remains to be done is connecting the previous last node with the new last node. The previous last node is being pointed to by temp and the new last node is being pointed to by r.
They are connected through the statement
temp -> link = r ;
this link gets established.
There is often a confusion as to how the statement temp = temp à link makes temp point to the next node in the list. Let us understand this with the help of an example. Suppose in a linked list it contains 4 nodes, temp is pointing at the first node. This is shown in following figure.
Instead of showing the links to the next node we have shown the addresses of the next node in the link part of each node.
When we execute the statement
temp = temp à link ;
the right hand side yields 100. This address is now stored in temp. As a result, temp starts pointing to the node present at address , 100, In effect the statement has shifted temp so that it has' started pointing to the next node in the list. Let us now understand the addatbeg( ) function. Suppose there are already 5 nodes in the list and we wish to add a new node at the beginning, of this existing linked list. This situation is shown in the following figure.
For adding a new node at the beginning, firstly space is allocated for this node and data is stored in it through the statement
temp à data = num ;
Now we need to make the link part of this node point to the existing first node. This has been achieved through the statement
temp à link = *q ;
Lastly, this new node must be made the first node in the list. This has been attained through the statement
*q = temp;
The addafter( ) function permits us to add a new node after a specified number of node in the linked list.
To begin with, through a loop we skip the desired number of nodes after which a new node is to be added. Suppose we wish to add a new node containing data as 99 after the 3rd node in the list. The position of pointers once the control reaches outside the for loop is shown in figure (a) given below. Now space is allocated for the node to be inserted and 99 is stored in the data part of it.
All that remains to be done is readjustment of links such that 99 goes in between 30 and 25. This is achieved through the statements
r à link = temp à link;
temp à link =r ;
The first statement makes link part of node containing 99 to point to the node containing 25. The second statement ensures that the link part of node .containing 30 points' to the node containing 99.On execution of the second statement the earlier link between 30 and 25 is severed. So now 30 no longer points to 25, it points to 99.
The display() and count() functions are straight forward. We leave them for you to understand.
That brings us to the last function in the program i.e. del( ). In this function through the while loop, we have traversed through the entire linked list, checking at each node, whether it is the node to be deleted. If so, we have checked if the node being deleted is the first node in the linked list. If it is so, we have simply shifted p (which is same as *q) to the next node and then deleted the earlier node.
If the node to be deleted is an intermediate node, then the position of various pointers and links before and after the deletion is shown in following figure.
Last modified: Monday, 28 October 2013, 7:58 AM