Thursday, August 7, 2008

Linked List

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

{

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 ) ;

}

Go Top


Maintaining An Ascending Ordered Linked List

How about ensuring that every element added to the linked list gets inserted at such a place that thelinked list is always maintained in ascending order? The following program illustrates the same. And if you know how to maintain a linked list then maintaining it in ascending order is very simple.

#include "alloc.h"

struct node

{

int data ;

struct node *link ;

} ;

main( )

{

struct node *p ;

p = NULL ; /* empty linked list */

add ( &p, 5 ) ;

add ( &p, 1 ) ;

add ( &p, 6 ) ;

add ( &p, 4 ) ;

add ( &p, 7 ) ;

clrscr( ) ;

display ( p ) ;

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

delete ( &p, 7 ) ;

delete ( &p, 4 ) ;

delete ( &p, 5 ) ;

delete ( &p, 9 ) ;

display ( p ) ;

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

}

/* adds node to an ascending order linked list */

add ( struct node **q, int num )

{

struct node *r, *temp = *q ;

r = malloc ( sizeof ( struct node ) ) ;

r -> data = num ;

/* if list is empty or if new node is to be inserted before the first node */

if ( *q == NULL || ( *q ) -> data > num )

{

*q = r ;

( *q ) -> link = temp ;

}

else

{

/* traverse the entire linked list to search the position to insert the new node */

while ( temp != NULL )

{

if ( temp -> data <= num && ( temp -> link -> data > num || temp -> link == NULL ) )

{

r -> link = temp -> link ;

temp -> link = r ;

return ;

}

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

}

r -> link = NULL ;

temp -> link = r ;

}

}

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

}

}

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

}

Have a look at add( ) in the above program. While traversing the linked list the data part of the node to be inserted is compared with that of the current node and that of it's subsequent one and accordingly inserted.

Go Top


Reversing A Linked List

How about reversing the links in the existing linked list such that the last node becomes the first node and the first becomes the last? Here is a program which shows how this reversal of links can be achieved.

#include "alloc.h"

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

struct node

{

int data ;

struct node *link ;

} ;

reverse ( struct node ** ) ;

main( )

{

struct node *p ;

p = NULL ; /* empty linked list */

addatbeg ( &p, 1 ) ;

addatbeg ( &p, 2 ) ;

addatbeg ( &p, 3 ) ;

addatbeg ( &p, 4 ) ;

addatbeg ( &p, 5 ) ;

addatbeg ( &p, 6 ) ;

clrscr( ) ;

display ( p ) ;

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

reverse ( &p ) ;

display ( p ) ;

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

}

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

}

reverse ( struct node **x )

{

struct node *q, *r, *s ;

q = *x ;

r = NULL ;

/* trasverse the entire linked list */

while ( q != NULL )

{

s = r ;

r = q ;

q = q -> link ;

r -> link = s ;

}

*x = r ;

}

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

}

In reverse( ) two variables s and r of type struct node* play an important role for reversing the links of the existing linked list. The variable q also of type struct node* is used to traverse the linked list till the end. While traversing the linked list, r stores address of current node and s stores the address of the previous node. Subsequently, the link part of the node to which r points is assigned the value stored in s. Finally, the last node is made the head node as you see in the last statement in reverse( ).

Go Top


Maintaining A Doubly Linked List

In the linked lists that we have used so far each node provides information about where is the next node in the list. It has no knowledge about where the previous node lies in memory. If we are at the 15th node in the list, then to reach the 14th node we have to traverse the list right from the first node. To avoid this we can store in each node not only the address of next node but also the address of the previous node in the linked list. This arrangement is often known as a Doubly Linked List and is shown in the following figure.

The following program implements the Doubly Linked List (DLL).

#include "alloc.h"

/* structure representing a node of the doubly linked list */

struct dnode

{

struct dnode *prev ;

int data ;

struct dnode * next ;

} ;

main( )

{

struct dnode *p ;

p = NULL ; /* empty doubly linked list */

d_append ( &p , 11 ) ;

d_append ( &p , 21 ) ;

clrscr( ) ;

d_display ( p ) ;

printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;

d_addatbeg ( &p, 33 ) ;

d_addatbeg ( &p, 55 ) ;

d_display ( p ) ;

printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;

d_addafter ( p, 1, 4000 ) ;

d_addafter ( p, 2, 9000 ) ;

d_display ( p ) ;

printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;

d_delete ( &p, 51 ) ;

d_delete ( &p, 21 ) ;

d_display ( p ) ;

printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;

}

/* adds a new node at the end of the doubly linked list */

d_append ( struct dnode **s, int num )

{

struct dnode *r, *q = *s ;

/* if the linked list is empty */

if ( *s == NULL )

{

/*create a new node */

*s = malloc ( sizeof ( struct dnode ) ) ;

( *s ) -> prev = NULL ;

( *s ) -> data = num ;

( *s ) -> next = NULL ;

}

else

{

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

while ( q -> next != NULL )

q = q -> next ;

/* add a new node at the end */

r = malloc ( sizeof ( struct dnode ) ) ;

r -> data = num ;

r -> next = NULL ;

r -> prev = q ;

q -> next = r ;

}

}

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

d_addatbeg ( struct dnode **s, int num )

{

struct dnode *q ;

/* create a new node */

q = malloc ( sizeof ( struct dnode ) ) ;

/* assign data and pointer to the new node */

q -> prev = NULL ;

q -> data = num ;

q -> next = *s ;

/* make new node the head node */

( *s ) -> prev = q ;

*s = q ;

}

/* adds a new node after the specified number of nodes */

d_addafter ( struct dnode *q, int loc, int num )

{

struct dnode *temp ;

int i ;

/* skip to desired portion */

for ( i = 0 ; i <>

{

q = q -> next ;

/* if end of linked list is encountered */

if ( q == NULL )

{

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

return ;

}

}

/* insert new node */

q = q -> prev ;

temp = malloc ( sizeof ( struct dnode ) ) ;

temp -> data = num ;

temp -> prev = q ;

temp -> next = q -> next ;

temp -> next -> prev = temp ;

q -> next = temp ;

}

/* displays the contents of the linked list */

d_display ( struct dnode *q )

{

printf ( "\n" ) ;

/* traverse the entire linked list */

while ( q != NULL )

{

printf ( "%2d <-->", q -> data ) ;

q = q -> next ;

}

printf ( "--> NULL\n" ) ;

}

/* counts the number of nodes present in the linked list */

d_count ( struct dnode * q )

{

int c = 0 ;

/* traverse the entire linked list */

while ( q != NULL )

{

q = q -> next ;

c++ ;

}

return c ;

}

/* deletes the specified node from the doubly linked list */

d_delete ( struct dnode **s, int num )

{

struct dnode *q = *s ;

/* traverse the entire linked list */

while ( q != NULL )

{

/* if node to be deleted is found */

if ( q -> data == num )

{

/* if node to be deleted is the first node */

if ( q == *s )

{

*s = ( *s ) -> next ;

( *s ) -> prev = NULL ;

}

else

{

/* if node to be deleted is the last node */

if ( q -> next == NULL )

q -> prev -> next = NULL ;

else

/* if node to be deleted is any intermediate node */

{

q -> prev -> next = q -> next ;

q -> next -> prev = q -> prev ;

}

free ( q ) ;

}

return ; /* return back after deletion */

}

q = q -> next ; /* go to next node */

}

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

}

Go Top


Merging Of Linked Lists

Suppose we have two linked lists pointed to by two independent pointers and we wish to merge the two lists into a third list. While carrying out this merging we wish to ensure that those elements which are common to both the lists occur only once in the third list. The program to achieve this is given below. It is assumed that within a list all elements are unique.

#include "alloc.h"

struct node

{

int data ;

struct node *link ;

} ;

main( )

{

struct node *first, *second, *third ;

first = second = third = NULL ; /* empty linked lists */

add ( &first, 1 ) ;

add ( &first, 2 ) ;

add ( &first, 3 ) ;

add ( &first, 4 ) ;

add ( &first, 5 ) ;

add ( &first, 6 ) ;

add ( &first, 7 ) ;

clrscr( ) ;

printf ( "First linked list : " ) ;

display ( first ) ;

printf ( "\nNo. of elements in Linked List : %d" , count ( first ) ) ;

add ( &second, 8 ) ;

add ( &second, 9 ) ;

add ( &second, 3 ) ;

add ( &second, 4 ) ;

add ( &second, 5 ) ;

add ( &second, 6 ) ;

add ( &second, 7 ) ;

printf ( "\n\nSecond linked list : " ) ;

display ( second ) ;

printf ( "\nNo. of elements in Linked List : %d" , count ( second ) ) ;

merge ( first, second, &third ) ;

printf ( "\n\nThe concatenated list : " ) ;

display ( third ) ;

printf ( "\nNo. of elements in Linked List : %d", count ( third ) ) ;

}

/* adds node to an ascending order linked list */

add ( struct node **q, int num )

{

struct node *r, *temp = *q ;

r = malloc ( sizeof ( struct node ) ) ;

r -> data = num ;

/* if list is empty or if new node is to be inserted before the first node */

if ( *q == NULL || ( *q ) -> data > num )

{

*q = r ;

( *q ) -> link = temp ;

}

else

{

/* traverse the entire linked list to search the position to insert the new node */

while ( temp != NULL )

{

if ( temp -> data <> link -> data > num

|| temp -> link == NULL ) )

{

r -> link = temp -> link ;

temp -> link = r ;

return ;

}

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

}

r -> link = NULL ;

temp -> link = r ;

}

}

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

}

/* merges the two linked lists, restricting the common elements to occur only once in the final list */

merge ( struct node *p, struct node *q, struct node **s )

{

struct node *z ;

z = NULL ;

if ( p == NULL && q == NULL )

return ;

while ( p != NULL && q != NULL )

{

if ( *s == NULL )

{

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

z = *s ;

}

else

{

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

z = z -> link ;

}

if ( p -> data <> data )

{

z -> data = p -> data ;

p = p -> link ;

}

else

{

if ( q -> data <> data )

{

z -> data = q -> data ;

q = q -> link ;

}

else

{

if ( p -> data == q -> data )

{

z -> data = q -> data ;

p = p -> link ;

q = q -> link ;

}

}

}

}

while ( p != NULL )

{

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

z = z -> link ;

z -> data = p -> data ;

p = p -> link ;

}

while ( q != NULL )

{

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

z = z -> link ;

z -> data = q -> data ;

q = q -> link ;

}

z -> link = NULL ;

}

In this program as usual we begin by building a structure to accommodate the data and link which together represent a node. We have used pointers first, second and third to point to the three linked lists. Since to begin with all the three linked lists are empty, these pointers contain NULL. Next, by calling the function add( ) repeatedly two linked lists are built, one being pointed to by first and other by the pointer second. Finally, the merge( ) function is called to merge the two lists into one. This merged list is pointed to by the pointer third. While merging the two lists it is assumed that the lists themselves are in ascending order. While building the two lists the add( ) function makes sure that when a node is added the elements in the lists are maintained in ascending order. While merging the two lists, the merge( ) function accounts for the possibility of any of the two lists being empty.

Go Top


Linked List Using Recursion

This program maintains a linked list using recursive function. addatend( ), display( ), compare( ), copy( ), length( ) are all recursive functions. compare( ) finds out whether the two linked lists possess same elements. copy( ) copies elements from one linked list to another. length( ) counts the number of nodes present in the linked list. But there are some limitations while using recursion. Since there are number of calls to the same function, the program tends to become slow. Also, same type of variables are created recursively at each call. So consumption of memory is considerable. Above all, there is chance of stack overflow if the calls are too many.

#include "alloc.h"

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

struct node

{

int data ;

struct node *link ;

} ;

main ( )

{

struct node *p, *first, *second ;

clrscr( ) ;

p = first = second = NULL ; /* empty linked list */

addatend ( &p, 1) ;

addatend ( &p, 2) ;

addatend ( &p, 3) ;

addatend ( &p, 4) ;

addatend ( &p, 5) ;

display( p ) ;

printf ( "\nLength of linked list = %d\n", length ( p ) ) ;

/* code to compare two linked lists using recursion */

addatend ( &first, 1) ;

addatend ( &first, 2) ;

addatend ( &first, 3) ;

display( first ) ;

addatend ( &second, 1) ;

addatend ( &second, 2) ;

addatend ( &second, 3) ;

display( second ) ;

if ( compare ( first, second ) )

printf ( "\nBoth linked lists are EQUAL" ) ;

else

printf ( "Linked lists are DIFFERENT" ) ;

/* copy one linked list into another */

addatend ( &first, 1) ;

addatend ( &first, 2) ;

addatend ( &first, 3) ;

addatend ( &first, 4) ;

addatend ( &first, 5) ;

addatend ( &first, 6) ;

addatend ( &first, 7) ;

display ( first ) ;

printf ( "\n" ) ;

copy ( first, &second ) ;

display ( second ) ;

printf ( "\n" ) ;

addatend ( &p, 1) ;

addatend ( &p, 2) ;

addatend ( &p, 3) ;

addatend ( &p, 4) ;

addatend ( &p, 5) ;

addatend ( &p, 6) ;

addatend ( &p, 10) ;

display ( p ) ;

}

/* counts the number of nodes in a linked list */

length ( struct node *q )

{

static int l ;

/* if list is empty or if NULL is encountered */

if ( q == NULL )

return ( 0 ) ;

else

{

/* go to next node */

l = 1 + length ( q -> link ) ;

return ( l ) ;

}

}

/* compares 2 linked lists and returns 1 if linked lists are equal and 0 if unequal */

compare ( struct node *q , struct node *r )

{

static int flag ;

if ( ( q == NULL ) && ( r == NULL ) )

flag = 1 ;

else

{

if ( q == NULL || r == NULL )

flag = 0 ;

if ( q -> data != r -> data)

flag = 0 ;

else

compare ( q -> link, r -> link ) ;

}

return ( flag ) ;

}

/* copies a linked list into another */

copy ( struct node *q, struct node **s )

{

if ( q != NULL )

{

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

( *s ) -> data = q -> data ;

( *s ) -> link = NULL ;

copy ( q->link, & ( ( *s ) -> link ) ) ;

}

}

/* displays the contents of the linked list */

display ( struct node * q )

{

if ( q != NULL )

{

printf ( " %d", q -> data ) ;

display ( q -> link ) ;

}

else

return ;

}

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

addatend ( struct node **s, int num )

{

if ( *s == NULL )

{

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

( *s ) -> data = num ;

( *s ) -> link = NULL ;

}

else

addatend ( &( ( *s) -> link ), num ) ;

}

No comments: