Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

insertAfter and insertBefore Methods

Consider the methods insertAfter and insertBefore of the LinkedList.Element class shown in Program gif. Both methods take a single argument that specifies an item to be inserted into the list. The given item is inserted either in front of or immediately following this list element.

   program3883
Program: LinkedList.Element class insertAfter and insertBefore methods.

The insertAfter method is almost identical to append. Whereas append inserts an item after the tail, insertAfter inserts an item after an arbitrary list element. Nevertheless, the running time of insertAfter is identical to that of append, i.e., it is O(1).

To insert a new item before a given list element, it is necessary to traverse the linked list starting from the head to locate the list element that precedes the given list element. In the worst case, the given element is the at the tail of the list and the entire list needs to be traversed. Therefore, the running time of the insertBefore method is O(n).


next up previous contents index

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