Unlike arrays, lists do not necessarily guarantee constant time access to each element. Some list implementations guarantee constant time insertion at the front of the list. Some list implementations guarantee constant time insertion at the end of the list. Before we implement lists, we need to consider a number of other issues related to the design of lists. There are a number of ways in which we can implement lists, and these implementations govern the cost of the various operations.
Most programmers expect that insertion and testing for emptiness are constant time operations.
There are a number of hidden issues to consider when designing implementations. We might speak about sharing of sublists. Filled in the details, many of which are based on outline 30 of CSC152 99F . Back to Introduction to Data Structures . On to Implementing Lists .