The Double-Linked List

Linked lists can be quite useful, for a number of reasons — though they take some time to wrap your mind around the concept. What's worse? The double-linked list.

Rather than merely link forward to the next structure, a double-linked list also links backward to the previous structure.

The following code demonstrates an interactive, double-linked list program. It's massive. Compare it with the linked-list code in this book to see the extra steps taken to maintain both forward and rearward pointers within the structure.

/* An interactive DOUBLE linked list program */
/* Dan Gookin, Beginning Programming with C For Dummies */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
struct typical {
    int value;
    struct typical *next;
    struct typical *previous;
};
struct typical *first;
struct typical *current;
struct typical *new;
int menu(void);
void add(void);
void show(void);
void delete(void);
void dump(void);
struct typical *create(void);
/* The main function works with input only.
   Everything else is handled by a function */
int main()
{
    int choice='\0';    /* get the while loop to spin */
    first=NULL;
    while(choice!='Q')
    {
        choice=menu();
        switch (choice)
        {
            case 'S':
                show();
                break;
            case 'A':
                add();
                break;
            case 'R':
                delete();
                break;
            case 'D':
                dump();
                break;
            case 'Q':
                break;
            default:
                break;
        }
    }
    return(0);
}
/* Display the main menu and collect input */
int menu(void)
{
    int ch;
    printf("S)how, A)dd, R)emove, D)ump, Q)uit: ");
    ch=getchar();
    while(getchar()!='\n')        /* remove excess input */
        ;
    return(toupper(ch));
}
/* Add an item to the end of the linked list */
void add(void)
{
    if(first==NULL)        /* Special case for the first item */
    {
        first=create();
        current=first;
        current->previous=NULL;
    }
    else                /* find the last item */
    {
        current=first;
        while(current->next)        /* last item == NULL */
            current=current->next;
        new=create();
        current->next=new;            /* update link */
        new->previous=current;
        current=new;
    }
    printf("Type a value: ");
    scanf("%d",&current->value);
    current->next=NULL;
    while(getchar()!='\n')        /* remove excess input */
        ;
}
/* Display all structures in the linked list */
void show(void)
{
    int count=1;
    if(first==NULL)            /* this list is empty */
    {
        puts("Nothing to show");
        return;
    }
    puts("Showing all records:");
    current=first;
    while(current)            /* last record == NULL */
    {
        printf("Record %d: %d\n",count,current->value);
        current=current->next;
        count++;
    }
}
/* Remove a record from the list */
void delete(void)
{
    int r,c;
    if(first==NULL)            /* check for empty list */
    {
        puts("No records to remove");
        return;
    }
    puts("Choose a record to remove:");
    show();
    printf("Record: ");
    scanf("%d",&r);
    while(getchar()!='\n')        /* remove excess input */
        ;
    c=1;
    current=first;
    while(c!=r)
    {
        if(current==NULL)    /* ensure that 'r' is in range */
        {
            puts("Record not found");
            return;
        }
        current=current->next;
        c++;
    }
    if(current->previous==NULL)        /* Special case for first record */
    {
        first=current->next;
        first->previous=NULL;
    }
    else                    /* point previous record at next */
    {
        current->next->previous=current->previous;
        current->previous->next=current->next;
    }
    printf("Record %d removed.\n",r);
    free(current);            /* release memory */
}
/* Display pointer references in the linked list */
/* Copied mostly from the show() function */
void dump(void)
{
    int count=1;
    if(first==NULL)            /* this list is empty */
    {
        puts("Nothing to dump");
        return;
    }
    puts("Pointer references");
    current=first;
    printf("Record #\tPrevious\tCurrent\tNext\n");
    while(current)            /* last record == NULL */
    {
        printf("Record %d:\t%p\t%p\t%p\n",
            count,
            current->previous,
             current,
            current->next);
        current=current->next;
        count++;
    }
}
/* Build an empty structure and return its address */
struct typical *create(void)
{
    struct typical *a;
    a=(struct typical *)malloc(sizeof(struct typical));
    if(a==NULL)
    {
        puts("Some kind of malloc() error");
        exit(1);
    }
    return(a);
}
  • Add a Comment
  • Print
  • Share
blog comments powered by Disqus
Advertisement

Inside Dummies.com