Data Structures and Algorithms Lecture Notes

16 February 2011 • Odds and Ends


Outline

A Dynamic-Array Pathology

Adding Delay

Delay Example

Controlling Delay

Dynamic Linked Sequences

void addAfter(T v)
  Node n = new Node()
  n.value = v
  n.next = next
  next = n

adding a new link

void remove(T v)
  Node l = findBefore(v)
  l.next = l.next.next

removing a value

Dynamic Storage Costs

Free Lists

Free-List Management

private Node newNode()
  if freeList != null
    Node n = freeList
    freeList = n.next
    return n
  return new Node()

adding a new link

public void remove(T v)
  Node n = findBefore(v)
  Node l = n.next
  n.next = l.next
  l.next = freeList
  freeList = l

removing a value

Oh Really?

Results

Free-List Problems.

Free-List Problems..

Dynamic-Array Lists

Faster Array Linked Lists

Link Definition

Example

Link Allocation

Free Lists Again

Linked-List Comparison

Summary


This page last modified on 2010 October 12.

Creative
    Commons License