Lists

External interface

• Create (list L)
• Insert (listtype item, position p, list L)
• Delete (position p, list L)
• position Lookup (listtype item, list L)
• listtype Retrieve (position p, list L)
• position First (list L)
• position Next (position p, list L)
• position Prev (position p, list L)

Implementations

• Store the list elements in an array, and represent positions using integer indices.
  • Prev is O(1)
  • Insert and Delete are O(N)
  • Arrays are usually fixed in size
• Use a linked list of records containing an item of type listtype, and a pointer to the next record in the list. Represent positions as pointers to the appropriate record.
  • Insert and Delete are O(N) unless position p is pointer to record containing position p-1
  • Prev is O(N)
  • Requires space for pointers
• Use a doubly-linked list of records, with pointers to the previous and next records in the list. Represent positions as above.
  • Prev, Insert, and Delete are O(1)
  • Requires twice as much space for pointers as previous implementation