Mastering Algorithms With C - Kyle Loudon [28]
Linked allocation of files
A type of file allocation that eliminates external fragmentation on a disk but is good only for sequential access. Each block of a file contains a pointer to the file's next block.
Other data structures
Some data structures whose implementations depend on linked lists are stacks, queues, sets, hash tables, and graphs, all of which are presented in this book.
Description of Linked Lists
Singly-linked lists, usually simply called linked lists, are composed of individual elements, each linked by a single pointer. Each element consists of two parts: a data member and a pointer, called the next pointer. Using this two-member structure, a linked list is formed by setting the next pointer of each element to point to the element that follows it (see Figure 5.1). The next pointer of the last element is set to NULL, a convenient sentinel marking the end of the list. The element at the start of the list is its head; the element at the end of the list is its tail.
To access an element in a linked list, we start at the head of the list and use the next pointers of successive elements to move from element to element until the desired element is reached. With singly-linked lists, the list can be traversed in only one direction—from head to tail—because each element contains no link to its predecessor. Therefore, if we start at the head and move to some element, and then wish to access an element preceding it, we must start over at the head (although sometimes we can anticipate the need to know an element and save a pointer to it). Often this weakness is not a concern. When it is, we use a doubly-linked list or circular list.
Conceptually, one thinks of a linked list as a series of contiguous elements. However, because these elements are allocated dynamically (using malloc in C), it is important to remember that, in actuality, they are usually scattered about in memory (see Figure 5.2). The pointers from element to element therefore are the only means by which we can ensure that all elements remain accessible. With this in mind, we will see later that special care is required when it comes to maintaining the links. If we mistakenly drop one link, it becomes impossible to access any of the elements from that point on in the list. Thus, the expression "You are only as strong as your weakest link" is particularly fitting for linked lists.
Figure 5.1. Elements linked together to form a linked list
Figure 5.2. Elements of a linked list linked but scattered about an address space
Interface for Linked Lists
Name
list_init
Synopsis
void list_init(List *list, void (*destroy)(void *data));
Return Value
None.
Description
Initializes the linked list specified by list. This operation must be called for a linked list before the list can be used with any other operation. The destroy argument provides a way to free dynamically allocated data when list_destroy is called. For example, if the list contains data dynamically allocated using malloc, destroy should be set to free to free the data as the linked list is destroyed. For structured data containing several dynamically allocated members, destroy should be set to a user-defined function that calls free for each dynamically allocated member as well as for the structure itself. For a linked list containing data that should not be freed, destroy should be set to NULL.
Complexity
O (1)
Name
list_destroy
Synopsis
void list_destroy(List *list);
Return Value
None.
Description
Destroys the linked list specified by list. No other operations are permitted after calling list_destroy unless list_init is called again. The list_destroy operation removes all elements from a linked list and calls the function passed as destroy to list_init once for each element as it is removed, provided destroy was not set to NULL.
Complexity
O (n), where n is the number of elements in the linked list.
Name
list_ins_next
Synopsis
int list_ins_next(List *list, ListElmt *element, const