Lists

By Herbert J. Bernstein
© Copyright 2003 Herbert J. Bernstein

Introduction to Lists

What we mean by ordered is that we have some way to tell the relative positions of items in the list. That is why an array is a particularly tempting data structure upon which to base a list:

• Advantages of using an array to represent a list
  • Simplicity
  • Direct immediate access to each item on the list by its array index
• Disadvantages of using an array to represent a list
  • Fixed size
  • Insertion or deletion may required massive copying

List Operations

• Construct a set from an empty set or an ordered set of data
• Find the number of items on the list
• Find the first item on the list
• Find the last item on the list
• Find an item by the ordinal of its position on the list
• Find the next item on the list
• Find the previous item on the list
• Find one or more items by their content
• Insert an item or a list of items into an existing list
• Delete an item or a sublist of items from an existing list
• Merge two lists by their contents
• Find the intersection of two lists by their contents

Not all implementations of lists will allow all of these operations to be performed efficiently.

Choices in implementation of lists

• Static arrays
  • Directly allocated arrays
  • Dope vectors
• Dynamic arrays
  • Based on static arrays and a capacity variable
  • Capacity scaled up by a constant multiplier when needed
  • Trimmed when appropriate
  • Prone to memory fragmentation
• Linked lists
  • Based on objects with data field and link field pointing to next object
  • Inefficient for searching
  • Efficient for insertion, deletion and finding the next object
  • Inefficient for finding the previous object
  • Sometime created as rings
  • Causes many small memory allocations
• Doubly linked lists
  • Based on objects with data field, forward link pointing to next object and backwards link pointing to the previous object
  • Inefficient for searching, but better than linked list
  • Efficient for insertion, deletion, finding next and previous objects
  • Sometimes created as contra-rotating rings
  • Causes many small memory allocations
• Block allocated linked and doubly linked lists
  • Large pools for objects for future allocation set up as linked list of arrays
  • Much less of a burden on memory allocation
  • Freeing nodes is complex
• Hash tables
  • A hash code maps an object to an integer
  • The hash code for two equal object must be the same
  • It is desirable for the hash codes for two unequal objects to be distinct
  • A hash table is an auxillary array organized by hash code pointing into the list
  • If multiple objects have the same hash code:
    • Make a dynamic array of the multiple hits
    • Make a linked list of the multiple hits
    • Steal a subsequent empty space
  • Allows O(size of list of duplicates) searches
  • Speeds up ordinal-based operations
  • Speeds up context-based operations
  • Complicates insertions and deletions
  • See http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html