A List Implementation That Links Data - Data Structures and Abstractions with Java - page 357

14.26

Adding to a list at a given position. The add method, as given in Segment 14.11, for the class
LList can add an entry to the beginning of a list in O(1) time. Adding to a list at other positions
depends on the position. As the position number increases, the time needed for an addition
increases. In other words, since add calls getNodeAt , and getNodeAt is O( n ), add is O( n ) when the
addition is beyond the beginning of the list.
The add method, as given in Segment 14.23, for the class LList2 can add an entry to either the
beginning or the end of a list in O(1) time. It requires O( n ) time for other additions.

Question 17 What is the Big Oh of the method toArray , as given in Segment 14.14?
Question 18 What is the Big Oh of the method remove , as given in Segment 14.16?

Question 19 What is the Big Oh of the method replace , as given in Segment 14.17?
Question 20 What is the Big Oh of the method getEntry , as given in Segment 14.18?

Question 21 What is the Big Oh of the method contains , as given in Segment 14.19?
Question 22 In light of the tail reference, what changes can you make to the method
getNodeAt , as given in Segment 14.7, to improve the time complexity of the methods
replace , getEntry , and contains ?

14.27

Using Big Oh notation, Figure 14-11 summarizes the time complexities of the operations of the ADT
list for the implementations that use an array and a chain of linked nodes. For some operations, two or
three complexities are given: The first one indicates the time requirement for an operation at the
beginning of the list, the second is for operations at other positions within the list, and the third one, if
it exists, is for operations at the end of the list.

FIGURE 14-11

The time efficiencies of the ADT list operations for three imple-
mentations, expressed in Big Oh notation

Operation

AList LList LList2

add(newEntry)
add(newPosition, newEntry)
toArray()
remove(givenPosition)
replace(givenPosition, newEntry)
getEntry(givenPosition)
contains(anEntry)
clear(), getLength(), isEmpty()

O(1)
O( n ); O(1)
O( n )
O( n ); O(1)
O(1)
O(1)
O( n )
O(1)

O( n )
O(1); O( n )
O( n )
O(1); O( n )
O(1); O( n )
O(1); O( n )
O( n )
O(1)

O(1)
O(1); O( n ); O(1)
O( n )
O(1); O( n )
O(1); O( n ); O(1)
O(1); O( n ); O(1)
O( n )
O(1)

For example, the first add method in an array-based implementation is O(1), and the second
add method is O( n ), unless it adds at the end of the list, in which case it is O(1). The method
toArray is always O( n ), and getEntry is always O(1).
For the linked implementation LList , which maintains only a head reference to the chain of
nodes, the first add method and toArray are each O( n ). The second add method is O( n ) unless it
adds to the beginning of the list, in which case it is O(1).