## Introduction to Lists

A list is an ordered set of objects. Unlike an array the objects in a list need not be of the same type. However, by use of arrays of references or pointers, we can always use an array to implement a list.

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
• 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
• 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
• 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

Last Updated on 2 May 2004
By Herbert J. Bernstein
Email: yaya@bernstein-plus-sons.com