Online Test Banks
Score higher
See Online Test Banks
eLearning
Learning anything is easy
Browse Online Courses
Mobile Apps
Learning on the go
Explore Mobile Apps
Dummies Store
Shop for books and more
Start Shopping

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

Dummies.com Sweepstakes

Win $500. Easy.