Double Linked List

[DuckCowMooQuack]

Hey everyone,

I'm writing a program that at the moment has a single linked list. I want to make this list a double linked list so that it prints it out foreward and then revearses the order of the list by going back the other way. I have two structures, the first one contains an integer, and two links. One link points to the next one in the list, the other points to the one before it. At this point the link pointing to the next one in the list works but I don't know how to implement the one pointing to the one before it.

Here's my code at the present time...If you want to make more sense of it rather than me trying to explain.

#include<stdio.h>
#include<stdlib.h>

typedef struct aboxtype node;
typedef struct header headernode;
typedef node *link;             //pointer to a node
typedef headernode *link2;

struct aboxtype
{
 int dat;
 link next;
 link prev;
};

struct header
{
link front;
link rear;
};

link getnode( int x )
{
 link tmp;
 tmp = malloc( sizeof(node) );
 tmp->dat = x;
 tmp->next = NULL;
 tmp->prev = NULL;
 return tmp;      //returns the amount of memory to the main
}

void printlist( link2 *h )    
{
 link2 head = *h;
 link mov;
 int x;
 mov = head->front;
 
 while (mov != NULL)
  {
   x = mov->dat;     //sets it equal to dat
   printf("%d ", x);  //prints out the dat
   mov = mov->next;    //moves mov to next
  }
 printf("\n");
}

void printlistrev( link2 *h )
{
link2 head = *h;
link move;
int x;
move = head->rear;

while(move != NULL)
 {
  x = move->dat;
  printf("%d ", x);
  move = move->prev;
 }
 printf("\n"); 
}

void insertfront( link2 *h, link p ) //front of list
{
 link2 headernode = *h;
 if (headernode->front == NULL)
   {
	headernode->front = p;
	headernode->rear = p;
   }
   else
    {
	 p->next = headernode->front;
     p->prev = p;	 
	 headernode->front = p;
	}
 }

 // insert w after p
 void insertafter( link2 *h, link p, link w ) // if in middle of list
{
 link2 headernode = *h;
 w->next = p->next;
 p->next = w;
 }
 
 
link insertrear ( link2 *h, link p ) // end of list
{
 link tmp, tmp2;
 link2 headernode = *h;
 
 if (headernode->front == NULL)
   {
    headernode->front = p;
	headernode->rear = p;
   }
 else
   {
    tmp = headernode->front;
	
    while ( tmp->next != NULL )
      tmp = tmp->next;

      tmp->next = p;
	  tmp->prev = p;
    }
 }

int main()
{
 link p, q;
 link2 h, y;
 int i, x;


h = malloc( sizeof(headernode) );
h->front = NULL;
h->rear = NULL;

/*for (i = 1; i <= 10; ++i)
 {
 
  p = getnode(i);
    if (i % 2)
     insertfront(&h, p );
  else
    insertrear( &h, p);
	printlist( &h );
 }

printf("Final List: ");
printlist( &h );
*/
p = getnode(1);
insertrear(&h, p);
p = getnode(2);
insertrear(&h, p);
printlist( &h );
printf("\n");
printlistrev( &h );

/*
printf("List Reverse:\n");

printlistrev( &h );

q = getnode(33);
insertafter(&h, p, q);
printlist( &h );

//insert 44 after the node cont. 1
//assume that 1 is actually in the list

q = getnode(44);  // q is node to insert

p = h->front;
while (p->dat != 1)
 {
  p = p->next;
 }

insertafter(&h, p, q);
printlist( &h );
*/

return 0;
}

This at the moment (when all commented code is left commented) prints out the first list being 1 and 2. But then when the second list (the revearsed list) comes into play it does not work. This is where I need some help.

[quzah]

void addnode( node** l, node *n )
{
    if first node is null
        set first node to n
    else
        ...find the last or first node, doens't matter how you do it...
        n->prev = that node we found
        that node we found->next = n;
}

Just set prev and next correctly when you insert a list. Then, it works exactly like any other list movement, but instead of walking ->next you walk ->prev.


Quzah.