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:
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; }