Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Append

 

The Append function, the definition of which is given in Program gif, adds a new ListElement<T> at the tail-end of the list. The appended element becomes the new tail of the list.

   program3659
Program: LinkedList<T> Class Append Function Definition

The Append function first allocates a new ListElement<T>. Its datum field is initialized with the value to be appended, and the next field is set to zero. If the list is initially empty, both head and tail are made to point at the new element. Otherwise, the new element is appended to the existing list, and the just tail pointer is updated.

The running time analysis of the Append function is essentially the same as for Prepend. I.e, the running time is tex2html_wrap_inline61025. And if T is one of the built-in types, the running time simplifies to O(1).


next up previous contents index

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