ERASING A LINKED LIST

< Day Day Up >

ERASING A LINKED LIST

Introduction

Erasing a linked list involves traversing the list starting from the first node, freeing the storage allocated to the nodes, and then setting the pointer to the list to NULL . If p is a pointer to the start of the list, the actions specified through the following code will erase the list:

while(p != NULL) { temp = p; p = p->link; free(t); }

But a better strategy of erasing a list is to mark all the nodes of the list to be erased as free nodes without actually freeing the storage of these nodes. That means to maintain this list, a list of free nodes, so that if a new node is required it can be obtained from this list of free nodes.

Program

Here is a complete program that erases a list pointed to by p by adding the nodes of a list pointed by p to the free list.

# include <stdio.h> # include <stdlib.h> struct node { int data; struct node *link; }; struct node *insert(struct node *, int); void erase(struct node **,struct node **); void printlist ( struct node * ); void erase (struct node **p, struct node **free) { struct node *temp; temp = *p; while (temp->link != NULL) temp = temp ->link; temp->link = (*free); *free = *p; *p = NULL; } struct node *insert(struct node *p, int n) { struct node *temp; if(p==NULL) { p=(struct node *)malloc(sizeof(struct node)); if(p==NULL) { printf("Error\n"); exit(0); } p-> data = n; p-> link = NULL; } else { temp = p; while (temp-> link!= NULL) temp = temp-> link; temp-> link = (struct node *)malloc(sizeof(struct node)); if(temp -> link == NULL) { printf("Error\n"); exit(0); } temp = temp-> link; temp-> data = n; temp-> link = NULL; } return (p); } void printlist ( struct node *p ) { printf("The data values in the list are\n"); while (p!= NULL) { printf("%d\t",p-> data); p = p-> link; } } void main() { int n; int x; struct node *start = NULL ; struct node *free=NULL; /* this code will create a free list for the test purpose*/ printf("Enter the number of nodes in the initial free list \n"); scanf("%d",&n); while ( n-- > 0 ) { printf( "Enter the data values to be placed in a node\n"); scanf("%d",&x); free = insert ( free,x); } /* this code will create a list to be erased*/ printf("Enter the number of nodes in the list to be created for erasing \n"); scanf("%d",&n); while ( n-- > 0 ) { printf( "Enter the data values to be placed in a node\n"); scanf("%d",&x); start = insert ( start,x); } printf("The free list islist is:\n"); printlist ( free ); printf("The list to be erased is:\n"); printlist ( start); erase(&start,&free); printf("The free list after adding all the nodes from the list to be erased is:\n"); printlist ( free ); }

Explanation

The method of erasing a list requires adding all the nodes of the list to be erased to the list of free nodes, as shown here.

click to expand

< Day Day Up >

POLYNOMIAL REPRESENTATION

Introduction

One of the problems that a linked list can deal with is manipulation of symbolic polynomials . By symbolic, we mean that a polynomial is viewed as a list of coefficients and exponents. For example, the polynomial

3 x ² +2 x +4,

can be viewed as list of the following pairs

(3,2),(2,1),(4,0)

Therefore, we can use a linked list in which each node will have three fields, as shown in Figure 20.10.

A polynomial 10 x ⁴ + 5 x ² + 1 can be represented as shown here:

Figure 20.10: Polynomial representation.

The procedure to add these two polynomials using the linked list is in the following program.

Program

# include <stdio.h> # include <stdlib.h> struct pnode { int exp; double coeff; struct pnode *link; }; struct pnode *insert(struct pnode *, int,double); void printlist ( struct pnode * ); struct pnode *polyadd(struct pnode *, struct pnode *); struct pnode *sortlist(struct pnode *); struct pnode *insert(struct pnode *p, int e,double c) { struct pnode *temp; if(p==NULL) { p=(struct pnode *)malloc(sizeof(struct pnode)); if(p==NULL) { printf("Error\n"); exit(0); } p-> exp = e; p->coeff = c; p-> link = NULL; } else { temp = p; while (temp-> link!= NULL) temp = temp-> link; temp-> link = (struct pnode *)malloc(sizeof(struct pnode)); if(temp -> link == NULL) { printf("Error\n"); exit(0); } temp = temp-> link; temp-> exp = e; temp->coeff = c; temp-> link = NULL; } return (p); } /* a function to

sort

a list */ struct pnode *sortlist(struct pnode *p) { struct pnode *temp1,*temp2,*max,*prev,*q; q = NULL; while(p != NULL) { prev = NULL; max = temp1 = p; temp2 = p -> link; while ( temp2 != NULL ) { if(max -> exp < temp2 -> exp) { max = temp2; prev = temp1; } temp1 = temp2; temp2 = temp2-> link; } if(prev == NULL) p = max -> link; else prev -> link = max -> link; max -> link = NULL; if( q == NULL) q = max; /* moves the node with highest data value in the list pointed to by p to the list pointed to by q as a first node*/ else { temp1 = q; /* traverses the list pointed to by q to get pointer to its last node */ while( temp1 -> link != NULL) temp1 = temp1 -> link; temp1 -> link = max; /* moves the node with highest data value in the list pointed to by p to the list pointed to by q at the end of list pointed by q*/ } } return (q); } /* A function to add two polynomials */ struct pnode *polyadd(struct pnode *p, struct pnode *q) { struct pnode *r = NULL; int e; double c; while((p!=NULL) && (q != NULL)) { if(p->exp > q->exp) { r = insert(r,p->exp,p->coeff); p = p->link; } else if(p->exp < q->exp) { r = insert(r,q->exp,q->coeff); q = q->link; } else { c = p->coeff + q->coeff; e = q->exp; r = insert( r, e,c); p = p->link; q = q->link; } while(p != NULL) { r = insert( r, p->exp,p->coeff); p = p->link; } while(q!=NULL) { r = insert( r, q->exp,q->coeff); q = q->link; } return(r); } void printlist ( struct pnode *p ) { printf("The polynomial is\n"); while (p!= NULL) { printf("%d %lf\t",p-> exp,p->coeff); p = p-> link; } } void main() { int e; int n,i; double c; struct pnode *poly1 = NULL ; struct pnode *poly2=NULL; struct pnode *result; printf("Enter the terms in the polynomial1 \n"); scanf("%d",&n); i=1; while ( n-- > 0 ) { printf( "Enter the exponent and coefficient of the term number %d\n",i); scanf("%d %lf",&e,&c); poly1 = insert ( poly1,e,c); } printf("Enter the terms in the polynomial2 \n"); scanf("%d",&n); i=1; while ( n-- > 0 ) { printf( "Enter the exponent and coefficient of the

term

number %d\n",i); scanf("%d %lf",&e,&c); poly2 = insert ( poly2,e,c); } poly1 = sortlist(poly1); poly2 = sortlist(poly2); printf("The polynomial 1 is\n"); printlist ( poly1 ); printf("The polynomial 2 is\n"); printlist ( poly2 ); result = polyadd(poly1,poly2); printf("The result of addition is\n"); printlist ( result ); }

Explanation

If the polynomials to be added have n and m terms, respectively, then the linked list representation of these polynomials contains m and n terms, respectively.
Since polyadd traverses each of these lists, sequentially, the maximum number of iterations that polyadd will make will not be more than m + n . So the computation time of polyadd is O( m + n ).