Maintaining A Linked List

Linked Lists

Maintaining A Linked List

In Computer Science linked lists are extensively used in Data Base Management Systems, Process Management, Operating Systems, Editors etc. We know that while using arrays very often the list of items to be stored in an array is either too short or too big as compared to the declared size of the array. Moreover, while using an array the list cannot grow beyond the size of the declared array during program execution. Also, operations like insertion and deletion at a specified location in a list requires a lot of movement of data, thereby leading to an inefficient and time consuming algorithm. The primary advantage of linked list over an array is that the linked list can grow and shrink in size during its life time. In particular, the linked list's maximum size need not be known in advance. In practical applications this often makes it possible to have several data structures share the same space, without paying particular attention to their relative size at any time. The second advantage of linked lists is that they provide flexibility in allowing the items to be rearranged efficiently. This flexibility is gained at the expense of quick access to any arbitrary item in the 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, this is how the marks obtained by different students can be stored in a linked list:

Observe that the linked list is a collection of elements called nodes, each of which stores two items of information: one, an element of the list, and two, a link, i.e. a pointer or an address that indicates explicitly the location of the node containing the successor of this list element. In the above figure, the arrows represent the links. The Data part of each node consists of the marks obtained by a student and the Next part is a pointer to the next node. The NULL in the last node indicates that this is the last node in the list. There are several operations that we can think of performing on linked lists. 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 delete( ) which can delete any node in the linked list. Go through the program carefully, a step at a time.

#include "alloc.h"

/* structure containing a data part and link part */

struct node

{

int data ;

struct node *link ;

} ;

main( )

{

struct node *p ;

p = NULL ; /* empty linked list */

printf ( "\nNo. of elements in the Linked List = %d", count ( p ) ) ;

append ( &p, 1 ) ;

append ( &p, 2 ) ;

append ( &p, 3 ) ;

clrscr( ) ;

display ( p ) ;

addatbeg ( &p, 999 ) ;

addatbeg ( &p, 888 ) ;

addatbeg ( &p, 777 ) ;

display ( p ) ;

addafter ( p, 7, 0 ) ;

addafter ( p, 2, 1 ) ;

addafter ( p, 1, 99 ) ;

display ( p ) ;

printf ( "\nNo. of elements in the Linked List = %d", count ( p ) ) ;

delete ( &p, 888 ) ;

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 */

append ( struct node **q, int num )

{

struct node *temp ;

temp = *q ;

if ( *q == NULL ) /* if the list is empty, create first node */

{

*q = malloc ( sizeof ( struct node ) ) ;

temp = *q ;

}

else

{

/* go to last node */

while ( temp -> link != NULL )

temp = temp -> link ;

/* add node at the end */

temp -> link = malloc ( sizeof ( struct node ) ) ;

temp = temp -> link ;

}

/* assign data to the last node */

temp -> data = num ;

temp -> link = NULL ;

}

/* adds a new node at the beginning of the linked list */

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 */

addafter ( struct node *q, int loc, int num )

{

struct node *temp, *t ;

int i ;

/* skip to desired portion */

for ( i = 0 ; i < loc ; i++ )

{

q = q -> link ;

/* if end of linked list is encountered */

if ( q == NULL )

{

printf ( "\nThere are less than %d element", loc ) ;

return ;

}

}

/* insert new node *

t = q -> link ;

temp = malloc ( sizeof ( struct node ) ) ;

temp -> data = num ;

temp -> link = t ;

q -> link = temp ;

}

/* displays the contents of the linked list */

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 */

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 */

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 ;

/* free the memory occupied by the node */

free ( temp ) ;

return ;

}

/* deletes the intermediate nodes in the linked list */

else

{

old -> link = temp -> link ;

free ( temp ) ;

return ;

}

}

else /* traverse the linked list till the last node is reached */

{

old = temp ; /* old points to the previous node */

temp = temp -> link ; /* go to the next node */

}

}

printf ( "\nElement %d not found", num ) ;

}