Class 39: Linked Lists

Held Tuesday, November 7, 2000

Summary

Today we consider how to implement lists using nodes that are similar to the cons cells (pairs) that you saw in Scheme.

Notes

• Don't forget to vote!
• Don't forget Math 314 (topics in applied mathematics): Chaos and Fractals. Prerequs: Math 220 (or 218, if necessary)
• I still don't have the next homework ready. I hope to have it ready for tomorrow. The basic format will be "implement and test expandable, shiftable, array-based lists". (I'm working on the interfaces you'll implement.)
• Here are my curernt stressors:
  • I guest-taught a course yesterday afternoon; I'm also guest-teaching on Wednesday and next Monday.
  • I'm sick enough that I collapsed in bed at 6:00 last night.
  • Administrative stressors are at an all-time high (phone interviews for the first set of candidates; advising; a matter of academic honesty; more guest teaching; phase II planning; ...)

Overview

• Variant array-based implementations (see yesterday's notes)
• Linked lists (like Scheme lists)
• Implementation basics
• Methods
• More ...

Linked Lists

• Philosophy: Build a list by using nodes (cons cells, pairs) that contain links to surrounding elements (typically next, sometimes previous).
  • Note: Surround those nodes with a wrapper class
• Name: Linked List
• Implementations
• Efficiency

Code Basics

• The basic Node class.

  /**
   * Nodes for a linked list.
   */
  protected class Node {
    // +--------+------------------------------------------------------------
    // | Fields |
    // +--------+
  
    /** The contents of the current node.  Can never be null. */
    Object contents;
  
    /** A link to the next node.  Set to null if this is the last node. */
    Node next;
  
  } // class Node
  

• The wrapper class:

  /**
   * A linked list.
   */
  public class LinkedList {
    // +--------+------------------------------------------------------------
    // | Fields |
    // +--------+
  
    /** The first element of the list.  Set to null for empty lists. */
    Node first;
  
    /** The last element of the list.  Set to null for empty lists. */
    Node last;
  
    /** The length of the list.  Easier to store in a field than recompute. */
    int length;
  
  } // class LinkedList
  

Implementing Methods

• Hint: Always draw pictures.
• Precise details to be determined in class.

Variations

• Doubly-linked lists: Include a link to the previous element
• Circularly-linked lists: Include a link from the last element to the first.
• ...