Transcript COMP 121 Week 11

COMP 121
Week 11: Linked Lists
Objectives
Understand how single-, double-, and
circular-linked list data structures are
implemented
 Understand the LinkedList class
 Understand the Iterator interface
 Understand the ListIterator interface


Become familiar with another piece of the
Java Collection framework
Linked Lists

Array List
 The
add and remove methods operate in linear
time O(n)


Require a loop to shift elements in the underlying
array
Linked List
 Overcomes
this by providing ability to add or
remove items anywhere in the list in constant
time O(1)
 Each element (node) in a linked list stores
information and a link to the next, and
optionally previous, node
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Single-Linked List Node
A node contains a data item and one or
more links
 A link is a reference to a node
 A node is generally defined inside of
another class, making it an inner class
 The details of a node should be private

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Single-Linked List
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Add a Node in a Single-Linked List
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Remove a Node from a SingleLinked List
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Double-Linked Lists

Limitations of a single-linked list include:
 Insertion

at positions other than the first is O(n)
Insertion at the front of the list is O(1)
 Can
insert a node only after a referenced node
 Can remove a node only if we have a reference
to its predecessor node
 Can traverse the list only in the forward direction

Limitations are overcome by adding a
reference in each node to the previous node
(double-linked list)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Double-Linked List Node
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Double-Linked List
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Add a Node to a Double-Linked
List (Steps 1 and 2)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Add a Node to a Double-Linked
List (Steps 3 and 4)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Remove a Node from a DoubleLinked List
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Circular Lists

Circular-linked list
 Links
the last node of a double-linked list to the
first node and the first to the last

Advantages
 Can
traverse in forward or reverse direction
even after you reach the last or first node
 Can visit all list elements from any starting point
 Can never fall off the end of a list

Disadvantage
 Possibility
of an infinite loop!
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Circular Lists
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
The LinkedList<E> Class
Part of the Java API
 Implements the List<E> interface using a
double-linked list

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
The Iterator<E> Interface
The interface Iterator is defined as part
of API package java.util
 The List interface declares the method
iterator(), which returns an
Iterator object that will iterate over the
elements of that list
 An Iterator does not refer to or point to
a particular node at any given time but
points between nodes

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
The Iterator<E> Interface (cont’d)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
The ListIterator<E> Interface

Iterator limitations

Can only traverse the List in the forward direction
Provides only a remove method
 Must advance an iterator using your own loop if
starting position is not at the beginning of the list

ListIterator<E> is an extension of the
Iterator<E> interface that overcomes
the above limitations
 Like Iterator, a ListIterator should
be thought of as being positioned between
elements of the linked list

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
The ListIterator
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
The ListIterator Interface
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
LinkedList Methods that
Return ListIterators
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Comparison of Iterator and
ListIterator

ListIterator is a subinterface of Iterator
that implement ListIterator provide the
capabilities of both
 Classes

Iterator interface
 Requires
fewer methods
 Iterates over more general data structures



Only in one direction (forward)
Iterator is required by Collection interface
ListIterator is required by List interface
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Conversion between a
ListIterator and an Index
The nextIndex method returns the index
value of the item that would be returned by
a call to the next method
 The previousIndex method returns the
index value of the item that would be
returned by a call to the previous method
 The listIterator(int index) method
is a method in LinkedList

a ListIterator whose next call to
next() will return the item at position index
 Returns
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Project: Using a LinkedList

Develop a program to maintain a list of
homework assignments. When an
assignment is assigned, add it to the list,
and when it is completed, remove it. Keep
track of the due date. The program should
provide the following services:
 Add
a new assignment
 Remove an assignment
 Provide a list of the assignments in the order
they were assigned
 Find the assignment with the earliest due date
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Class Diagram
Assignment
HomeworkList
description
dueDate
theList
compareTo()
add()
remove()
showAssignments()
findEarliest()
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
HomeworkList Class
import java.util.ListIterator;
import java.util.LinkedList;
public class HomeworkList
{
private LinkedList<Assignment> theList;
public HomeworkList()
{
theList = new LinkedList<Assignment>();
}
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
HomeworkList Class (cont’d)
public void add(Assignment assignment)
{
theList.addLast(assignment);
}
public void remove(Assignment assignment)
{
theList.remove(assignment);
}
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
HomeworkList Class (cont’d)
public void showAssignments()
{
String message;
int i = 1;
for (Assignment assignment : theList)
{
message = "Assignment #" + (i++) +
":\n" +
assignment.getDescription() +
"\nDue date: " +
assignment.getDueDate();
System.out.println(message);
}
}
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
HomeworkList Class (cont’d)
public Assignment findEarliest()
{
Assignment earliest = null;
Assignment current;
ListIterator<Assignment> iter =
theList.listIterator();
if (iter.hasNext())
{
earliest = iter.next();
while (iter.hasNext())
{
current = iter.next();
if (current.compareTo(earliest) < 0)
{
earliest = current;
}
}
}
return earliest;
}
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Summary
A linked list consists of a set of nodes,
each of which contains its data and a
reference to the next node
 To find an item at a position indicated by
an index in a linked list requires traversing
the list from the beginning until the item at
the specified index is found

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Summary (cont’d)
An iterator gives with the ability to access
the items in a List sequentially
 The ListIterator interface is an
extension of the Iterator interface
 The Java API provides the LinkedList
class, which uses a double-linked list to
implement the List interface

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Any Questions?