Class 54: Linked Lists (1)

Held: Tuesday, 7 December 2004

Summary: Today we consider an alternate implementation of lists, linked lists, which are composed of nodes with links to each other.

Related Pages:

• EBoard.
• Sample List Code.
• Sample Linear Structure Code.

Notes:

• I will provide time for questions and answers at the beginning of class.

Overview:

• An OrderedList ADT
• Implementing lists with nodes
• Iterating linked lists
• Adding elements
• Deleting elements

Designing an OrderedList ADT

• What methods do we expect to see in OrderedList?
• Should OrderedList be an implementation of SimpleList?

Linked Lists

• Linked lists provide an alternative implementation of lists.
• Instead of using an underlying array, we instead use a collection of Nodes that are linked to each other.
• A wrapper class organizes the nodes (and keeps track of some of the nodes, most typically the first and last nodes).