Back to Iterating Array-Based Lists. On to Linked Lists, Continued.

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

• 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
• 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:
```/**
*/
// +--------+------------------------------------------------------------
// | 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;

```

Implementing Methods

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

Variations

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

History

Wednesday, 23 August 2000

• Created as a blank outline.

Thursday, 24 August 2000

• Slight reorganization to page design.

Tuesday, 7 November 2000

• Created. All new!

Back to Iterating Array-Based Lists. On to Linked Lists, Continued.

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.