Linux Unleashed, Third Edition:Programming in C++

-->

Linked Lists

The GNU C++ library supports two kinds of linked lists: single linked lists implemented by the SLList class, and doubly linked lists implemented by the DLList class. Both of these types of lists support all the standard linked list operations. A summary of the operations that these classes support is shown in Table 27.5.

**Table 27.5.** List operators.

Operator	Description

`list.empty()`	Returns `TRUE` if `list` is empty
`list.length()`	Returns the number of elements in `list`
`list.prepend(a)`	Places `a` at the front of `list`
`list.append(a)`	Places `a` at the end of `list`
`list.join(list2)`	Appends `list2` to `list`, destroying `list2` in the process
`a = list.front()`	Returns a pointer to the element that is stored at the head of the list
`a = list.rear()`	Returns a pointer to the element that is stored at the end of the list
`a = list.remove_front()`	Deletes and returns the element that is stored at the front of the list
`list.del_front()`	Deletes the first element without returning it
`list.clear()`	Deletes all items from `list`
`list.ins_after(i, a)`	Inserts `a` after position `i` in the list
`list.del_after(i)`	Deletes the element following position `i` in the list

Doubly linked lists also support the operations listed in Table 27.6.

**Table 27.6.** Doubly linked list operators.

Operator	Description

`a = list.remove_rear()`	Deletes and returns the element stored at the end of the list
`list.del_real()`	Deletes the last element, without returning it
`list.ins_before(i, a)`	Inserts `a` before position `i` in the list
`list.del(i, dir)`	Deletes the element at the current position and then moves forward one position if `dir` is positive and backward one position if `dir` is 0 or negative

Plex Classes

Plex classes are classes that behave like arrays but are much more powerful. Plex classes have the following properties:

• They have arbitrary upper and lower index bounds.

• They can dynamically expand in both the lower and upper bound directions.

• Elements may be accessed by indices. Unlike typical arrays, bounds checking is performed at runtime.

• Only elements that have been specifically initialized or added can be accessed.

Four different types of Plexes are defined: the FPlex, the XPlex, the RPlex, and the MPlex. The FPlex is a Plex that can grow or shrink only within declared bounds. An XPlex can dynamically grow in any direction without any restrictions. An RPlex is almost identical to an XPlex, but it has better indexing capabilities. Finally, the MPlex is the same as an RPlex except that it allows elements to be logically deleted and restored.

Table 27.7 lists some of the operations that are valid on all four of the Plexes.

**Table 27.7.** Operations defined for `Plex`es.

Operation	Description

`Plex b(a)`	Assigns a copy of `Plex a` to `Plex b`
`b = a`	Copies `Plex a` into `b`
`a.length()`	Returns the number of elements in `a`
`a.empty()`	Returns `TRUE` if `a` has no elements
`a.full()`	Returns `TRUE` if `a` is full
`a.clear()`	Removes all the elements from `a`
`a.append(b)`	Appends `Plex b` to the high part of `a`
`a.prepend(b)`	Prepends `Plex b` to the low part of `a`
`a.fill(z)`	Sets all elements of `a` equal to `z`
`a.valid(i)`	Returns `TRUE` if `i` is a valid index into `a`
`a.low_element()`	Returns a pointer to the element in the lowest position in `a`
`a.high_element()`	Returns a pointer to the element in the highest position in `a`

Plexes are a very useful class on which many of the other classes in the GNU C++ class library are based. Some of the Stack, Queue, and Linked list types are built on top of the Plex class.

Table of Contents