8.6. Other self-referential data structures

In addition to linked lists, it is also possible to build other types of self-referential data structures. Some other data structure examples are double link lists, stacks, queues, and binary trees. The basic implementation of these structures is not very difficult and we will not take much time in class to discuss these data structures.

8.6.1. Stacks with Linked Lists

Stack are a very useful storage container. The basic concept of a stack is last in, first out. So the two main operations used with stacks are push and pop. A push operation adds a value to the top of the stack, while a pop operation returns and removes the top value from the stack. They can be implemented with either an array or using linked lists. The main advantage of the linked list approach is that the memory can grow and shrink as needed. In either case the most difficult part of implementing push and pop is just to maintain where the top of the stack is.

In the following implementations of push and pop, the top node is treated as a static node. This allows us to just pass that top node to the functions and let the functions take care of the details. The functions know that the real stack is below the top node. An alternative that works equally well is to use a pointer to the top of stack and then another pointer to that pointer (pointer to pointer). For example:

int main(void)
{
    Stack *base, **top;

    base = NULL;
    top = &base;
    ...

We need a fixed variable that points to the top of the stack because where it points to will change. We could always pass the memory address of that pointer variable, but it is more convenient to use another variable (pointer to pointer) that points to it.

To use these functions, it is necessary to set a few things up in advance.

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

typedef struct node {
    double value;
    struct node *next;
} Stack;

void push( Stack *, double );
double pop( Stack * );

int main(void)
{
    Stack base, *top;

    base.value = 0.0;
    base.next = NULL;
    top = &base;

    push(top, 5);
    printf("%lf\n", pop(top));
    return 0;
}

8.6.1.1. push

void push( Stack *top, double newdata )
{
/*
    * Stack function builds the dynamic stack below top, which
    * must already exist as a node and is static.
    */
    assert( top != NULL );
    Stack *new;
    if( (new = (Stack *)malloc(sizeof(Stack))) == NULL) {
        printf( "Memory Allocation error.\n" );
        return;
    }
    new->next = top->next;  // put old top of data below new.
    new->value = newdata;
    top->next = new;
}

8.6.1.2. pop

double pop( Stack *top )
{
    /*
    * Stack function builds the dynamic stack below top, which
    * must already exist as a node and is static.
    *

    * The main reason for keeping the top of the stack static is to make
    * it easy to maintain the new top of the stack and also to return the
    * top data value that is popped or removed from the stack.
    */

    double value;
    Stack *tmp;

    assert( top != NULL );
    tmp = top->next;
    if( tmp != NULL ) {
        value = tmp->value;
        top->next = tmp->next;
        free( tmp );
        return value;
    }
    else
        return top->value;
}