Chapter 5. Linked Lists
Linked lists are some of the most fundamental data structures. Linked lists consist of a number of elements grouped, or linked, together in a specific order. They are useful in maintaining collections of data, similar to the way that arrays are often used. However, linked lists offer important advantages over arrays in many cases. Specifically, linked lists are considerably more efficient in performing insertions and deletions. Linked lists also make use of dynamically allocated storage, which is storage allocated at runtime. Since in many applications the size of the data is not known at compile time, this can be a nice attribute as well.
This chapter covers:
- Singly-linked lists
The simplest linked lists, in which elements are linked by a single pointer. This structure allows the list to be traversed from its first element to its last.
- Doubly-linked lists
Linked lists in which elements are linked by two pointers instead of one. This structure allows the list to be traversed both forward and backward.
- Circular lists
Linked lists in which the last element is linked to the first instead of being set to NULL. This structure allows the list to be traversed in a circular fashion.
Some applications of linked lists are:
- Mailing lists
Lists such as the ones found in email applications. Since it is difficult to predict how long a mailing list may be, a mailer might build a linked list of addresses before sending a message.
- Scrolled lists
Components found in graphical user interfaces. Often data associated with items in scrolled lists is not displayed. One approach to managing this “hidden” data is to maintain a linked list wherein each element stores the data for one item in the scrolled list.
- Polynomials
An important part of mathematics not inherently supported as a datatype by most languages. If we let each element of a linked list store one term, linked lists are useful in representing polynomials (such as 3x 2 + 2x + 1).
- Memory management (illustrated in this chapter)
An important role of operating systems. An operating system must decide how to allocate and reclaim storage for processes running on the system. A linked list can be used to keep track of portions of memory that are available for allocation.
- LISP
An important programming language in artificial intelligence. LISP, an acronym for LISt Processor, makes extensive use of linked lists in performing symbolic processing.
- 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.