Transcript COMP 121

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 List
ArrayList: add/remove methods operate in linear
time O(n)
 Require a loop to shift elements in the underlying
array
LinkedList:
 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
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 defined inside of List class, making it an
inner class
The details of a node should be private
Single-Linked List
Adding an Element
Removing an Element
Single-Linked List - Limitations
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
Solution: double-linked list
Double-Linked List Node
Double-Linked List
Adding an Element to a DoubleLinked List (Steps 1 and 2)
Adding an Element to a DoubleLinked List (Steps 3 and 4)
Removing an Element from a
Double-Linked List
Circular-Linked Lists
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:
 If not careful, can cause an infinite loop!
Circular Linked List
The LinkedList<E> Class
Part of the Java API
Implements the List<E> interface using a double-linked list
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
The Iterator<E> Interface (cont’d)
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
ListIterator
The java.util.ListIterator Interface
LinkedList Methods that Return
ListIterators
ListIterator vs. Index
nextIndex returns the index value of the item
that would be returned by a subsequent call to
next()
previousIndex returns the index value of the
item that would be returned by a subsequent call
to previous()
listIterator(int index) is a method of
the LinkedList class:
 Returns a ListIterator whose subsequent call to
next() will return the item at position index
Case Study: Writing 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
UML Class Diagram
Assignment
HomeworkList
description
dueDate
assignmentList
compareTo()
add()
remove()
displayAssignments()
findEarliest()
HomeworkList Class
import java.util.ListIterator;
import java.util.LinkedList;
public class HomeworkList
{
private LinkedList<Assignment> assignmentList;
public HomeworkList()
{
assignmentList = new LinkedList<Assignment>();
}
HomeworkList Class (cont’d)
public void add(Assignment assignment)
{
assignmentList.addLast(assignment);
}
public void remove(Assignment assignment)
{
assignmentList.remove(assignment);
}
HomeworkList Class (cont’d)
public void displayAssignments()
{
String message;
int i = 1;
for (Assignment assignment : assignmentList)
{
message = "Assignment #" + (i++) +
":\n" +
assignment.getDescription() +
"\nDue date: " +
assignment.getDueDate();
System.out.println(message);
}
}
HomeworkList Class (cont’d)
public Assignment findEarliest()
{
Assignment earliest = null;
Assignment current;
ListIterator<Assignment> iter =
assignmentList.listIterator();
if (iter.hasNext())
{
earliest = iter.next();
while (iter.hasNext())
{
current = iter.next();
if (current.compareTo(earliest) < 0)
{
earliest = current;
}
}
}
return earliest;
}
Summary
A linked list consists of a set of nodes, each of which
contains its data and a reference to the next node
Locating 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
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
Questions?