Linked lists

Introduction

A linked list is an implementation type and not an abstract data type.

A linked list can be used to implement a great number of abstract data types such as sets, stacks, and queues. When we say list or linked list, we usually mean simply linked list. If we are talking about a doubly linked lists, we normally say so explicitly.

Usually, when we use a list, we assume that the elements on the list are in the form of pointers, in other words we respect uniform reference semantics.

We use linked lists is so many other parts of this document, that it is worthwhile to give the definition once and for all here.

The definition

For the purpose of this document, we shall define a list as a pointer to a structure of type cell like this: 
  typedef struct cell *list;

  struct cell
  {
    void *element;
    list next;
  };
Notice that as usual, we prefer to manipulate the pointer rather than the structure itself. Also notice the names of the fields that we try not to change so that code that uses the list for implementation is easier and faster to read.

Although a list is not an abstract data a type, we often need the same operations on a list. The most basic operation is what is known as a constructor, whose purpose is to construct new list elements. Such a constructor takes an element, a list to be assigned to the next field, and returns a new list with those fields filled in. The name of the constructor does not matter so much, but we have borrowed the name from the Lisp programming language, namely cons. Here is the code: 

  list 
  cons(void *element, list l)
  {
    list temp = malloc(sizeof(struct cell));
    temp -> element = element;
    temp -> next = l;
    return temp;
  }
While we could also define accessor functions that take a list and return its fields, we don't think that is necessary. Since a list is not an abstract data type, we may use the pre-defined C syntax l -> element and l -> next to access the fields.

However, there is a very common situation in which given a list, one wants to deallocate the first element and use the second. Such an operation can greatly simplify code that uses lists. Here is the code: 

  list 
  cdr_and_free(list l)
  {
    list temp = l -> next; 
    free(l);
    return temp;
  }

Creating a reusable list module

While we recognize that a list is not an abstract data type, we can still turn it into a useful reusable module in the form of a header file and an implementation file. Since it is not an abstract data type, we can (and must) put the struct declaration in the header file, something which is never done with abstract data types. Here is the header file: 
  #ifndef LIST_H
  #define LIST_H

  typedef struct cell *list;
  
  struct cell
  {
    void *element;
    list next;
  };

  extern list cons(void *element, list l);
  extern list cdr_and_free(list l);

  #endif
And here is the implementation file: 
  #include "list.h"
  #include 
 
  list
  cons(void *element, list l)
  {
    list temp = malloc(sizeof(struct cell));
    temp -> element = element;
    temp -> next = l;
    return temp;
  }

  list 
  cdr_and_free(list l)
  {
    list temp = l -> next; 
    free(l);
    return temp;
  }