Data Structures & Algorithms Lecture Notes

11 November 2008 • Linked Lists

Outline

• Motivation

• List properties.

• The list ADT.

• ADT implementations.

• Extension and details.

Arrays

• Arrays have several properties:

  • They support the before and after relation (they are sequential).

  • They have indexed access to elements.

  • Element access is efficient (O(1) time).

• These properties accrue from the tight mapping between the array data structure and the layout of primary store.

Consequences

• The tight mapping between arrays and storage has a consequence:

  Arrays are static in the number of elements they can hold.

• Static arrays make it impossible or more expensive to change array size by inserting or deleting elements.

The Trade-Off

• The trade-off is between efficient storage and access and the number of elements held.

  • Arrays trade-off dynamic element counts for fast and efficient storage and access.

• How does the trade-off work in the other direction?

  • How much do we have to give up to get dynamic data-structure size?

Properties

• The desirable data-structure properties are:

  • Unrestricted ability to hold varying numbers of elements.

  • The ability to add and remove elements.

  • The ability to reference elements (index or access).

  • Be sequential (support before and after).

• There are unfortunate interactions between these properties.

Dynamics vs. Referencing

• Useful referencing requires stability.

  • An element reference should not change "by magic".

• Unless careful, dynamics conflicts with stability.

  

  • This is similar to dangling pointers.

The ADT

• The maintenance operations are create and delete.

• The manipulation operations are add and remove.

  • But add and remove where?

  • Indicated by an element-reference parameter.

• The ADT should include a type for element references.

Adding and Removing Elements

• The element to be removed is given in the call.

• Should the element added go before or after the element referenced?

  

• How do you insert with no elements?

Query Operations

• The usual operations: size, empty, member, ...

• Access the referenced element (pointer follow, element_at).

• Traverse the elements in (possibly reverse) order.

  • Looping constructs and similar aggregative operations.

• Reference navigation: before and after.

  • For manual traversals.

Traversal Operations

• There are three kinds of traversal operations:

  1. for-loop style operations.

     for (r=l.start(); l.more; r=l.next())
     

  2. Java- or C#-style iterators.

     foreach (e in l)
     

  3. Lisp- or functional-style maps.

     void f(e: element) { ... }
     map(f, l)
     

Traversals vs. Dynamics

• There is a nasty interaction between traversal operators and dynamic elements.

• Remove all elements from l that satisfy p.

  for (r=l.start(); l.more; r=l.next())
    if (p(l.element_at(r))
      l.remove(r)
  

• The data structure is being changed while its being traversed.

List ADT Implementations

• What implementations will do for the list ADT?

• Two come immediately to mind:

  1. An array-based implementation.

  2. A dynamic-storage-based implementation.

• There are others.

Array-Based Implementation

• Aren't we trying to do better than arrays?

• Yes, but

  • The arrays are hidden inside the ADT.

  • The ADT inherits array efficiencies (and inefficiencies).

• The array implementation can be static or dynamic.

  • Assume static to start.

Array Representation

• An n-element array represents an (at most) n-element list.

• One array end (0 or n - 1) always represents the first list element.

  • A variable keeps track of the index of the last list element.

  

List Element References

• Element references correspond to array indices.

  • This suffers from phantom reference problems.

• Store a pseudo-index value with each element.

  • Phantom references disappear or are detectable.

  • Element retrieval is now costs O(n) time.

    • Pointers as element references help here.

List Adding and Removing

• Adding an element (before or after) involves sliding O(n) elements one to the right.

  • What to do if there's no more space?

• Deleting an element involves sliding O(n) elements one to the left.

• Potentially makes all references phantom

  • Like iterator invalidation in the STL.

List Traversal

• Use for-loop style traversal operations.

  • Can also serve as the navigating operations.

• A reference variable called the cursor keeps track of the current element.

  • start() sets the cursor to the first element.

  • next() advances the cursor one element.

    • Both start() and next() return the cursor.

• Changing the list while traversing it causes undefined behavior.

Array-List Comparison

	Array	List
		(Array)
create	O(1)	O(1)
delete	O(1)	O(1)
add	O(n)	O(n)
remove	O(n)	O(n)
traversal	O(1)	O(1)
navigation	O(1)	O(n)
dynamic	No	No

Dynamic Lists

• The tight coupling between storage and arrays makes arrays static.

• Loosening the coupling permits dynamic lists.

  • But breaks the before-after relation.

  • Dynamics lists will have to maintain that too.

• The resulting list is known as a linked list.

Basic Idea

• Each list element carries its before-after information.

  Singly-linked lists carry only after information. Doubly-linked lists carry before and after information. At twice the storage overhead.

Linked Representation

• A list-element representation (usually called a node).

  struct Node 
    T data;
    Node * next  // singly-linked.
    Node * prev  // doubly-linked.
  

• The list ADT needs a pointer to the list.

  • Known as the head of the list.

• An element count for a constant-time size() operation.

List Add and Remove

• Manipulating linked elements is trickier than it is for array-based lists.

  Singly-linked elements require care. Manipulating before (solid) takes O(n) time. Manipulating after (dotted) takes O(1) time.

Other Details

• Element references.

  • Element pointers can be used as element references.

• Traversal and navigation operations.

  • Links don't affect the choice or implementation of the traversal and navigation operations.

List Comparison

	Array	List	List
		(Array)	(Node)
create	O(1)	O(1)	O(1)
delete	O(1)	O(1)	O(1)
add	O(n)	O(n)	O(1)
remove	O(n)	O(n)	O(1)
traversal	O(1)	O(1)	O(1)
navigation	O(1)	O(n)	O(n)
dynamic	No	No	Yes

Element Management

• Allocating and freeing list elements is expensive.

• Two tricks can reduce cost:

  1. Block allocate many elements at once.

     • Amortize element-creation costs over many elements.

  2. Hang on to removed elements.

     • Delay element-deletion costs.

Free-List Management

• Both element-management tricks can be implemented using a free list of elements.

• Block allocate elements onto the free list.

  • Without care, this could be an O(n) operation, where n is the block size in elements.

• New elements are pulled off the free list.

• Removed elements are hung back on the free list.

Do They?

• Around 50,000,000 alloc-free pairs.

  		int		point
  simple		0.09		0.1
  free list		0.03		0.07
  block		0.02		0.05

  • Time in usec/alloc-free.

  • Block size is 1000 elements.

  • See the code.

Sorting Lists

• The list traversal and navigation operations make sorting cumbersome.

  • Faster sorts exploit random access.

• Two tricks make list sorting easier:

  1. Sorting through references.

  2. Using merge sort.

Indirect Sorting

• Store a list's element references in an array, then sort the array.

  • Then reconstruct the list.

    

• Indirect sorting is useful whenever moving sort elements is expensive.

Merge Sorting Lists

• Although O(n log n), element copying makes merge sort more expensive than quicksort with intelligent pivot selection.

• A list's indirect before and after relations eliminate the need to copy.

  • Lists can be split and merged by rearranging elements without copying.

• Merge sort has potential relative to sorting linked lists.

Does It?

• Apparently not.

• See the code.

Why Sort?

• Sorting lists is moderately difficult and moderately expensive.

• Why sort? To more quickly search lists.

• A sorted list only moderately improves searching and increases insertion costs.

References

• Iterators: Signs of Weakness in Object-Oriented Languages by Henry Baker, ACM OOPS Messenger, pages 18-25, July, 1993.