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.
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;
}
#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" #includelist 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; }