An Implementation

Figure  illustrates the the singly-linked list scheme we have chosen to implement. Two structures are used. The elements of the list are represented using a structure which comprises two fields--datum and next. The former holds the a single data item; the latter is a pointer to the next array element. The main structure also comprises two fields-head and tail. Which contain pointers to the first and last list elements, respectively.

  
Figure: Memory Representation of Linked List Objects

Program  gives the declaration of the LinkedList<T> and ListElement<T> class templates. The ListElement<T> class is used to represent the elements of a linked list. It has two private member variables, datum and next, a private constructor, and two public accessor functions.

  
Program: LinkedList<T> and ListElement<T> Class Definitions

A LinkedList<T> class object has two protected member variables, head and tail, several constructors, a destructor, and various other member functions.

We can calculate the total storage required, S(n), to hold a linked list of n items from the class definitions given in Program  as follows:

Since LinkedList<T> and ListElement<T> are generic classes, we have no a priori knowledge of the amount of storage used by an object of type T. However, it is often reasonable to assume that . And since a pointer requires a constant amount of space, . If we assume that the amount of storage used by an object of type T is O(1), then S(n)=O(n).

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.