Transcript wk14.1

Linked Structures - Review
Chapter 13
Instructor: Scott Kristjanson
CMPT 125/125
SFU Burnaby, Fall 2013
Scope
2
Introduction to Linked Structures:
 Object references as links
 Linked vs. array-based structures
 Managing linked lists
 Linked implementation of a stack
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 2
Linked Structures
3
An alternative to array-based implementations are linked
structures
A linked structure uses object references to create links
between objects
Recall that an object reference variable holds the address of
an object
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 3
Linked Lists
4
A Person object could contain a reference to another Person
public class Person
{
private String name;
private String addr;
private Person next; // Link to Another Person object
}
A series of Person objects could make up a linked list:
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 4
Linked Non-Linear Structures
5
Links could also be used to form more complicated, non-linear
structures
This is called a graph
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 5
Linked Lists
6
There are no index values built into linked lists
To access each node in the list you must follow the references
from one node to the next
Person current = firstPerson;
while (current != null)
{
System.out.println(current);
current = current.next;
}
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 6
Linked Lists – Inserting a node in the Middle
7
1. Set the “next” member in obj to refer to the next object in the list
2. Set the “next” member of the previous object to refer to the new object
obj
1
2
prev
x next
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 7
Linked Lists – Inserting a node at the front
8
Care must be taken to maintain the integrity of the links
To insert a node at the front of the list, first point the new node
to the front node, then reassign the front reference
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 8
Linked Lists – Deleting the First Node
9
To delete the first node, reassign the front reference
accordingly
If the deleted node is needed elsewhere, a reference to it
must be established before reassigning the front pointer
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 9
Put Linked List Details into separate Node Class
10
So far we've assumed that the list contains nodes that are self-referential
(Person points to a Person)
But often we'll want to make lists of objects that don't contain such
references
Solution: have a separate Node class that forms the list and holds a
reference to the objects being stored
Node
Node
Node
Node
Node
Node
Person
Person
Person
Person
Person
Person
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 10
Doubly Linked Lists
11
There are many variations on the basic linked list concept
For example, we could create a doubly-linked list with next and
previous references in each node and a separate pointer to the rear of
the list
next
Node
Node
Node
Node
Node
Node
Person
Person
Person
Person
Person
previous
Person
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 11
Implementing a Stack using Links
12
Let's implement a stack using a linked list to hold the elements
Our LinkedStack<T> class stores a generic type T and
implements the same StackADT<T> interface used
previously
A separate LinearNode<T> class forms the list and hold a
reference to the element stored
An integer count will store how many elements are currently
in the stack
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 12
LinkedStack<T>
13
public class LinkedStack<T> implements StackADT<T>
{
private int count;
private LinearNode<T> top;
/**
LinkedStack<T>
* Creates an empty stack.
*/
public LinkedStack()
{
count = 0;
top
= null;
LinearNode<T> top
}
int count
Linear
Node<T>
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 13
LinearNode<T>
14
public class LinearNode<T>
{
private LinearNode<T> next;
private T element;
public LinearNode()
{ next
= null;
element = null;
LinearNode<t> top
}
public LinearNode(T elem)
{ next
= null;
element = elem;
}
public LinearNode<T> getNext()
{
return next;}
LinearNode<t> next
Linear
T element
Node<T>
Object of Class T
public void setNext(LinearNode<T> node)
{
next = node;}
public T getElement()
{
return element;}
public void setElement(T elem)
{
element = elem;}
}
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 14
Implementing a Stack using Links
15
Since all activity on a stack happens on one end, a single
reference to the front of the list will represent the top of the
stack
Linear
Node
Linear
Node
Linear
Node
Linear
Node
Linear
Node
Linear
Node
T
T
T
T
T
T
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 15
Implementing a Stack using Links
16
The stack after A, B, C, and D are pushed, in that order:
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 16
Implementing a Stack using Links
17
After E is pushed onto the stack:
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 17
Implementing a Stack using Links
18
package jsjf;
/**
* Represents a node in a linked list.
*
* @author Java Foundations
* @version 4.0
*/
public class LinearNode<T>
{
private LinearNode<T> next;
private T element;
/**
* Creates an empty node.
*/
public LinearNode()
{
next = null;
element = null;
}
/**
* Creates a node storing the specified element.
* @param elem element to be stored
*/
public LinearNode(T elem)
{
next = null;
element = elem;
}
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 18
Implementing a Stack using Links
19
/**
* Returns the node that follows this one.
* @return reference to next node
*/
public LinearNode<T> getNext()
{
return next;
}
/**
* Sets the node that follows this one.
* @param node node to follow this one
*/
public void setNext(LinearNode<T> node)
{
next = node;
}
/**
* Returns the element stored in this node.
* @return element stored at the node
*/
public T getElement()
{
return element;
}
/**
* Sets the element stored in this node.
* @param elem element to be stored at this node
*/
public void setElement(T elem)
{
element = elem;
}
}
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 19
Implementing a Stack using Links
20
package jsjf;
import jsjf.exceptions.*;
import java.util.Iterator;
/**
* Represents a linked implementation of a stack.
*
* @author Java Foundations
* @version 4.0
*/
public class LinkedStack<T> implements StackADT<T>
{
private int count;
private LinearNode<T> top;
/**
* Creates an empty stack.
*/
public LinkedStack()
{
count = 0;
top = null;
}
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 20
Implementing a Stack using Links
21
/**
* Adds the specified element to the top of this stack.
* @param element element to be pushed on stack
*/
public void push(T element)
{
LinearNode<T> temp = new LinearNode<T>(element);
temp.setNext(top);
top = temp;
count++;
}
/**
* Removes the element at the top of this stack and returns a
* reference to it.
* @return element from top of stack
* @throws EmptyCollectionException if the stack is empty
*/
public T pop() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("stack");
T result = top.getElement();
top = top.getNext();
count--;
return result;
}
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 21
Implementing a Stack using Links
22
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 22
Key Things to take away:
23
Linked Objects:
• Object Reference variables can be used to create linked structures
• A Linked List is composed on objects that each point to the next in the list
• Objects stored in a collection should not contain any implementation
details of the underlying data structure that
• The order in which references are changed are very important
• Dealing with the first node in the list often requires special handling
• A Linked List implementation of a Stack adds elements to, or removes
elements from, one end of the linked list.
• Queues, Trees, and other structures can be created with Linked Objects
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 23
Practice Array Questions
24
Problem 1: Write a program that shuffles a deck of cards, then
deals out 5 cards each to two players.
Problem 2: Create a method that accepts two 2-dimensional
arrays A and B as formal parameters and returns the matrix
product A*B.
Problem 3: What is wrong with Bob’s Array code?
Problem 4: Write a method called sumArray that accepts an
array of floating point values and returns the sum of the values
stored in the array
Problem 5: Write a method called sum2DArray that accepts
an int[][] array and sums all the numbers in the array and
returns the sum of the values stored in the array.
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 24
Problem 1: Write a program to shuffle and deal cards
25
Step 1: Create the Shuffled Deck using a Stack
for(int i=0; i<Card.numSuits*Card.numValues; i++) {
boolean foundNextCard = false;
int
tries
= 0;
while (!foundNextCard) {
int cardValue = valueGen.nextInt(Card.numValues);
int cardSuit = suitGen .nextInt(Card.numSuits );
tries++;
if (cardDealt[cardSuit][cardValue] == false) {
Card nextCard = new Card(cardValue+1, cardSuit);
deckOfCards.push(nextCard);
cardDealt[cardSuit][cardValue] = true;
foundNextCard = true;
System.out.println("Card "+(i+1)+" : "+
nextCard+" found after "+tries+" tries");
}
}
}
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 25
Problem 1: Write a program to shuffle and deal cards
26
Step 2: Deal five cards to each player
for(int p=0; p<numPlayers; p++)
for(int c=0; c<numCardsPerHand; c++)
hand[p][c] = deckOfCards.pop();
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 26
Problem 1: Write a program to shuffle and deal cards
27
Step 3: Display both player’s hands
for(int p=0; p<numPlayers; p++) {
System.out.println("\nPlayer "+p+" hand:");
for(int c=0; c<numCardsPerHand; c++) {
System.out.println(
"Card " + c + ": "+hand[p][c]);
}
}
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 27
Problem 1: Write a program to shuffle and deal cards
28
Discussion: How does a Card get converted to a String?
System.out.println("Card "+c+": "+hand[p][c]);
Using the toString method from the Card class!
public String toString() {
if (value == 0)
return "Joker";
else
return cardNames[value]+" of "+suit;
}
enum Suit {Hearts, Diamonds, Clubs, Spades};
private final static String[] cardNames =
{"Joker","Ace", "Two", "Three","Four","Five", "Six",
"Seven","Eight","Nine","Ten", "Jack","Queen","King"};
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 28
Problem 2: Method to return the matrix product A*B.
29
public static int[][] matrixMultiply(int[][] A, int [][] B) {
int aRows = A.length;
int aCols = A[0].length;
int bRows = B.length;
int bCols = B[0].length;
int N
= A.length; // Assume A and B are both NxN
if (aCols != bRows)
throw new IllegalArgumentException(
"A Columns: " + aCols + " did not match number of B Rows " + bRows);
int[][] C = new int[aRows][bCols];
for (int i = 0; i < aRows; i++)
// A Row
for (int j = 0; j < bCols; j++)
// B Column
for (int k = 0; k < aCols; k++) // A Column
C[i][j] += A[i][k] * B[k][j];
return C;
}
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 29
And the Winner for best TicTacToe GUI is…
30
Curtis Babnik
Human vs Smarter: http://www.youtube.com/watch?v=nZyvR0v3ixs
Human vs Learns : http://www.youtube.com/watch?v=t87UFMKbegE
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 30
TicTacToe UML
31
A UML Diagram using a Eclipse UML Plugin:
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 31
References:
32
1.
J. Lewis, P. DePasquale, and J. Chase., Java Foundations: Introduction to
Program Design & Data Structures. Addison-Wesley, Boston, Massachusetts,
3rd edition, 2014, ISBN 978-0-13-337046-1
Scott Kristjanson – CMPT 125/126 – SFU
Slides based on Java Foundations 3rd Edition, Lewis/DePasquale/Chase
Wk14.1 Slide 32