|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
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 instance attributes,
_list, _datum and _next.
The main structure is an instance
of the LinkedList class which also comprises two instance attributes,
_head and _tail,
which refer to the first and last list elements, respectively.
The _list instance attribute of every Element
contains a reference to the LinkedList instance
with which it is associated.
The _datum instance attribute is used to refer to the objects in the list and
the _next instance attribute 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 instance attributes, _list, _datum and _next,
an __init__ method and two properties, datum and next.
Program: 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 Python object identifiers (addresses) occupy a constant amount of space. Therefore, S(n)=O(n).
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.