17 September 2009

doubly linked list in C

list *reverse(list *current)
{
list *prev = NULL;
list *next = NULL;

while(current)
{
next = current->next; //tricky: save the next node
current->next = prev; //point current to previous
current->prev = next; //point current to next
prev = current;
current = next;
}

return prev;
}

---------------------dlist.c---------------------
#include <stdio.h>
#include <stdlib.h>

typedef struct list{
int val;
struct list *next;
struct list *prev;
}list;

list *getfirst(list *head)
{
while(head && head->prev) head = head->prev;
return head;
}

list *getlast(list *head)
{
while(head && head->next) head = head->next;
return head;
}

void print(list *head1)
{
list *head = NULL;
list *end = NULL;

head = head1;
printf("to next: ");
while(head)
{
printf("%d->", head->val);
head = head->next;
}
printf("NULL\n");

head = getlast(head1);
printf("to prev: ");
while(head)
{
printf("%d->", head->val);
head = head->prev;
}
printf("NULL\n");
}


list *insert(list *head, int val)
{
list *new = (list*)malloc(sizeof(list));
new->val = val;
new->prev = NULL;
new->next = head;

if(head) head->prev = new;

return new;
}

list *reverse(list *current)
{
list *prev = NULL;
list *next = NULL;

while(current)
{
next = current->next; //tricky: save the next node
current->next = prev; //point current to previous
current->prev = next; //point current to next
prev = current;
current = next;
}

return prev;
}

int main()
{
list *head = NULL;

head = insert(head, 10);
head = insert(head, 20);
head = insert(head, 60);
head = insert(head, 51);
head = insert(head, 73);
head = insert(head, 19);
head = insert(head, 10);
head = insert(head, 81);
head = insert(head, 95);
printf("before reverse:\n");
print(head);

printf("after reverse:\n");
head = reverse(head);
print(head);

return 0;
}
-------------------------------------------------

Output:
before reverse:
to next: 95->81->10->19->73->51->60->20->10->NULL
to prev: 10->20->60->51->73->19->10->81->95->NULL
after reverse:
to next: 10->20->60->51->73->19->10->81->95->NULL
to prev: 95->81->10->19->73->51->60->20->10->NULL

No comments:

Post a Comment