Transcript Linked List - MHS Comp Sci

Linked Lists
Starring:
Singly Linked List
ListNode
Doubly Linked List
Iterator
Co-Starring:
ListIterator
1
Purpose:
In this lecture series we will learn about
Linked Lists
Linked Lists are another type of Data
Structure based off of the List Abstract
Data Type.
Linked Lists provide advantages in terms
of efficiency when certain types of actions
need to be performed on the data.
2
 Resources:
 Java Methods AB Data Structures Chapter 2 p.34
 Java Essentials Chapter 19 p.737
 Java Essentials Study Guide Chapter 16 p.263
 Barrons Chapter 8 p.244 & Chapter 11 p.361
 Big Java Chapter Chapter 19 p.737
 Lambert Comprehensive Units 4 & 5 (chs 12-16)
 Taft Notes p.12 (old) & also in last summers
notes
 Taft Notes 2003
3
Handouts:
1.Java Classes And Interfaces:
List
Linked List
Iterator
ListIterator
2.ListNode Class
3.Sample Code (UsingLinkedList.java &
SampleLinkedList.java)
4.ListIterator Illustration JESG p.266-268 &
p.269-280
4
 What we Will Cover in This Lecture:
 The List Interface as it pertains to the
ArrayList and Linked List Data Structures
 Advantages and Drawbacks of the
ArrayList Data Structure
5
 What we Will Cover in This Lecture:
 The Need for an Alternate method of Data
Storage
 The Concept of the Linked List
 The ListNode Class (Singly LL)
6
What we Will Cover in This Lecture:
Behaviors of a Linked List: Create, Insert
(Add) , Remove, Traverse (Iterate)
Singly, Doubly, Circular LL & LL with a Tail
Review Of Sample Code (Instructor)
7
What we Will Cover in This Lecture:
TPS Create Your Own Linked List Class
Java’s LinkedList Class
Doubly LL
8
What we Will Cover in This Lecture:
Iterator and ListIterator Classes
Iterating Thru a LinkedList (Java Class)
Big-O of a Linked List (compared to
ArrayList)
The AP AB Requirements
9
The List Interface
Lets Re-focus on the List Interface and
then we will look at a class, LinkedList,
that implements the List interface
10
11
This is merely a structure or a set of
criteria that can be implemented different
ways
We can have a LinkedList implementation
of the Abstract List Structure. All we need
to do is make sure we provide for the
BEHAVIORS as specified in the Criteria for
a List (add, remove, get, size, modify)
12
Each implementation must be evaluated
against their relative “costs” when
deciding which one to use for a particular
system
The List interface merely identifies the
behaviors that MUST exist in a List
13
The actual implementation of which is left
to the specific data structure
As for the Iterator and ListIterator
Interfaces, we will discuss these shortly
The List Interface requires you implement
a Size and an Add Behavior
14
The List also requires implementation of a
ListIterator.
We will use this when we work with Java’s
LinkedList class
15
The ArrayList Data Structure’s Advantages
and Drawbacks
Since Lists can be implemented as either
an ArrayList or a LinkedList we need to
discuss when we would select one over
the other as each has strengths as well as
limitations
16
ArrayLists are good at direct access of the
n-th element --- O(1)
This makes arrays excellent for a Binary
Search as it requires direct access to the
middle of an Array of elements
17
LinkedLists, by their nature, do not
provide direct access to specific Nodes
because each element only knows about
its previous or next Node. So access to a
specific Node is a Linear operation --- O(n)
18
Arrays are not good at inserting elements
at the top or near the middle and are also
not best used when the size of the list
varies widely--- O(n)
19
LinkedLists are best at insertion and
removal of specific nodes as we merely
have to rearrange the links --- O(1)
They are also good in situations where the
size of the list is unknown as nodes are
only allocated as needed, leading to no
wasted memory
20
You do not need to RESIZE a LinkedList
21
Therefore, when the data being stored is
static and its size is known an Array is a
better choice because its weaknesses are
minimized and its strengths compliment
the dominant process of searching the
data --- Log(n)
22
In situations where the size and content of
the data vary to a point where these
operations become the dominant process
a LinkedList is preferred
This is because the insertion and removal
are efficient , O(1), and we can live with
sporadic searches --- O(n)
23
Alternate List Implementation (Linked
List)
We can think of an Array or an ArrayList
as a book
A Book is a contiguous set of elements
indexed by page numbers
We can read through the book page by
page or we can open it directly to any part
of the book
That’s what a book is best at doing
24
However, we can not easily insert a new
page into an existing book as we would
have to rearrange the pages that follow
the insert
Also, if the book becomes too big for its
bindings, we would need to transfer the
pages to a Bigger one
25
We can think of a LinkedList as a
magazine article
The article appears “in parts” scattered
throughout the book
We need to know where the first “part” of
the article is
26
Then at the end of each “part” we are told
where the next “part” is
We only know when the article is
completed when it says “END” at the end
of the last “part”
27
Since the article is spread out, it is not a
problem to insert a new piece to the story
It is also easy to remove a part of the
story
However, we can only get to a specific
“part” of the story by traversing the entire
article from the beginning
28
The Conceptual Linked List
More formally, an element of a Linked List
is a called a “node”
Each node contains information plus a
pointer to the next node
The nodes provide REFERENCES to
another node
29
We know a Linked List ends when its last
node points to nothing (NULL)
ILLUSTRATION:
Given a class called AirFLight that
contains a flight destination and a flight
number we could construct the following
Data Link:
30
“Head” of the Link is at OC1
ATLANTA #100
OC4
NEWARK #300
ORLANDO #500 OCE
KENNEDY #350
OC7
NULL
31
The ListNode Implementation (for AB
Exam)
The previous example illustrates a Singly
Linked List
This type of LinkedList contains a Head
node and each node only knows about its
next node
32
A Singly Linked List is best used in cases
where we insert new nodes in the
beginning (not in the middle or the end) of
the list and where searches in the list are
minimized
Go to the handout that displays the
ListNode class
For us to create our own LinkedList we
need to create a “node” class
33
This class must contain two class level
attributes, one to hold an actual data
element and one to hold the reference to
the next node in the list
There are also methods to set these
values
34
public class ListNode
{
private Object value;
private ListNode next;
public ListNode(Object initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}
public Object getValue()
{
return value;
}
public ListNode getNext()
{
return next;
}
35
public void setValue(Object theNewValue)
{
value = theNewValue;
}
public void setNext(ListNode theNewNext)
{
next = theNewNext;
}
36
This ListNode is self-referential as it
refers to the ListNode data type inside the
ListNode datatype
When we implement our own LinkedList
we will use this class as our standard
node class
The ListNode class, as currently
constructed, reflects a Singly LinkedList
37
Furthermore, the ListNode class is going
to be used on the AP exam for questions
on any LinkedList question
Also this class would be used as a base
for any LinkedList Free Response
question
What is missing from this class is the
actual data that is to be maintained at
each node
38
The attribute private Object value; needs
to hold some value
It can be ANY object, but we will use in
our examples an object that maintains
flight information
39
public class AirFlight
{
private String Destination;
private int flightNum;
public AirFlight(String s, int num)
{
Destination = s;
flightNum = num;
}
public String getDestination()
{
return Destination;
}
40
public int getFlightNum()
{
return flightNum;
}
public String toString()
{
return Destination + " flight #" + flightNum;
}
}
41
The flight class does not “KNOW” it is a
part of a list and it only contains
information about a specific airline flight
42
The ListNode class does not care about
the type of object at each node, it only
cares about maintaining a REFERENCE to
an object and the LOCATION of the next
node
43
This provides a level of abstraction
In the next sections we will examine the
SampleLinkedList code to see a
LinkedList in action
44
ListNode as a Generic Class
As presently Constructed, the ListNode
class accepts an Object reference as the
“value” Being linked.
Therefore, when we GET the state of the
value pointed to by a given Node, we
must CAST to the specific object we are
linking
45
ListNode as a Generic Class
For Example, if we are linking instances
of Airflight we must:
AirFlight a = (AirFlight)head.getValue();
However, if we were to modify the
ListNode class to be Generic, we can set
the “value”
46
ListNode as a Generic Class
Object when the Node is constructed,
then we would do the following:
ListNode<Integer> node = new
ListNode<Integer>(12);
Then we do not need to cast when
accessing the “value” at a given node:
Integer I = head.getValue()
47
ListNode as a Generic Class
Furthermore, we must use the generic
constructor whenever we create a Node
instance:
head.setNext(new ListNode<Integer>(34));
48
ListNode as a Generic Class
TestListNodeGeneric.java is the driver
program that utilizes a generic ListNode
class.
You will be writing the supporting
ListNode class as one of your
assignments.
49
Linked List Behaviors:
Like any other List Data Structure a
LinkedList must provide for the following
behaviors:
Create a new list
Insert (Add) a new node to the list
Remove a node from the list
Traverse (Iterate) the nodes in the list
50
To begin working with your own
LinkedList (not java’s LinkedList class)
you need to create a class that will hold
the information you wish to store
You then need to Create an initial Node in
the list and make this node the head of
the list
51
Lets work with our flight class and create
an initial instance of it:
AirFlight f1 = new AirFlight("Atlanta", 100);
Then create an initial node to maintain the
flight data:
ListNode node = new ListNode(f1, null);
// A
Then establish this as the start of the list:
ListNode head = null;
head = node;
52
We can now add or insert nodes to the
front of the list
We can do this 2 ways, we can use the
ListNodes setNext method to point the
initial node to the next node in the list:
head.setNext(new ListNode(f2, null));
// A O
53
Or we can use the ListNodes constructor
to establish a new node and reset the
head
head = new ListNode(f4,head);
// N K A O
head = new ListNode(f5,head);
// U N K A O
head = new ListNode(f6,head);
// H U N K A O
Lets Draw out the resulting linked list on
the Board…
54
We can print out the contents of the first
node:
System.out.println("The first Node is " +
((AirFlight)head.getValue()).toString());
Note that AirFlight class has a toString
method
55
We can also retrieve the object at the
head node
AirFlight a = (AirFlight)head.getValue();
We can easily remove a node from the
front of the list:
head = head.getNext();
56
This remove works by setting the head to
bypass the first node and point to the
second node
Once the garbage collector sees that the
first node is no longer referenced, it will
destroy it
57
We can traverse the list:
for (node = head2; node != null ; node =
node.getNext())
{
b = (AirFlight)node.getValue();
System.out.println(b.toString());
}
Lets look at the sample code
SampleLinkedList.java to see how to add
and remove nodes from the end of the list
58
Singly Linked List
A Singly LinkedList is one where the
nodes in the link know only about the
node that FOLLOWS it
Head = OC4
OC4 OC7 OC1 BA3 CD4 AE4
Hou Utah New Ken Atl Orlando
OC7 OC1 BA3 CD4 AE4 NULL
59
Insertion and removal at the beginning of
the list are efficient as they are constant
time O(1)
Searches and traversals are Linear time
O(n)
60
Linked List with a Tail
We keep track of the head node to provide
us with the start of the list
We can also keep track of the last node of
the list by maintaining a reference to its
tail
61
ListNode tail = head2;
Then as we insert new nodes we update
the tail reference:
node = new ListNode(f2,null);
// change previous "tails" next node
// BEFORE updating the list to include the
NEW tail
tail.setNext(node);
tail = node;
62
Using the tail we can traverse from the
end of the list and insert to the end of the
list
In the previous example the head is still
OC4 but the tail is AE4
63
Circular Linked List
In a circular linked list, we maintain the
reference to the head of the list in the last
node of the list
This type of list does not contain a NULL
next pointer in the last node to signify the
end of the list
We know the list has been fully traversed
when the “next” reference matches the
head’s reference
64
ListNode head3 = new ListNode(f1, null);
tail = head3;
tail.setNext(head3);
node = new ListNode(f2,null);
// change previous "tails" next node
// BEFORE updating the list to include the NEW
// tail
tail.setNext(node);
tail = node;
tail.setNext(head3); // 8. Cir LL requires last
// node's "next" to point to HEAD or First node
65
 Traversal of a Circular list is different as we can
no longer check for NULL:
node = head3;
do
{
b = (AirFlight)node.getValue();
System.out.println(b.toString());
node = node.getNext();
System.out.println(node + " "+ head3);
}while (node != head3); // this is a circular
// linked list !!!
66
Doubly Linked List
A Doubly Linked list improves on the
singly LinkedList because each node
contains a reference to the node before it
as well as the node after it
Before we can implement this type of List
we need to enhance the ListNode class to
add in a reference to the previous node:
67
private ListNode prev;
We also overload the constructor to
create a doubly Linked List
public ListNode(Object initValue, ListNode
initNext, ListNode initPrev)
{
value = initValue;
next = initNext;
prev = initPrev; // DOUBLY LINKED LIST
68
We also need to be able to access and
modify the previous reference:
public ListNode getPrev()
{
return prev;
}
public void setPrev(ListNode theNewPrev)
{
prev = theNewPrev;
}
69
A Doubly Linked List is used to maintain
an ordered list of nodes
Our Insertion and Removal become more
involved as we need to iterate through the
nodes
For Insertions, we need to know if the
node is the first one created
If it is then it is the head node and its
NEXT and PREV references are null
70
Otherwise, we traverse the list, keeping
track of the prev node, until we locate a
node whose data is greater than the data
in the new node
Once the proper place is found we link the
previous node to point to the new node
Then we have the new node point to the
“previous” node’s next node
71
We still have to maintain the prev
references
The new node points back to the
“previous” node and the node the new
node points to needs have its prev node
refer to the new node
72
Lets put an example on the board (#5 in
code handout)
73
Lets look at the sample code for the
Doubly Linked List example
74
Sample Code Review
For a more complete review of a Linked
List lets refer to the sample code :
SampleLinkedList.java
75
TPS
Create Your Own Linked List

Make a copy of the following files to your
student account:


LittleList.java
TestMyList.java
These files are online as are the TPS
instructions
You will create your own list class
76
TPS2 Create a Templeted / Generic
Version of the ListNode class
We can also Convert the ListNode class
to utilize Generic Capability
In this case, we would modify the
ListNode class to accept a specific object
to be Linked
77
TPS2 Create a Templeted / Generic
Version of the ListNode class
The following is a code sample of the
Driver program that utilizes a generic
ListNode:
ListNode head = null;
ListNode<Integer> node = new
ListNode<Integer>(12);
head = node;
System.out.println("The first Node is " +
(head.getValue()).toString());
78
TPS2 Create a Templeted / Generic
Version of the ListNode class
NOTE: the getValue method of ListNode’s
Generic Version DOES NOT require a
Cast to a specific object, Integer, in this
case.
// add a node to the list using the setnext
method
// this will be the second node in the list
head.setNext(new ListNode<Integer>(34);
79
 TPS2
Create a Templeted / Generic Version
of the ListNode class
// add new nodes to the BEGINNING OF THE LIST
ListNode<Integer> t = new ListNode<Integer>(65);
t.setNext(head);
head = t;
System.out.println("The New first Node is " +
(head.getValue()).toString());
80
 TPS2 Create a Templeted / Generic Version of
the ListNode class
 Now Traverse the List, Note: YOU CANT USE
FOR EACH LOOP AS OUT LISTNODE DOES
NOT UTILIZE ITERATOR OR LISTITERATOR
Integer b;
for (node = head; node != null ; node =
node.getNext())
{
b = node.getValue();
System.out.println(b.toString());
}
81
TPS2 Create a Templeted / Generic
Version of the ListNode class
Removing a Node:
head = head.getNext();
82
TPS2 Create a Templeted / Generic
Version of the ListNode class
Modify ListNode to allow Generics
Make a copy of the following files to your
student account:

TestListNodeGeneric.java
Using this code as a guide, create your
own version of a generic ListNode class
83
Java’s LinkedList Class
Java has a LinkedList class that is
designed to be a Doubly Linked List
This class is used in much the same way
as the ArrayList class
84
LinkedList ll = new LinkedList();
ll.add(f1);
ll.add(f2);
ll.remove(1); // removes
ll.removeLast();
System.out.println();
System.out.println("AFTER Removal There is
NOW " + ll.size() + " Nodes in the List “);
printLL(ll);
AirFlight af = (AirFlight)ll.getFirst();
85
You can loop thru a LinkedList by using
the get(index) method, but it has hidden
costs as we can explain by examining the
following code:
for (int i = 0; i < ll.size(); i++)
{
AirFlight af = (AirFlight)ll.get(i);
}
86
Each iteration begins AT THE START of
the list and traverses to the i th node
You are responsible for understanding the
implicit costs of the methods in the
LinkedList class
Using the LinkedList class we can use the
get method that returns the i th node
87
Each call to this method traverses from
the beginning of the list and has a Linear
cost O(n)
We can move thru the list by iterative
calls to the get method incrementing the
index by one each time
However, EACH call to get STARTS at the
HEAD node and becomes a Quadratic
operation O(n^2)
88
This leaves us with an efficiency issue
that is addressed with the Iterator and
ListIterator interfaces which we will
discuss shortly
Lets open up and review Java’s
LinkedList class in JavaDoc
Now Review the AP Subset for the
LinkedList Class (USE AP JAVA DOC)
89
It is important to note that there are some
hidden performance issues to consider
with the implementation of the List
Interfaces get and set behaviors
The ArrayList implementation of these
methods are an asset to the array as the
“cost” of these operations is Constant --O(1)
90
The LinkedList implementation, however,
is not as efficient
For a LinkedList to access the n th node it
must start at the head of the list and
traverse each node, counting each one,
until it gets to the specified one --- Linear,
O(n)
91
In contrast the add behavior as
implemented in a LinkedList merely
rearranges the links while the ArrayList
must rearrange its elements and/or copy
them to a larger array
LinkedLists are also efficient at inserting
a node at the beginning of the list or at
the end (as long as it has a tail)
92
Using the Generic Version of the LinkList
Class
Java’s LinkedList Class is Generic,
therefore, we can identify the type of
Object we wish to link.
Code Examples are in the
UseLinkedListClassWithGeneric.java file
93
Using the AirFlight class as the object, we
will create a LinkedList as follows:
LinkedList <AirFlight> ll = new
LinkedList<AirFlight>();
AirFlight f1 = new AirFlight("Atlanta", 100);
AirFlight f2 = new AirFlight("Orlando", 500);
AirFlight f3 = new AirFlight("Kennedy",
350);
ll.add(f1);
ll.add(f2);
ll.add(f3);
94
Then you can Iterate using the FOR EACH
loop:
for(AirFlight r:ll)
{
// display list with newark removed
System.out.println(r.toString());
}
95
 You can Iterate by calling a method and passing
a LIST instance:
printLL(ll);
static public void printLL( List ll )
{
Iterator iter = ll.iterator();
iter = ll.iterator();
while(iter.hasNext())
{
// display list with newark removed
System.out.println(iter.next());
}
}
96
 You can Iterate by calling a method and passing a Generic LIST
instance:
static public void printLLITERATOR( List<AirFlight> ll )
{
for(AirFlight r:ll)
{
// display list with newark removed
System.out.println(r.toString());
}
System.out.println(" AND TRAVERSE WITH AN
ITERATOR...");
// NOW ITERATE using an iterator
for(Iterator<AirFlight> itr = ll.iterator(); itr.hasNext();)
{
System.out.println(itr.next());
}
}
97
Iterator Interface
We can traverse thru a list efficiently if we
have access to the first node in the list
for (node = head2; node != null ; node =
node.getNext())
However, if we implement the linkedlist as
part of an encapsulated class we do not
have access to the head of the list
98
We can use an Iterator to process thru a
linkedlist
This gives us the flexibility to handle each
node as we need to
We can make use of the Iterator to
sequence through a list
The LinkedList class has an Iterator
reference that can be used to “iterate”
thru the list
99
When you create an Iterator it points to a
specific element in the list (usually the
first node)
You can have multiple iterators against a
single List object and each can be at a
different “node”
100
 Iterating thru a Linked List
static public void printLL(List ll)
{
System.out.println();
// instance of iterator
Iterator iter = ll.iterator();
// roll thru nodes of list until none are left
while(iter.hasNext())
{
// returns the next node's Object (value) in the list
System.out.println(iter.next());
}
}
101
 Remove a node thru the iterator
while(iter.hasNext())
{
// returns the next node's Object (value) in the
// list
AirFlight f = (AirFlight)iter.next();
// remove the flight number 300 -- Newark
if (f.getFlightNum() == 300)
{
iter.remove();
System.out.println(f + " Removed");
}
}
102
ListIterator Interface
Iterators have limitations as they always
start at the beginning of the list and then
only move forward (in one direction)
What if we had to find duplicate flights in
a list of AirFlights
We could nest separate iterators but this
is inefficient because the inner iterator
will start at the first node each iteration
103
AirFlight fl1, fl2;
Iterator iter1, iter2;
iter1 = ll.Iterator();
while (iter1.hasNext( ))
{
fl1 = (AirFlight)iter1.next();
iter2 = ll.Iterator(); // will start at first node each time
while(iter2.hasNext( ))
{
fl2 = (AirFlight)iter2.next();
if (fl1 != fl2 && fl1.getFlightNum( ) ==
fl2.getFlightNum( ) )
System.out.println(“Duplicate Flight: “ +
fl1.toString())
}
}
104
NOTE: The check fl1 != fl2 makes sure
we are not comparing the same 2 flights
Java’s enhanced version of the Iterator is
the ListIterator (java.util.ListIterator)
ListIterator EXTENDS the Iterator
interface
105
In the Full Java version of the
ListInterface there are several methods
that allow us to move forward as well as
backward in the LinkedList (remember
that the Java LinkedList is implemented
as a Doubly LL)
To get the full power of this interface, look
at the FULL Java Doc where the List
Interface has an overloaded ListIterator
that passes in an index so we can START
our iteration at any point in the list
106
Lets open up and review Java’s FULL
VERSION OF THE Iterator & ListIterator
Interfaces in JavaDoc
Therefore we can make our duplicate
flight search more efficient:
107
AirFlight fl1, fl2;
ListIterator iter1, iter2;
iter1 = ll.ListIterator();
while (iter1.hasNext( ))
{
fl1 = (AirFlight)iter1.next();
iter2 = ll.ListIterator(iter1.nextIndex( )); // will start at
//index node each time
while(iter2.hasNext( ))
{
fl2 = (AirFlight)iter2.next();
if (fl1 != fl2 && fl1.getFlightNum( ) ==
fl2.getFlightNum( ) )
System.out.println(“Duplicate Flight: “ +
fl1.toString())
}
}
108
Lets open up and review AP Java’s
Iterator & ListIterator Interfaces in the AP
JavaDoc (USE AP JAVA DOC)
Review the AP Subset for the Iterator and
ListIterator Interfaces
Note that the AP subset for the List
Interface DOES NOT include the
overloaded ListIterator method
109
add inserts a new node (specified
element) into the list BEFORE the current
iterator position and moves the iterator
PAST the inserted element (node)
set replaces the value of the node
(element) returned by the next method
remove method removes the last node
returned by the iterator AND CAN only be
called ONCE AFTER a call to the next
method
110
Lets look at the ListIterator sample code
handout (JESG p.266-268)
For the AP exam we will not be asked to
iterate through the LinkedList class as a
doubly linked list as the AP version of the
ListIterator class has limited behaviors
111
Big-O of a Linked List
Singly
Doubly
LL CLass
Insert / Add /remove
to beginning of list
O(1)
O(1)
O(1)
Insert / Add /Remove
to end of list
O(n)
O(1)
O(1)
Insert / Remove in
(middle) of list
Search for a key
O(n) for search O(n) for search O(n) for srch
O(1) for insert O(1) for insert O(1) for insert
O(n)
O(n)
O(n)
112
LinkedList Class
(Doubly LL)
addFirst, addLast,
getFirst, getLast,
removeFirst,
removeLast
O(1)
set
O(n) to locate note
113
Examine the addlast code in Barrons
page 248 and Determine its efficiency
114
AP AB Subset Requirements
Students are expected to write linked list
insert (add) to front, insert to tail, insert in
order, remove, traverse, a singly, doubly
or circular linked list
Students are also responsible for using
the Java LinkedList class an the Iterator
and ListIterator Interfaces
115
Multiple Choice and Free Response
Questions will use the ListNode class as
the NODE for Linked List implementations
Students also need to understand the BigO of Linked List behaviors and compare
them to ArrayLists
116
Students must also evaluate appropriate
selection of a list (linked or array)
117
LABS:
POE Revisited
Case Study Modifications
Barrons M/C Questions
Free Response Questions
Enhance the ListNode Class to
implement a Doubly LL & LL with
Tail]
Handout of Multiple Choice Questions
118
TEST IS DAY
AFTER THE
LABS ARE DUE
!!!!!
119