|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
To prepend an element to a linked list
is to insert that element in front of the first element of the list.
The prepended list element becomes the new head of the list.
Program 
gives the algorithm for the
prepend method of the LinkedList class.
Program: LinkedList class prepend method.
The prepend method first creates a new LinkedList.Element. Its _datum instance attribute is initialized with the value to be prepended to the list, item; and the _next instance attribute refers to the first element of the existing list by initializing it with the current value of _head. If the list is initially empty, both _head and _tail refer to the new element. Otherwise, just _head needs to be updated.
Note, the LinkedList.Element instance is initialized
by calling its __init__ method.
In Section the running time of the __init__ method
was determined to be O(1).
And since the body of the prepend method adds
only a constant amount of work,
the running time of the prepend method is also O(1).
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.