Lecture
In a single-linked list, each information item contains a link to the next list item. Each data element is usually a structure that consists of information fields and a link pointer. The conceptually single-linked list looks like the one shown in fig. 22.2.
There are two main ways to construct a single-linked list. The first way is to place new items at the end of the list [1] . The second is to insert elements into certain positions in the list, for example, in ascending order. The algorithm for the function of adding an element depends on the method of building the list. Let's start with a simpler way to create a list by putting items at the end.
As a rule, the elements of a linked list are structures, because, in addition to data, they contain a link to the next element. Therefore, it is necessary to define the structure that will be used in the following examples. Since mailing lists are usually stored in linked lists, a structure that describes a postal address is a good choice. Its description is shown below:
struct address {
char name [40];
char street [40];
char city [20];
char state [3];
char zip [11];
struct address * next; / * link to the next address * /
} info;
The slstore () function shown below creates a single- linked list by placing each item at the end of the list. As parameters, it is passed a pointer to an address type structure containing the new entry, and a pointer to the last element of the list. If the list is empty, the pointer to the last element must be zero.
void slstore (struct address * i,
struct address ** last)
{
if (! * last) * last = i; / * first item in the list * /
else (* last) -> next = i;
i-> next = NULL;
* last = i;
}
Although the list created using the slstore () function can be sorted by a separate operation after it has been created, it is easier to immediately create an ordered list by inserting each new item at the right place in the sequence. In addition, if the list is already sorted, it makes sense to maintain its orderliness by inserting new items into the appropriate positions. To insert an element in this way, you need to sequentially browse the list until the location of the new element is found, then insert a new entry into the found position and reinstall the links.
When inserting an element into a single-linked list, one of three situations can arise: the element becomes the first, the element is inserted between the other two, the element becomes the last. In fig. 22.3 the scheme of change of links in each case is shown.
Insert at the top of the list
+ ---- + n + ---- +
| new | p | new |
+ ---- + e + ---- +
| | in .------------ | |
+ ---- + p | + ---- +
a |
+ ---- + + ---- + + ---- + u in | + ---- + + ---- + + ---- +
| info | | info | | info | a | | info | | info | | info |
\ / \ / \ -> + ---- + + ---- + + ---- + e | + ---- + + ---- + + ---- +
| | ---> | | ---> | 0 | t '-> | | ---> | | ---> | 0 |
+ ---- + + ---- + + ---- + c + ---- + + ---- + + ---- +
I
Insert in the middle of the list
+ ---- + n + ---- +
| new | p | new |
+ ---- + e + ---- +
| | in .----------> | |
+ ---- + p | .-- + ---- +
a | |
+ ---- + + ---- + + ---- + u in | + ---- + | + ---- + + ---- +
| info | | info | | info | a | | info | | | info | .-> | info |
\ / \ / \ -> + ---- + + ---- + + ---- + e \ / \ / \ -> + ---- + | + ---- + | + ---- +
| | ---> | | ---> | 0 | t '- | | '-> | | - '| 0 |
+ ---- + + ---- + + ---- + c + ---- + + ---- + + ---- +
I
Insert at the end of the list
+ ---- + n + ---- +
| new | p | new | <----------.
+ ---- + e + ---- + |
| | in | 0 | |
+ ---- + p + ---- + |
a |
+ ---- + + ---- + + ---- + ni + ---- + + ---- + + ---- + |
| info | | info | | info | and | info | .-> | info | | info | |
\ / \ / \ -> + ---- + + ---- + + ---- + e \ / \ / \ -> + ---- + | + ---- + + ---- + |
| | ---> | | ---> | 0 | t | | - '| | ---> | | - '
+ ---- + + ---- + + ---- + c + ---- + + ---- + + ---- +
I
|
It should be remembered that when inserting an element at the beginning (first position) of the list, it is also necessary to change the address of entry into the list somewhere else in the program. To avoid these difficulties, you can store a service watchdog element as the first element of the list [2] . In the case of an ordered list, it is necessary to select some special value that will always be first in the list in order for the initial element to remain unchanged. The disadvantage of this method is a rather large memory consumption for storing the watchdog, but usually this is not so important.
The next function, sls_store () , inserts structures of type address into the mailing list, ordering it in ascending order of values in the name field. The function accepts pointers to pointers to the first and last elements of the list, as well as a pointer to the inserted element. Since the first or last elements of the list may change, the sls_store () function automatically updates pointers to the beginning and end of the list, if necessary. The first time the function is called, the first and last pointers must be zero.
/ * Insert in an ordered single-linked list. * /
void sls_store (struct address * i, / * new element * /
struct address ** start, / * start of list * /
struct address ** last) / * end of list * /
{
struct address * old, * p;
p = * start;
if (! * last) {/ * first item in the list * /
i-> next = NULL;
* last = i;
* start = i;
return;
}
old = NULL;
while (p) {
if (strcmp (p-> name, i-> name) <0) {
old = p;
p = p-> next;
}
else {
if (old) {/ * insertion in the middle * /
old-> next = i;
i-> next = p;
return;
}
i-> next = p; / * insert at the beginning * /
* start = i;
return;
}
}
(* last) -> next = i; / * insert at the end * /
i-> next = NULL;
* last = i;
}
Sequential iteration of the elements of a linked list is very simple: start from the beginning and follow the signs. Usually, the search code fragment is so small that it is inserted into another procedure — for example, a search, delete, or display function. So, the following function displays all the names on the mailing list:
void display (struct address * start)
{
while (start) {
printf ("% s \ n", start-> name);
start = start-> next;
}
}
When the display () function is called, the start parameter must be a pointer to the first structure in the list. After that, the function proceeds to the next element pointed to by the pointer in the next field. The process terminates when the next is zero.
To get an item from the list, you just need to go through the chain of links. The following is an example of a search function by the contents of the name field:
struct address * search (struct address * start, char * n)
{
while (start) {
if (! strcmp (n, start-> name)) return start;
start = start-> next;
}
return NULL; / * no matching item found * /
}
Since the search () function returns a pointer to a list item containing the name being searched for, the return type is described as a pointer to the address structure. If there are no matching items in the list, a null ( NULL ) is returned.
Removing an item from a single-linked list is easy. As in the case of insertion, three cases are possible: deleting the first element, deleting an element in the middle, deleting the last element. In fig. 22.4 all three operations are shown.
Fig. 22.4. Removing an item from a single-linked list Delete the first list item
+ ------ + + ------ + + ------ +
| data | | data | | data |
\ / \ / \ -> + ------ + + ------ + + ------ +
| | ---> | | ---> | 0 |
+ ------ + + ------ + + ------ +
turns into
+ ------ + + ------ + + ------ +
| deleted | \ / \ / \ -> | data | .-> | data |
+ ------ + + ------ + | + ------ +
| 0 | | | - '| 0 |
+ ------ + + ------ + + ------ +
Remove middle list item
+ ------ + + ------ + + ------ +
| data | | data | | data |
\ / \ / \ -> + ------ + + ------ + + ------ +
| | ---> | | ---> | 0 |
+ ------ + + ------ + + ------ +
turns into
+ ------ + + ------ + + ------ +
| data | | deleted | | data |
\ / \ / \ -> + ------ + + ------ + + ------ +
| | | 0 | .-> | 0 |
+ ------ + + ------ + | + ------ +
\ ______________ |
Delete the last item in the list
+ ------ + + ------ + + ------ +
| data | | data | | data |
\ / \ / \ -> + ------ + + ------ + + ------ +
| | ---> | | ---> | 0 |
+ ------ + + ------ + + ------ +
turns into
+ ------ + + ------ + + ------ +
| data | | data | | deleted |
\ / \ / \ -> + ------ + + ------ + + ------ +
| | ---> | 0 | | 0 |
+ ------ + + ------ + + ------ +
|
Below is a function that removes the specified item from the list of address structures.
void sldelete (
struct address * p, / * previous element * /
struct address * i, / * element to delete * /
struct address ** start, / * start of list * /
struct address ** last) / * end of list * /
{
if (p) p-> next = i-> next;
else * start = i-> next;
if (i == * last && p) * last = p;
}
The sldelete () functions must pass pointers to the element to be deleted, to the element to be deleted, and also to the first and last elements. When deleting the first element, the pointer to the previous element must be zero ( NULL ). This function automatically updates the start and last pointers if one of them refers to the item to be deleted.
Single-linked lists have one big disadvantage: a single-linked list cannot be read in the opposite direction. For this reason, doubly linked lists are commonly used.
[1] Do not forget that a single-linked list, like a rope, has two ends: the beginning and the end.
[2] Often referred to as a signal mark .
Comments
To leave a comment
Structures and data processing algorithms.
Terms: Structures and data processing algorithms.