9

LINKED LISTS—VARIANTS

In the previous chapter we considered linear linked lists. They are linear in their structure in the sense that list elements must be processed in a sequential manner from first to last. This is because the linked lists that we have seen have a head node which is directly accessible and each node contains an information part together with a link part that allow to move to its successor node, if it exists.

But in some cases, it may be convenient to use different kinds of accesses. In fact, other kinds of links between the nodes may also be helpful. In this chapter we consider some of these variants of linked lists such as linked stacks, linked queues, lists with fixed head, circular linked list, and so on.

9.1 LINKED STACKS

An array-based implementation of stacks that we have seen in chapter 6 loses its generality because the fixed size of the array puts a limitation on the size or length of the stack list. A pointer-based implementation of stacks will not impose such limitation on the stack size.

We know that a stack is nothing but a list such that its elements can be accessed only at one end which is known as stack top, that is, insertion (push) and deletion (pop) operations are done at the top of this stack. We have also seen that a linked list is accessible only through the head (start node) of the list. Clearly, if we create and maintain a linked list in such a way that all the elements that are inserted to the list are the front of the list and removal is also from the beginning of the list then it will follow the conditions of a stack. Hence, to implement a stack using pointers we may declare as below.

       typedef struct stack_node{
             char info[20]; /* Information part */
             struct stack_node *link; /* Link part*/
             } stacktype;
       stacktype *stack;

To define the abstract data type of stack we need to talk about the operations on stack also, which is already discussed at the time of array implementation.

Creating an empty stack may simply be written as

       create(stacktype **stackptr);
       {
             *stackptr = (stacktype *) NULL;
             return;
       }

The function to check whether a stack is empty, can now be written as

           empty(stacktype *stack)
           {
                 return(stack = = NULL);
           }

The push operation for stack is simply the insertion operation which is restricted to the beginning of the linked list. So the function push ( ) is the simplified form of the function insertnode ( ) of Section 8.5. The code for the function push ( ) is presented below.

 stacktype *push(stacktype *stack, char element[])
 {
       stacktype *ptr;
 
       ptr=(stacktype *)malloc(sizeof(stacktype));
       strcpy(ptr->info, element);
       ptr->link = stack;
       stack=ptr;
       return stack;
 }

It should be noted that this push function does not check whether the stack is full, which was checked in the push function of the array-based stack implementation. This is because the pointer implementation of stack does not impose any limit on the size of the stack and hence can never be full. Of course, the stack size is limited to the available memory in this case. But the pop function must check for the empty-stack condition in this implementation also, because the stack may have no element at a point of time and if we try to pop a stack element at that time it is an error condition. A code to pop ( ) function is given below.

 stacktype *pop(stacktype *stack, char element[])
 {
       stacktype *ptr;
 
       if (empty(stack))
       {
 
              printf(“Stack underflow !
”);
              exit(1); /* Exit with error condition */
       } else {
              strcpy(element, stack->info);
              ptr = stack;
              stack = stack->link;
              free(ptr);
       }
 }

9.2 LINKED QUEUES

The linked implementation of a queue is a simple modification of that of a stack. We recall that a queue is nothing but a list in which elements are removed only at one end called the front or head of the queue and elements are inserted only at the other end called the rear or tail of the queue. From the above definition it is very natural that a linked list will become a queue if the deletion occurs at the front of the list and any insertion is done at the end of the list. The deletion operation will then be very similar to the pop operation of the linked stack but the insertion operation will require a list traversal to get the pointer to the last node(element) of the list after which the insertion will take place. It is possible to avoid this list traversal if we keep the pointer to the last node of the list to a variable. So implementation of a linked queue needs the declaration of the form

       typedef struct queue_node{
                   char info[20]; /* Information part*/
                   struct queue_node *link; /*Link part*/
                   } nodetype;
       typedef struct {
                   nodetype *qfront, *qrear;
                   } queuetype;
       queuetype queue;

We have already seen that the operation commonly used on a queue includes the following.

The function create ( ) to create an empty queue may be simply written as

       create(queuetype *qptr)
       {
             qptr->qfront = qptr->qrear = (nodetype *)NULL;
             return;
       }

The function to check if the queue is empty or not may be implemented by using the function

       emptyQ(queuetype queue)
       {
             return(queue.qfront==NULL);
       }

The operation to insert an element at the end of the queue is basically inserting a node in the linked list (linked queue) after the node pointed by qrear of the queue. But this needs special attention because if the queue is an empty queue the insertion should take place at the front of the queue. The deletion operation can be implemented just like the pop ( ) function of a linked stack discussed in the last section. The function insertQ ( ) to add a node to the rear of the queue may be written as

 insertQ(queuetype *Qptr, char element[])
 {
       nodetype *ptr;
 
       ptr=(nodetype *)malloc(sizeof(nodetype));
       strcpy(ptr->info, element);
       if(empty (*Qptr))
       {
             Qptr->qfront = ptr;
             Qptr->qrear = ptr; 
       }
       else 
       {
             ptr->link=Qptr->qrear->link;
             Qptr->qrear->link=ptr;
             Qptr->qrear = ptr; 
       }
       return; 
 }

Similarly, the function deleteQ ( ) from the front of the queue may be written as

 nodetype *delete(queuetype *Qptr)
 {
       nodetype *ptr;
 
       if(emptyQ(*Qptr));
       { 
             printf(“Attempt to delete node from empty queue
”);
             exit(1);
       } else {
             ptr=Qptr->qfront;
             Qptr->qfront = ptr->link;
             if(Qptr->qfront==NULL)
                   Qptr->qrear=NULL;
             free(ptr);
       }
 }

9.3 VARIANTS OF LINKED LISTS

There are other varieties of linked lists which are useful for certain applications. These variants are nothing but modifications to standard linked list which also simplifies the basic list operations for typical applications.

9.3.1 Lists with Fixed Head Nodes

Each of the two basic list operations, insert and delete, considers two different cases.

The reason for considering these two cases is that the first node in a standard linked list does not have any predecessor but all other nodes have a predecessor. Clearly, if we can make a predecessor of the first node then characteristically it will not differ from other nodes of the linked list. Obviously, then the algorithms for insertion and deletion will be simple. We can achieve this by introducing a dummy head node at the beginning of a linked list which will actually store no list element in its information part. The link part of this dummy head node will point to the actual first node of the list and hence this dummy node serves the purpose of the predecessor of the actual first node of the linked list. Since this dummy node is fixed, insertion and deletion at the front of the list will occur at the node just after this dummy node, keeping the head of the list unchanged. Obviously, every link list in this implementation should have head node and so an empty list also must have such a node. We have already seen that a declaration of the following form is used to implement a linked list.

typedef struct list_node {
                        char info[20];
                        struct list_node *link;
                        } nodetype;
nodetype *head;

In this implementation the same declaration will do. But the algorithm for the basic list operations will be changed a little. To create an empty list, in this implementation instead of just setting head to NULL we may use a function create ( ) as below.

 create(nodetype **head)
 {
       *head = (nodetype *)malloc(sizeof(nodetype));
       (*head)->link = NULL;
       return;
 }

The call create (&head) where head is declared as a pointer to nodetype will create an empty list as below.

A function empty ( ) to check if a list is empty may be written as

       empty(nodetype *head)
       {
             return(head->link = = NULL);
       }

A linked list with fixed head node that holds the city names ‘Bangalore’, ‘Pune’, and ‘Surat’ will look like

As the dummy head node has an undefined information part, this area may be used to store the information regarding the type of the list members. For example, the above list may be presented as

In such implementation every node is having a predecessor node and so the insertnode ( ) function will require only two arguments.

 insertnode(nodetype *prevptr, char element[])
 {
       nodetype *ptr;
 
       ptr = (nodetype *) malloc(sizeof(nodetype));
       strcpy (ptr->info, element);
       ptr->link = prevptr->link;
       prevptr->link = ptr;
       return;
 }

The above function need not return pointer to head because head is fixed in this case with pointer to the dummy node having an undefined information part. In a similar way the function to delete a node from a linked list with fixed head node may be written as

 deletenode (nodetype *prevptr )
 {
       nodetype *ptr;
 
       ptr = prevptr->link;
       prevptr->link = ptr->link;
       free(ptr);
       return;
 }

The function traverse_list ( ) to print all the list members will change a little, and is presented below.

 traverse_list(nodetype *head)
 {
       nodetype *current;
 
       current = head->link;
       while(current != NULL)
       {
             printf(“%s
”, current->info);
             current=current->link;
       }
       return;
 }

9.3.2 Circular Linked List

Another useful data structure is a linked list in which the link part of the last node, instead of having NULL pointer value, points back to the head node of the list. These linked lists are known as circular linked lists and may be depicted as in the following where cllist is the pointer to the head node.

It is clear that every node in a circular linked list is having a predecessor and a successor. So, as in the case of linked lists with fixed head node, here also no special considerations are required for insertion and deletion of nodes. An empty circular linked list may be created by simply setting cllist to NULL and to check if a circular linked list is empty we need to check if cllist is NULL.

A function insertcllist ( ) for inserting an element into a circular linked list whose head is pointed by cllist after the node pointed by prevptr is shown below.

 nodetype *insertcllist(nodetype *cllist, nodetype *prevptr,
                        char element[])
 {
       nodetype *ptr;
       ptr=(nodetype *)malloc(sizeof(nodetype));
       strcpy(ptr->info, element);
       if(empty(cllist))
       {
             ptr->link=ptr;
             cllist=ptr;
       }
       else
       {
             ptr->link=prevptr->link;
             prevptr->link=ptr;
       }
       return cllist;
 }

A single-node circular linked list points to itself, as shown in the figure below. So we need to give special attention when the insertion takes place in a circular list with no elements.

Similarly, the function deletecllist ( ) may be written as

 nodetype *deleteclist(nodetype *cllist, nodetype *prevptr)
 {
       nodetype *ptr;
 
       if(empty(cllist))
       {
             printf(“Attempt to delete node from empty list 
”);
             exit(1);
       }
       else
       {
             ptr = prevptr-> link ;
             if(ptr == prevptr) /* Single node circular list /*
                   cllist = NULL;
             else
                   prevptr->link = ptr->link;
             free(ptr);
             return cllist;
       }
 }

Obviously, we need to give special attention to the case where we want to delete from a single-node circular list .The function traverse_cllist ( ) to traverse a circular list is a simple modification of the function to traverse a simply linked list and is of the following form.

 traverse_cllist(nodetype   *cllist)
 {
       nodetype *current;
 
       if(!empty(cllist))
       {
             current = cllist;
             do
             {
                   printf (“%s
”, current-> info);
                   current = current->link;
             } while (current!=cllist);
       }
       return;
 }

Note that in this case do _while loop is used instead of while loop. If we implement a queue as a circular linked list, it may be advantageous to maintain one pointer cllist to the tail node instead of the head node. Then to maintain a queue we need only one pointer cllist (the rear) to access both the front (cllist->link) and the rear (cllist) of the queue. Some other application may use a circular linked list with fixed head node to simplify the algorithms of the application.

9.3.3 Doubly Linked Lists

So far, we were restricted to only singly linked lists in the sense that a node may have only one link part in it which points to the successor of the node. Some applications might also need to get the predecessor of a node frequently. In case of singly linked lists, accessing the predecessor of a node needs a search from the beginning and hence is inefficient. Such applications may employ another data structure which is a doubly linked list in which each node contains two links, one to the successor node in the list and other to the predecessor node in the list as shown below.

These lists are also known as symetrically linked lists. It is very clear that with such lists it is possible to move to either direction through the list by keeping only one pointer. Though traversal in both directions is possible, it is achieved at the cost of extra space for the predecessor links. As a variant of this, like in the singly linked list, we can introduce fixed head node for doubly linked list also. This will simplify the basic operations on lists. Furthermore, for easy access to either end of the list we can make this doubly linked list with dummy head node as a circular one also. With such modifications our doubly linked list will take the following form.

The pointer implementation of doubly linked list requires the following declarations.

typedef struct listnode{
                        char element[20]; /* Information part */
                        struct listnode *plink, slink ;
                              /* Predecessor & Sucessor links */
                      } nodetype;
nodetype *dllist;

An empty doubly linked list may be created by using the function

 createD(nodetype **nodeptr)
 {
       *nodeptr = (nodetype *) malloc(sizeof(nodetype));
       (*nodeptr)->plink = (*nodeptr)->slink = (nodeptr *) NULL;
       return;
 }

A call to createD(&dllist) will create an empty doubly linked list which may be depicted as

The function emptyD ( ) to check if a doubly linked list is empty may be written as follows.

       emptyD(nodetype *nodeptr)
       {
             return (nodeptr->plink == nodeptr);
       }

In fact, we may return the value of the expression nodeptr->slink = = NULL also.

Inserting a node into a doubly linked list after the node pointed by prevptr needs a little care. Consider the portion of such a doubly linked list as depicted below which contains the city names ‘Bangalore’ and ‘Surat’. Let prevptr point to the node with city name ‘Bangalore’ and we need to insert the node with city name ‘Chennai’ after it.

Let ptr points to the node be inserted. For insertion, the order of the link adjustments is as follows. First, we need to set the predecessor and successor links of the node to be inserted. That is, (i) ptr->plink = prevptr; and (ii) ptr->slink = prevptr->slink;

The above two instructions may be in either order within themselves. These are used to set the link fields of the node we are inserting. Now the resetting of links is to be made so that the node pointed by ptr is inserted at its proper place and these may be written as (iii) prevptr->slink = ptr; and (iv) ptr->slink->plink = ptr;

These reset instructions may also come in either order but we must be careful that first set instruction and then the reset instructions should be done to insert a node in doubly linked lists. The order of these instructions are marked in the figure with dashed lines. The above discussion leads to the following function insertdllist ( ) to insert a node to a doubly linked list.

 insertdllist(nodetype *prevptr, char element[])
 /* prevptr points to node after which insertion take place */
 {
       nodetype *ptr;
 
       ptr=(nodetype *) malloc(sizeof(nodetype));
       strcpy(ptr->info, element);
       ptr->plink = prevptr;
       ptr->slink = prevptr->slink;
       prevptr->slink = ptr;
       ptr->slink->plink = ptr;
       return;
 }

The deletion operation is more simple and only requires to reset the slink part of the predecessor of the node to delete and the plink part of its successor. The function deletedllist ( ) may be written as

       deletedllist(nodetype *nodeptr)
       {
          /* nodeptr points to the node to delete */
             nodeptr->plink->slink = nodeptr->slink;
             nodeptr->slink->plink = nodeptr->plink;
             free(nodeptr);
             return;
       }

9.4 APPLICATIONS OF LINKED LISTS

There are several applications of linked lists. Out of these enormous applications we choose to present two applications, which seem to be sufficient to explain the linked-list functions. First we will show a pointer implementation of sparse polynomials which may be considered as an application of singly linked list with fixed head node. Next we present an application of circular doubly linked list with fixed head: large integer arithmetic.

9.4.1 Sparse Polynomial Manipulation

A polynomial in x (a single variable) is expressed as

p(x) = a₀ + a₁x + a₂x² +…+ a_nxⁿ

where a₀, a₁, a₂,…, a_n are constant coefficients in the polynomial. The degree of the polynomial p(x) is n where n is the largest power of x in p(x) with nonzero a_n. A constant is a polynomial of degree zero.

Clearly, the polynomial can be represented as the list of constant coefficients (a₀, a₁…, a_n).

This list may be stored in an array. But this array representation of polynomials will be worthwhile if the value of n is not too large and most of the coefficients a are non-zero. In fact, for a sparse polynomial, where most of the coefficients as are zeros, this array representation is highly inefficient. For example, consider the sparse polynomial

u(x) = 7 - 7x⁵¹ + 5x⁹⁹

For storing u(x) the array implementation as shown below needs to reserve an array of 100 elements of which only three elements will be non-zero and other elements will have no use and hence highly costly with respect to storage requirements.

u(x)<=>(7,0,…,-7,0,…,5)

corresponding exponent positions (0,1,…,51,52,…,99)

A little understanding suggests another representation of a polynomial which uses a list of (coefficient, exponent) pairs instead of a list of coefficients only. With this representation, our polynomial u(x) may be identified by the following list of pairs

u(x)<=>((7,0),(-7,51),(5,99))

The above discussion suggests that a linked implementation is more appropriate to represent a polynomial where each node in the list has two members in the information part and a single member for the link to its successor, as depicted in the following.

Obviously, the coefficient member of a node is always non-zero.

For such a linked implementation of polynomials, we may use the declarations of the following form.

       typedef struct list_node{
                               float co-eff;
                               int expo;
                               struct list_node *link;
                               } nodetype;
       nodeptr, *uptr,*vptr;

Here as above, uptr and vptr may be used as pointers to head nodes of two different lists, each of them representing a different polynomial. To simplify the list algorithms we choose to represent a polynomial by a linked list with fixed head node. Thus the polynomials

may be represented as the following linked lists pointed by uptr and vptr, respectively.

For an illustration of how to process such linked representation of polynomials we consider the polynomial addition operation. We begin by creating an empty linked list with fixed head node. Let this empty list be pointed by fptr. This linked list pointed by fptr will hold the linked list representation of the polynomial which we get after adding u(x) and v(x). The empty created list will look like

To create such an empty list we may execute the following statements

       fptr=(nodetype *)malloc(sizeof(nodetype));
       fptr->link=NULL;

which leave the coefficient and exponent part of the node (fixed head) as undefined.

As we have considered linked lists with fixed head nodes, the pointers uptr, vptr, and fptr are fixed. So we will need three auxiliary pointers which will run through three lists. Let u, v, and f be the three auxiliary pointers that will run through the linked lists pointed by uptr, vptr, and fptr, respectively. At first we initialise these three auxiliary pointers as below

             u = uptr->link;
             v = vptr->link;
             and f = fptr;

The above initialization of pointers sets u and v to point to the current nodes of uptr and vptr to be processed, respectively, and f points to the last node of fptr. We compare the exponents of the nodes pointed by u and v at every step. If the exponents are equal, then the coefficient parts of these nodes are added. If this sum is nonzero, a node is created with coefficient part as this sum, exponent part as the common exponents of the nodes pointed by u and v. This created node is then attached at the end of the list pointed by fptr. That is, the created node is attached to fptr after the node pointed by f, the last node. But if this sum is zero, then no node is added to fptr, instead u and v are advanced to point to their successors.

On comparison of the exponent in the nodes pointed by u and v if we find that they are different a node is created which is a copy of the node containing the smaller exponent with its link part set to NULL and inserted at the end of the list pointed by fptr. Then the pointers (u or v) which point to the node with smaller exponent and fare advanced to point the successor node of the corresponding list.

The above process is continued till u or v becomes NULL. The changes at each step in the lists pointed by uptr, vptr, and fptr are shown below.

Step 1:

Step 2:

Step 3:

Step 4:

When the end of one of the lists (uptr or vptr) is reached, the remaining nodes of the other list are attached at the end of fptr, to get the linked representation of sum polynomial (pointed by fptr).

Actual C functions for such polynomial operations are not written here and are left to the reader. We can build algorithms for other polynomial operations such as multiplication of two polynomials and evaluation of a polynomial for a given value of x with little care.

9.4.2 Large Integer Arithmetic

We know that the size of a number (integer) that can be stored in computer memory is limited to the word size of the system being used. In fact, the highest positive integer number that can be stored in the n bit word is (2^n-1 - 1) in 2's complement representation. Clearly, to store and manipulate positive integers which are larger than this size is not possible to do in a straight forward manner. Rather, first we need to choose a data structure that can be used to represent a large integer.

It seems very natural to choose a linked list as the data structure to represent a large integer, because there is no upper bound on the number of digits in the integer. For simplicity, we consider large positive integers only. The processing of such linked list representation of large positive integers will require a frequent back and forth movement through the linked list. So a circular doubly linked list representation would be a better choice in this case. To make the list operations simpler we choose the circular linked list with fixed head nodes to represent a large positive integer. Each node in this linked list will store a three digit integer (say) except possibly the first node, which corresponds to a group of three consecutive digits in the large positive integer. The first node may contain an integer which might have less than three digits also. For example, the positive integer 72, 165, 834, 982 is represented as the following circular linked list with fixed head pointed by operand as

To create this doubly linked list for the above integer the input should be in a group of three digits separated by blanks as shown below.

72       165     834     982

We need a declaration of the form given below to create such lists.

       typedef struct list_node{
                                int info;
                                struct list_node *plink, *slink;
                                } nodetype;
       nodetype *nodeptr;

To create a circular doubly linked list with fixed head pointed by nodeptr we first create a node of nodetype pointed by nodeptr as follows.

       nodeptr = (nodetype *) malloc(sizeof(nodetype));
       nodeptr->plink = nodeptr->slink = nodeptr;

This may be depicted as

The first part of the large integer (in this case 72) is read and stored it to variable num (say). A new node is then created whose info member is holding the value of num.

This may be done by

       ptr=(nodetype *)malloc(sizeof(nodetype));
       ptr->info = num;

ptr is the pointer to this created node. Now this node is inserted as the last node of the circular doubly linked list pointed by nodeptr. This may be achieved by executing the following code:

       ptr->plink = nodeptr->plink;
       ptr->slink = nodeptr;
       nodeptr->plink->slink = ptr;
       nodeptr->plink = ptr;

The following figure shows the state of the list.

The same process is repeated by reading the next part of the large integer and is continued until we finish with all the parts of the integer that has come in the input. A function to read such a long integer forming a circular doubly linked list with fixed head is given below. This function readint ( ) returns a pointer to nodetype which is the pointer to the head of the linked list representing the large integer.

 nodetype *readint( )
 {
       nodetype *nodeptr,*ptr;
       int num;
       nodeptr = (nodetype *)malloc(sizeof(nodetype));
       nodeptr->plink = nodeptr->slink = nodeptr;
       while(scanf(“%d”, &num) != EOF)
       {
             ptr = (nodetype *)malloc(sizeof(nodetype));
             ptr->info = num;
             ptr->plink = nodeptr->plink;
             ptr->slink = nodeptr;
             nodeptr->plink->slink = ptr;
             nodeptr->plink = ptr;
       }
       return nodeptr;
 }

Consider the following circular doubly linked lists with head nodes pointed by operand1 and operand2 representing two large integers 2,583, 647 and 72,165, 834, 982.

To add the integers represented by the above doubly linked lists we traverse the lists from right to left (starting from the end of the list), add the two three digit integers in the corresponding nodes and carry digit drawn from the previous node processed to get the sum and carry digit. We then create a node to store this sum and insert it at the front of another circular doubly linked list with fixed head that will represent the total of the two given large integers.

For a better understanding we present a C program in the following example 9.1 that adds and prints two large integers given as input. The integers are represented as a doubly linked list.

Example 9.1

 # include  <stdio.h>
 # define  SIZE 1000
 # define  LEN 3
 typedef struct list_node{
             int info;
             struct list_node *plink, *slink;
             } nodetype;
 nodetype *operand1, *operand2, *total, *readint( ), *addnodeint( );
 main( )
 {
       printf (“Enter two integers in group of %d 
”, LEN);
       printf (“
separating each group by space :
”);
       printf (“First integer :”);
       operand1 = readint( );
       print_dlist(operand1);
       printf (“Second integer :”);
       operand2 = readint( );
       print_dlist(operand2);
       total = addnodeint(operand1, operand2);
       printf(“Sum of these two integers = ”);
       print_dlist(total);
       return;
 }
 nodetype *readint( )
 {
       nodetype *nodeptr, *ptr;
       int  num;
       /* function to read from stdin a big integer in groups
          of LEN number of digits. A circular doubly linked
          list with fixed head node is formed with these
          integer values. The pointer to the head node is
          returned */
          nodeptr = (nodetype *)malloc(sizeof(nodetype));
          nodeptr->plink = nodeptr->slink = nodeptr;
       while (tokenise(&num) != EOF)
       {
             ptr = (nodetype *)malloc(sizeof(nodetype));
             ptr->info = num;
             ptr->plink = nodeptr->plink;
             ptr->slink = nodeptr;
             nodeptr->plink->slink = ptr;
             nodeptr->plink = ptr;
       }
       return nodeptr;
 }
 tokenise(int *pi)
 {
       static char ibuf[50];
       static int i=0, cc=0;
       int c, n=0;
       if (cc = = 0)
       {
             while ((c=getchar( )) != ‘
’)
                   ibuf[cc++] = c;
             ibuf[cc] = ‘
';
       }
       if (i = = cc)
       {
             i = cc = 0;
             return -1;
       }
       while(!isdigit(ibuf[i]))
             i + +;
       do    {
             n = n*10 + ibuf[i] - ‘O';
       } while( isdigit(ibuf[++i]) );
       *pi = n;
       return 0;
 }
 
 print_dlist(nodetype *nodeptr)
 {
 /* function to traverse the circular doubly linked list with
fixed head node pointed by nodeptr and prints the information
contents of all the nodes */
       nodetype *ptr;
 
       ptr=nodeptr->slink;
       while (ptr !=nodeptr)
       {
             printf(“%d,”, ptr->info);
             ptr = ptr->slink;
       }
       putchar (‘
’);
       return;
 }
 
 nodetype   *addnoteint(nodetype  *ptr1,  nodetype  *ptr2)
 nodetype   *ptr1,  *ptr2;
 {
 /* function to add two integers represented in circular doubly
linked list with fixed head node pointed by ptr1
& ptr2 and store the resulting integers into another
identical type of list pointed by the returned value of the
function */
 
       nodetype *temp1, *temp2, *total, *ptr, *headptr;
       int sum, carry = 0;
 
       temp1=ptr1->plink; /* pointer to the last node of 1st list */
       temp2=ptr2->plink; /* pointer to the last node of 2nd list */
       total = (nodetype *)malloc(sizeof(nodetype));
       total->plink = total->slink = total; /* Set initial list */
       while ( temp1 != ptr1 && temp2 != ptr2 ) .
       {
       /* add integers in nodes pointed by temp1 & temp2 */
             sum = temp1->info + temp2->info + carry;
             carry = sum / SIZE;
             attach (total, sum%SIZE);
             temp1 = temp1-> plink;
             temp2 = temp2-> plink;
       }
       ptr = (temp1 = = ptr1) ? temp2 : temp1;
       headptr = (ptr = = temp1) ? ptr1 : ptr2; /* select list to
                                               continue with */
       while (ptr != headptr)
       {
             sum = ptr->info + carry;
             carry = sum / SIZE;
             attach (total, sum%SIZE);
             ptr = ptr->plink;
       }
       if (carry)
             attach (total, carry);
       return total;
 }
 
 attach (nodetype *ptr, int element)
 {
 /* function to insert a node with element as information
part at the front of the circular doubly linked list with
fixed head node pointed by ptr */
 
       nodetype   *temp;
 
       temp = (nodetype *)malloc(size of (nodetype));
       temp->info = element;
       temp->slink = ptr->slink;
       temp->plink = ptr;
       ptr->slink->plink = temp;
       ptr->slink = temp;
       return;
 }

EXERCISES