A linked list is a representation of a sequence of objects, all of the same type, in the random access memory of a computer. Each element of the sequence is stored in a cell of the list: the first element in the first cell, the second element in the second cell, and so on.

## The structure of a linked list

A linked list is a sequence of cells. Each cell contains an object (all the objects are of the same type) and the address of the following cell.  In this chapter, we assume that the objects stored in the cells are of type int.  Each cell is a struct that can be defined as follows:

```   struct record {
int            contents;
struct record *next;
};
```

We shall treat the cells as a new data type and to assign a name to this new type:

```   typedef struct record cell;
```

A cell  c  and a pointer  p  to a cell can be declared as follows:

```   cell  c;
cell *p;
```

If c is a cell then  c.contents  is the payload of the cell and  c.next  is the address of the next cell.  If  p  is the address of a cell, then  p->contents  is the payload of the cell and  p->next  is the address of the next cell.  If  p  is the address of the last cell of the list then  p->next  is  NULL.

(The figure can give the false impression that the cells of the list occupy consecutive positions in the memory. Actually, the cells are usually spread over the memory in an unpredictable manner.)

## Exercises 1

1. Alternative declaration.  Check that the declaration of the cell type could also be written as follows:
```typedef struct record {
int            contents;
struct record *next;
} cell;
```
2. Alternative declaration.  Check that the declaration of the cell type could also be written as follows:
```typedef struct record cell;
struct record {
int   contents;
cell *next;
};
```
3. Alternative declaration.  Check that the declaration of the cell type could also be written as follows:
```typedef struct cell cell;
struct cell {
int   contents;
cell *next;
};
```
4. Size of a cell.  Compile and execute the following program:
```int main (void) {
printf ("sizeof (cell) = %d\n",
sizeof (cell));
return EXIT_SUCCESS;
}
```

(Do not mistake lst for 1st.)  The list is empty (that is, has no cells) if and only if lst == NULL.

Linked lists are recursive animals. To make this apparent, consider the following observation:  if lst is a nonempty linked list then  lst->next  is also a linked list.  Many algorithms for linked lists become simpler when written in recursive form.

Example.  The following recursive function prints the contents of the linked list lst:

```void printlist (cell *lst) {
if (lst != NULL) {
printf ("%d\n", lst->contents);
printlist (lst->next);
}
}
```

And here is an iterative version of the same function:

```void printlist (cell *lst) {
cell *p;
for (p = lst; p != NULL; p = p->next)
printf ("%d\n", p->contents);
}
```

## Exercises 2

1. Counting.  Write a function to count the number of cells of a linked list. Write two versions: one iterative and one recursive.
2. Height.  The height of a cell c in a linked list is the distance between c and the end of the list. More precisely, the height of c is the number of steps in the path that goes from c to the last cell of the list.  Write a function to calcule the height of a given cell.
3. Depth.  The depth of a cell c in a linked list is the number of steps on the path that goes from the first cell of the list to c.  Write a function to calcule the depth of a given cell.

See how easy it is to check whether an integer x belongs to a linked list, i.e., whether x is equal to the contents of some cell of the list:

```// This function receives um integer x and a
// linked list lst of integers and returns
// the address of a cell that contains x.
// If such cell does not exist, returns NULL.

cell
*find (int x, cell *lst)
{
cell *p;
p = lst;
while (p != NULL && p->contents != x)
p = p->next;
return p;
}
```

Nice! No signal boolean variables!  Moreover, the function behaves correctly even if the list is empty.

Here is a recursive version of the same function:

```cell *rfind (int x, cell *lst)
{
if (lst == NULL)  return NULL;
if (lst->contents == x) return lst;
return rfind (x, lst->next);
}
```

## Exercises 3

1. The function below promises to behave like the function find above. Criticize the code.
```cell *find (int x, cell *lst) {
cell *p = lst;
int found = 0;
while (p != NULL && !found) {
if (p->contents == x) found = 1;
p = p->next; }
if (found) return p;
else return NULL;
}
```
2. Criticize the code of the following variant of the function find.
```cell *find (int x, cell *lst) {
cell *p = lst;
while (p != NULL && p->contents != x)
p = p->next;
if (p != NULL)  return p;
else  printf ("x is not in the list\n");
}
```
3. Increasing list.  Write a function to check whether a given linked list is increasing, i.e., whether the sequence that the list represents is in increasing order.
4. Write a function to search an increasing linked list. Write a recursive and an iterative versions.
5. Minimum.  Write a function to find a cell with smallest content in a linked list of integers. Write a recursive and an iterative versions.
6. Equality.  Write a function to check whether two linked lists are equal, i.e., whether they represent the same sequence. Write a recursive and an iterative versions.
7. Midpoint.  Write a function that will receive a linked list and return the address of a cell that is closest to the midpoint of the list. Do this without explicitly counting the number of cells in the list.

Sometimes it is convenient to ignore the contents of the first cell of a linked list and to treat it as a mere start marker. We say then that the list is headed and its first cell is the head of the list.

A headed linked list lst is empty if and only if lst->next == NULL.  To create an empty linked list with a head, all we need to say is

```   cell *lst;
lst = malloc (sizeof (cell));
lst->next = NULL;
```

To print the contents of a headed linked list lst, run the following function:

```void printlist (cell *lst) {
cell *p;
for (p = lst->next; p != NULL; p = p->next)
printf ("%d\n", p->contents);
}
```

## Exercises 4

1. Write versions of the functions find and rfind for headed linked lists.
2. Write a function to check whether a headed linked list is in increasing order. (Assume that the cells contain integer numbers.)

## Insertion into a linked list

Consider the problem of inserting a new cell into a linked list. Suppose that we wish to insert a new cell between the one pointed to by  p  and the next one.  (Of course this only makes sense if p is not NULL.)

```// This function inserts a new cell into a
// linked list. The new cell has contents x
// and will be inserted between cell p and
// the next one. (The function assumes that
// p != NULL.)

void
insert (int x, cell *p)
{
cell *new;
new = malloc (sizeof (cell));
new->contents = x;
new->next = p->next;
p->next = new;
}
```

Fast and simple!  No need to move cells in order to make room for the new cell, as we have to do with arrays. All we need to do is to change the values of a few pointers. Observe that the function does the right thing even when we wish to insert at the end of the list, i.e., when p->next == NULL.  If the list has a head, the function can be used to insert in the beginning of the list: just make p point to the head cell.  But, in the case of a list without head, the function is not capable of inserting before the first cell.

The time consumption of the function does not depend on where the insertion is done: the time is the same regardless of whether the insertion point is closer to the beginning or the end of the list.  This is quite different from what happens when inserting into an array.

## Exercises 5

1. Why the following version of function insert does not work?
```void insert (int x, cell *p) {
cell new;
new.contents = x;
new.next = p->next;
p->next = &new;
}
```
2. Write a function that will insert a new cell in a headless linked list. The function must be able, in particular, to insert the new cell at the beginning of the list. (You will have to take some design decisions before starting to write code.)
3. Copy.  Write a function to make a copy of a linked list. Write two versions: an iterative and a recursive.
4. Concatenate.  Write a function to concatenate two linked lists (i.e., link the second onto the end of the first). Write an iterative and a recursive versions.
5. Write a function to insert a new cell with contents x immediately after the k-th cell of a linked list. Write an iterative and a recursive versions.
6. Interchange.  Write a function to switch the positions of two cells of a linked list.
7. Reverse.  Write a function to reverse the order of the cells of a linked list (the first cell becomes the last, the second becomes the last-but-one, etc.). Do this without using auxiliary space, just changing pointers. Write an iterative and a recursive versions.
8. Allocate cells.  Is it a good idea to allocate the cells of a linked list one-by-one?  Propose alternatives. (But see the observation about the allocation of small blocks of bytes in chapter Dynamic memory allocation.)

## Deletion from a linked list

Consider the problem of deleting a cell from a linked list. How to specify the cell to be deleted? The most obvious idea is to point to the cell we wish to delete. But this not a good ideia. It is better to point to the cell that precedes the one we wish to delete.  (But it is not possible to delete the first cell using this convention.)

```// This function receives the address p of a
// cell of a linked list and deletes the
// cell p->next. The function assumes that
// p != NULL and p->next != NULL.

void
delete (cell *p)
{
cell *garbage;
garbage = p->next;
p->next = garbage->next;
free (garbage);
}
```

Great! No need to copy data from one place to another, as we had to do with arrays: all we have to do is to change the value of one pointer.  The function consumes the same time, whether the cell to be deleted is closer to the beginning or to the end of the list.

Observe that the deletion function does not need to know the address of the list, that is, does not need to know where the list begins.

## Exercises 6

1. Criticize the following version of the function delete:
```void delete (cell *p, cell *lst) {
cell *garbage;
garbage = p->next;
if (garbage->next == NULL)  p->next = NULL;
else  p->next = garbage->next;
free (garbage);
}
```
2. Suppose that we wish to delete the first cell of a nonempty linked list lst. Criticize the following code fragment:
```   cell **p;
p = &lst;
lst = lst->next;
free (*p);
```
3. Invent a way to delete a cell from a headless linked list. Your function must be able to delete the first cell of the list. (You will have to take some design decisions before starting to code.)
4. Deallocate.  Write a function to deallocate all the cells of a linked list (that is, to apply the free function to every cell).  We are assuming that each cell of the list was originally allocated by malloc.  Write an iterative and a recursive versions.
5. Josephus problem.  Use a linked list to solve the Josephus problem stated in the Arrays chapter.

## Exercises 7

1. From array to list.  Write a function to copy the contents of an array into a linked list preserving the order of the elements. Write an iterative and a recursive versions.
2. From list to array.  Write a function to copy the contents of a linked list into an array preserving the order of the elements. Write an iterative and a recursive versions.
3. Union.  Let's say that a si-list is a headless linked list that contains a sequence of strictly increasing integer numbers.  We might say that a si-list represents a set of integers.  Write a function to produce a si-list to represent the union of two given si-lists.  The union must be a si-list and must be built from the cells of the two given si-lists.
4. Linked lists without pointers.  Implement a linked list without pointers. Use two parallel arrays: an array contents[0..N-1] and an array next[0..N-1].  For each i in the set 0..N-1, the pair (contents[i], next[i]) represents a cell of the list.  The next cell is (contents[j], next[j]), where j = next[i].  Write search, insertion, and deletion functions for this representation.
5. Lists of strings.  This exercise deals with lists of strings: each cell of the list is (i.e., points to) an ASCII string. Write a function to check whether a given list of this kind is in lexicographic order.  Suppose the cells are of the following type:
```typedef struct cell {
char *str; struct cell *next;
} cell;
```
6. Counting words.  Let's say that a text is an array of bytes, the value of each beeing between 32 and 126. (Each one of these bytes represents an ASCII character.)  Let's say that a word is a maximal segment of text that contains no spaces (see the ASCII table). The adjective maximal means that the segment cannot be extended forward or backward. (In other words, the byte of the text that follows the segment is a space and the byte of the text that precedes the segment is a space.)  Write a function to receive a text and print a table of all the words in the text together with the number of occurrences of each word. Use a linked list to store the words.

## Search and delete

Given a linked list lst of integers and an integer y, we wish to delete from the list the first cell to contain y. If such cell does not exist, nothing needs to be done.  Let's assume that the list has a head cell. This assumption simplifies things because we need not change the address of the list even if the initial cell contains y.

```// This function receives a headed linked
// list lst and deletes from the list the
// first cell to contain y, if such cell
// exists.

void
searchanddelete (int y, cell *lst)
{
cell *p, *q;
p = lst;
q = lst->next;
while (q != NULL && q->contents != y) {
p = q;
q = q->next;
}
if (q != NULL) {
p->next = q->next;
free (q);
}
}
```

To prove that the code is correct, we need to check the following invariant: at the beginning of each iteration (immediately before the q != NULL test), one has

```q == p->next
```

that is,  q  is one step ahead of  p.

## Exercises 8

2. Write a function to delete from a linked list all the cells containing a given y.
3. Write a function to delete the k-th cell from a headless linked list. Write an iterative and a recursive versions.

## Search and insert

Suppose we are given a headed linked list.  We wish to insert into the list a new cell containing x immediately before the first cell that contains y.

```// This function receives a headed linked list
// lst and inserts into the list a new cell
// immediately before the first cell to
// contain y. If no cell contains y, insert
// the new cell at the end of the list.
// The contents of the new cell is x.

void
searchandinsert (int x, int y, cell *lst)
{
cell *p, *q, *new;
new = malloc (sizeof (cell));
new->contents = x;
p = lst;
q = lst->next;
while (q != NULL && q->contents != y) {
p = q;
q = q->next;
}
new->next = q;
p->next = new;
}
```