|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
Figure 
illustrates the
the singly-linked list scheme we have chosen to implement.
Two related structures are used.
The elements of the list are represented using instances
of the Element class which comprises three fields,
list, datum and next.
The main structure is an instance
of the LinkedList class which also comprises two fields,
head and tail,
which refer to the first and last list elements, respectively.
The list field of every Element
contains a reference to the LinkedList instance
with which it is associated.
The datum field is used to refer to the objects in the list and
the next field refers to the next list element.
Figure: Memory representation of a linked list.
Program defines the LinkedList.Element class.
It is used to represent the elements of a linked list.
It has three fields, list, datum and next,
a constructor and two properties, Datum and Next.
Program also defines the fields of the LinkedList class,
head and tail.
Program: LinkedList fields and LinkedList.Element class.
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:
In C# all object references occupy a constant amount of space. Therefore, S(n)=O(n).
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.