![[linked-list.jpg]](img/linked-list.jpg "Copied from www.monzy.com/")
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.
Table of contents:
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;
};
![[cell de linked list]](png-from-tex/celula-de-lista-next.png)
We shall treat the cells as a new data type and will assign the name cell to this new type:
typedef struct record cell;
(The name of the struct and the name of the new data type need not be different. We could have written typedef struct record record;.)
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 .
![[lista encadeada]](png-from-tex/lista.png)
(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.)
typedef struct record {
int contents;
struct record *next;
} cell;
typedef struct record cell;
struct record {
int contents;
cell *next;
};
typedef struct cell cell;
struct cell {
int contents;
cell *next;
};
int main (void) {
printf ("sizeof (cell) = %d\n",
sizeof (cell));
return EXIT_SUCCESS;
}
The address of a linked list is the address of its first cell. If lst is the address of a linked list, we may simply say that
lst is a linked list.
(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 style.
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);
}
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);
}
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;
}
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");
}
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);
}
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 if the list is not headed, 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 point of insertion is closer to the beginning or the end of the list. This is quite different from what happens when inserting into an array.
void insert (int x, cell *p) {
cell new;
new.contents = x;
new.next = p->next;
p->next = &new;
}
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 need to do is change the value of one pointer. The function consumes the same time, whether the cell to be deleted is closer to the beginning or closer to the end of the list.
Notice 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.
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);
}
cell **p; p = &lst; lst = lst->next; free (*p);
typedef struct cell {
char *str; struct cell *next;
} cell;
Given a linked list 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 the code correct,
we need to check the following invariant:
at the beginning of each iteration
(immediately before the q != NULL
test),
we have
q == p->next
that is, q is one step ahead of p.
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;
}
Now that we understand the basic linked lists, we can invent many others kinds of linked lists. For example, we can build a circular linked list, one in which the last cell links to the first. The address of such a list is the address of any of its cells. We can also build a doubly liked list: each cell contains the address of the previous cell as well as the address of the next cell.
The following questions are appropriate for any kind of linked list. Under what conditions is a list empty? Is it convenient to have a head cell and/or a tail cell? How to delete a cell pointed to by p? Likewise, for the cell next to the one pointed to by p? Likewise, for the cell preceding the one pointed to by p? How to insert a new cell between the cell p and the previous one? Likewise, between p and the next one?