Data Structures and Algorithms Lecture Notes

2 February 2011 • Linked Lists

---

Outline

Motivation List properties. The list interface. List 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 and independent of size.
• 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 expensive to change array size.
• Static data structures are inconvenient (if too small) or wasteful (if too large).
  • It’s hard to get the size right.

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 Interface

• 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 Interface 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(); r.more(); r = r.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 odd.

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

• The data structure is being changed while it’s being traversed.

List Implementations

• What implementations will do for the list?
• 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 implementation.
  • The implementation 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 may now involve every element.
    • Pointers as element references help here.

List Adding and Removing

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

  

  • What to do if there’s no more space?
• Deleting an element involves sliding elements one to the left.
• Potentially makes all references phantom

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	fast	fast
delete	fast	fast
add	slow	slow
remove	slow	slow
traversal	fast	fast
navigation	fast	slow
dynamic	No	No

• fast: single-element operation.
• slow: potentially n-element operation.

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 or a link).

  class Node<T>
    T data
    Node next  // singly-linked.
    Node prev  // doubly-linked.
  

• The list implementation 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) may involve every element. Manipulating after (dotted) involves one element.

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	fast	fast	fast
delete	fast	fast	fast
add	slow	slow	fast
remove	slow	slow	fast
traversal	fast	fast	fast
navigation	fast	slow	slow
dynamic	No	No	Yes

• fast: single-element operation.
• slow: potentially n-element operation.

Summary

• Arrays are efficient but can’t change size.
• Linked lists are reverse: dynamic but less efficient.
• Changing the trade-offs moves from one to the other.

Credits

• Peruvian Quipu - a knotted mathematical mystery by Carsten ten Brink under a Creative Commons AT NC ND license.

---

This page last modified on 2011 February 2.