The List ADT

• We will deal with a general list of the form A0, A1, A2, …, AN−1. We say that the size of this list is N. We will call the special list of size 0 an empty list.
• Some popular operations are printList and makeEmpty, which do the obvious things; find, which returns the position of the first occurrence of an item; insert and remove, which generally insert and remove some element from some position in the list; and findKth, which returns the element in some position (specified as an argument). If the list is 34, 12, 52, 16, 12, then find(52) might return 2; insert(x,2) might make the list into 34, 12, x, 52, 16, 12 (if we insert into the position given); and remove(52) might turn that list into 34, 12, x, 16, 12.
• Although arrays are created with a fixed capacity, we can create a different array with double the capacity when needed. This solves the most serious problem with using an array, namely that historically, to use an array, an estimate of the maximum size of the list was required.
• Array implementation


  • Allows printList to be carried out in linear time
  • findKth operation takes constant time
• Insertion and deletion

  • Potentially expensive, depending on where the insertions and deletions occur
  • In the worst case, inserting into position 0 requires pushing the entire array down one spot to make room
  • Deleting the first element requires shifting all the elements in the list up one spot
  • Worst case for these operations is O(N)
  • On average, half of the list needs to be moved for either operation, so linear time is still required
  • If all the operations occur at the high end of the list, then no elements need to be shifted, and then adding and deleting take O(1) time
• There are many situations where the list is built up by insertions at the high end, and then only array accesses (i.e., findKth operations) occur
• If insertions and deletions occur throughout the list, and in particular, at the front of the list, then the array is not a good option
• Linked list


  In order to avoid the linear cost of insertion and deletion, we need to ensure that the list is not stored contiguously, since otherwise entire parts of the list will need to be moved.
• The linked list consists of a series of nodes, which are not necessarily adjacent in memory. Each node contains the element and a link to a node containing its successor. We call this the next link. The last cell’s next link references null.
• To execute printList or find(x) for a linked list

  1. Start at the first node

  2. Traverse the list by following the next links
• Executing printList or find(x) for a linked list

  • Linear-time operation
  • Constant likely larger than array implementation
• To execute findKth(i) for a linked list

  Traverse down the list in the obvious manner
• findKth(i) for a linked list

  Takes O(i) time
• The bound for findKth(i) is pessimistic, because frequently the calls to findKth are in sorted order (by i)
• For a linked list, The remove method can be executed in one next reference change.

  The insert method requires obtaining a new node from the system by using a new call and then executing two reference maneuvers.
• As we can see, in principle, if we know where a change is to be made, inserting or removing an item from a linked list does not require moving lots of items and instead involves only a constant number of changes to node links.
• The special case of adding to the front or removing the first item is thus a constant-time operation, presuming of course that a link to the front of the linked list is maintained. The special case of adding at the end can be constant-time, as long as we maintain a link to the last node. Thus, a typical linked list keeps links to both ends of the list.
• In a linked listm removing the last item is trickier, because we have to find the next-to-last item, change its next link to null, and then update the link that maintains the last node. In the classic linked list, where each node stores a link to its next node, having a link to the last node provides no information about the next-to-last node.
• we have every node maintain a link to its previous node in the list. This is known as a doubly linked list