Transcript Chapter 6 Slides

Chapter 6
Linked Structures
© 2006 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
Overview
●
6.1 Introduce linked structures.
–
Made from chains of nodes, connected by references.
●
6.2 Stacked and Queue interfaces are implemented.
●
6.3 List interface
●
6.4 Linked structures in the Java collections framework.
●
Java API: See Dr. Lee Website
List Nodes
●
A list node contains only one element but it also
contains a reference to another list node.
List Nodes
1. To create the nodes, then link them together:
2. To create the entire chain with one expression:
List Nodes
●
●
These chains of nodes are usually constructed
gradually.
We can splice (separate) a node out of a chain
if we can find the node's predecessor.
node1.setNext(node2.getNext());
Linked List
Linked List
Doubly Linked Nodes
Doubly Linked Nodes
The LinkedStack Class
●
The LinkedStack points at the top of the stack.
●
See Figure 6-9 on page 162.
The LinkedStack Class (Fig. 6-10, p162)
Same operations
as in Fig 4-1, p88
The LinkedStack Class (Fig. 6-11, p163)
The LinkedStack Class (Fig. 6-11, p163)
The LinkedStack Class (Fig. 6-12, p164)
Pushing a series of elements (A,B,C) onto a LinkedStack.
The LinkedStack Class
●
●
●
The pop() method in Fig. 6-11 (p163)
splices a node out.
We have to store the element from the
node we are removing in a variable
called “result” (Fig. 6-11, line 27).
We have to do this before we remove
the node (Fig. 6-11, line 28), because
the node becomes unreachable once
we change the value of the top.
The LinkedStack Class (Fig. 6-13, p165)
Repeated popping (C, B, A) from a LinkedStack.
The LinkedQueue Class (Fig. 6-13, p165)
Always append a new item to the back
and remove an item from the front.
The LinkedQueue Class
The LinkedQueue Class
line 22: to append a new node to the back
The LinkedQueue Class
line 36: to remove the front node
The LinkedQueue Class (Fig. 6-16, p167)
The LinkedQueue Class (Fig. 6-17, p167)
●
●
If we remove the last node, front becomes null.
It does not matter that back still points to the
node that was just removed, because we didn’t
touch the back pointer (or reference).
front = front.getNext();
front becomes null.
The LinkedList Class
The LinkedList Class
●
●
LinkedList methods involve walking down
(traverse) the chain of reference.
General form:
The LinkedList Class (Fig. 6-19, p169)
The LinkedList Class (line 13 tally = count)
The LinkedList Class
●
●
●
●
●
These loops do not use an int to keep track of the
current position in the list.
We know when we've reached the end of the loop
when node is null.
The get() and set() methods do use an int, since
they want to advance a specific number of nodes
to find the node we want to get or set. (See Figure
6-20 on page 170, or next slide.)
The get() method is to get the item from the node
specified by the index number.
The set() method is to set (store) the target item
into the node specified by the index number.
The LinkedList Class
(get or set the element of the node with “index” number)
The LinkedList Class (Fig. 6-22, p171)
Append a new node (item = “target”) to the end of the linked list.
The LinkedList Class
●
Lines 3 (for an empty list) and 9 (for non-empty
list) in the add method (Fig. 6-22) do almost
exactly the same thing:
–
●
●
Create a new ListNode and set some reference to
point to.
We can use polymorphism to write a single line
of code which does whichever of these things is
appropriate.
Since LinkedList and ListNode have no fields or
methods in common, a superclass doesn't really
make sense; an interface is a better choice.
The Predecessor Interface
The LinkedList Class
●
●
Both LinkedList and ListNode will have to implement it.
ListNode already provides these methods. So we just have to
change the first noncomment line in Figure 6-4 (p159) to:
public class ListNode<E> implements Predecessor<E> {
The Predecessor Interface
●
The Predecessor interface is implemented by two classes.
●
The LinkedList class implements two interfaces. Fig. 6-25
A Shorter Version of the add() Method
(Fig. 6-26)
The LinkedList Class
●
Two remove() methods
–
–
–
–
–
●
One of these methods removes the element at a
particular position;
The other checks a particular Object.
Both use the technique of splicing out a node.
We walk down the list looking for either the ith node
or the node containing target.
Problem: Once we find the offending node, we've
forgotten the previous node.
Solution: Keep track of two nodes (Fig. 6-27, p173)
–
–
The previous one
The current one
●
Know as a two-finger algorithm.
The LinkedList Class (Fig. 6-27, p173)
The two-finger algorithm
The LinkedList Class (Fig. 6-28, p173)
The ListIterator Class
Fig. 6-29 The iterator() method returns an
instance of ListIterator.
The ListIterator Class
The ListIterator Class
The Java Collections Framework Revisited
●
Java collections framework contains a class
LinkedList.
–
It is a Doubly linked list
●
Provides methods addFirst(), addLast(), removeFirst(),
and removeLast().
–
A LinkedList can function as a stack, a queue, or
even a deque.
–
Deque is a double-ended queue allowing insertion
into or deletion from either end. (p115)
The Java Collections Framework Revisited
The Java Collections Framework Revisited
●
Linked structures are sequential access.
–
●
With sequential access data structure, it is
necessary to go through the preceding elements.
Array-based structures are random access.
–
In a random access data structure, we can jump
to any pint instantaneously.
The Java Collections Framework Revisited
●
If ArrayLists and LinkedLists are built into Java,
why have we bothered to write these classes
ourselves?
–
These are relatively easy data structures to build.
●
Needed to understand the more complex structures yet
to come.
–
We will likely have to write a data structure that is
very similar to, but not identical to, a built-in
structure.
–
Knowing what's going on “under the hood” allows
us to use the built-in structures more effectively.
Summary
●
The LinkedList class is a general-purpose linked structure.
●
We can build arbitrarily long chains of ListNodes.
●
●
●
●
●
●
A DoublyLinkedNode also contains a reference to the previous
node.
LinkedStack class splices nodes in and out of one end of a
chain.
LinkedQueue class appends a new node to the back and
removes a node from the front.
The Predecessor interface allows us to avoid writing special
code.
Two-finger algorithms require that we keep track of two
consecutive nodes.
Java collections framework provides a class LinkedList.
–
It is doubly linked.
Chapter 6 Self-Study Homework
●
Pages: 161-179
●
Exercises: 6.5, 6.10, 6.12, 6.23, 6.24.