A linked list is a set of items organized sequentially, where each member of the list is a node and the connection between any two nodes is a link. A linked implementation of a list is flexible because it uses almost no storage until nodes are added to the list. It expands and shrinks dynamically according to the number of nodes, and generally makes efficient use of memory.
Some common operations on lists are as follows: Append adds a node to the end of a list; Insert inserts a node in the middle of a list; Empty indicates if a list is empty; Find searches for a node; Get retrieves a node; Clear removes all nodes; Prepend inserts a node at the beginning of a list; Remove removes a node; and Replace replaces the contents of a node.
In this chapter, we showed how to create two types of lists: template-based lists (called non-intrusive) and object-based lists (called intrusive).
In a singly linked list, each node contains a link pointer that points to the next node in the list. A doubly linked list consists of nodes having both forward and backward links. To traverse a list means to begin at one end of a list and follow the links between nodes to move to the other end.
A template-based list uses a type parameter to determine what types of objects will be stored in the list. In this chapter, we created the Tlist<T> class template, where T can be int, float, Student, Package, or any other class type. This type of list requires no knowledge of the internal list structure by the class user. We wrote a simple test program that created several lists: a list of test scores, a list of names and a list of patients.
In this chapter we continued our study of graphs that was begun in Chapter 7, with a program that creates an adjacency matrix. We implemented the matrix using an array of linked lists, and showed how to search for a specific path between any two given nodes. We introduced the depth-first search algorithm for searching a graph, and created a Graph class that implemented the search.
We created an object-based list class called DblList that implemented a doubly linked list. We also created the DblNode class, the base class for all objects inserted in a DblList. We showed that this type of intrusive list is efficient, but its use requires some modifications to existing classes. We wrote a test program that demonstrated the DblList class.
We explained how to create and use an iterator class for list processing called DblIterator. We demonstrated the iterator in a short program that processed a list of books. Iterator objects have an advantage in programs that do complex manipulation of list pointers, because the same list can have multiple iterators and the iterators can be completely independent.