Lecture 15: Linked Structures
"The name of the song is called 'Haddocks' Eyes.' " "Oh, that's the name of the song, is it?" Alice said, trying to feel interested. "No, you don't understand," the Knight said, looking a little vexed. "That's what the name is called. The name really is 'The Aged Aged Man.' " "Then I ought to have said 'That's what the song is called' ?" Alice corrected herself. "No, you oughtn't: that's quite another thing! The song is called 'Ways and Means,' but that is only what it's called, you know!" "Well, what is the song, then?" said Alice, who was by this time completely bewildered. Lewis Caroll Through the Looking Glass "I was coming to that," the Knight said. "The song really is 'A-sitting On A Gate,' and the tune's my own invention."
Linked vs. Sequential Allocation
Goal: process a collection of objects. Sequential allocation: put object one after another. TOY: consecutive memory cells. Java: array of objects.
! !
Linked allocation: include in each object a link to the next one. TOY: link is memory address of next object. Java: link is reference to next object.
! !
Key distinctions. Sequential allocation: random access, fixed size. Linked allocation: sequential access, variable size.
! !
COS126: General Computer Sci ence
http://w w w .cs.Pri nceton.EDU/~cos126
Linked Lists
Linked list of strings. A recursive data structure. A string plus a pointer to another linked list (or empty list). Unwind recursion: linked list is a sequence of strings.
! ! !
Linked List Demo
addr
value "Alice" null 0 "Carol" C9 0 0 0 0 "Bob" C0 0
Linked lists in Java. Easy to define as a Java class. A reference to a String. A reference to another List. Use special value null to terminate list.
! ! ! !
public class List { private String name; private List next; }
List a a.name a.next List b b.name b.next List c c.name c.next
= = = = = = = = =
new List(); "Alice"; null; new List(); "Bob"; a; new List(); "Carol"; b;
a List C0
C0 C1 C2 C3
b List C9
C4 C5 C6
c List C3
C7 C8 C9
List x Carol Bob Alice
null
c Carol
3
b Bob
a Alice
null registers
CA CB
main memory
4
Traversing a List
Paradigm for traversing a null-terminated linked list.
Stack and Queue ADTs
Fundamental data type. Set of operations (add, remove, test if empty) on generic data. Intent is clear when we insert. Which object do we remove?
! ! !
for (List x = c; x != null; x = x.next) { System.out.println(x.name); }
Stack. Remove the object most recently added. ("last in first out") Analogy: cafeteria trays, surfing Web.
! !
Queue. Remove the object least recently added. ("first in first out") Analogy: Registrar's line.
! !
x Carol Bob Alice
null
% java List
Multiset. Remove any object. Law professor calls on arbitrary student.
! !
12
Queue
Queue operations. enqeuue Insert a new object onto queue. dequeue Delete and return the object least recently added. isEmpty Is the queue empty?
! ! !
More Applications of Queues
Real world applications. iTunes playlist. Echo filter to store last ten waves. Dispensing requests on a shared resource (printer, processor). Asynchronous data transfer (file IO, pipes, sockets). Data buffers (iPod, TiVo). Graph processing (stay tuned).
! ! ! ! ! !
public static void main(String[] args) { Queue q = new Queue(); q.enqueue("Vertigo"); q.enqueue("Just Lose It"); q.enqueue("Pieces of Me"); q.enqueue("Pieces of Me"); System.out.println(q.dequeue()); q.enqueue("Drop It Like It's Hot"); while(!q.isEmpty()) System.out.println(q.dequeue()); }
A simple queue client
13
Simulations of the real world. Traffic analysis of Lincoln tunnel. Waiting times of customers in McDonalds . Determining number of cashiers to have at a supermarket.
! ! !
14
Queue: Linked List Implementation
Linked list implementation. Maintain linked list of elements. Let first be reference to first node on list. Let last be reference last node on list.
! ! !
Queue: Linked List Implementation
Linked list implementation. Maintain linked list of elements. Let first be reference to first node on list. Let last be reference last node on list.
! ! !
Insert.
first last first last x
now
is
the
time
now
is
the
time
List x = new List(); x.item = "for"; last.next = x; last = x;
15 16
Queue: Linked List Implementation
Linked list implementation. Maintain linked list of elements. Let first be reference to first node on list. Let last be reference last node on list.
! ! !
Queue: Linked List Implementation
Linked list implementation. Maintain linked list of elements. Let first be reference to first node on list. Let last be reference last node on list.
! ! !
Insert.
first last x
Insert.
first last x
now
is
the
time
for
now
is
the
time
for
List x = new List(); x.item = "for"; last.next = x; last = x;
17
List x = new List(); x.item = "for"; last.next = x; last = x;
18
Queue: Linked List Implementation
Linked list implementation. Maintain linked list of elements. Let first be reference to first node on list. Let last be reference last node on list.
! ! !
Queue: Linked List Implementation
Linked list implementation. Maintain linked list of elements. Let first be reference to first node on list. Let last be reference last node on list.
! ! !
Insert.
first last
Delete.
first last
now
is
the
time
for
now
is
the
time
for
List x = new List(); x.item = "for"; last.next = x; last = x;
19
val
now
String val = first.item; first = first.next; return val;
20
Queue: Linked List Implementation
Linked list implementation. Maintain linked list of elements. Let first be reference to first node on list. Let last be reference last node on list.
! ! !
Queue: Linked List Implementation
Linked list implementation. Maintain linked list of elements. Let first be reference to first node on list. Let last be reference last node on list.
! ! !
Delete.
first last
Delete.
first last
now
is
the
time
for
now
is
the
time
for
val
now
String val = first.item; first = first.next; return val;
val
now
String val = first.item; first = first.next; return val;
21
22
Queue: Linked List Implementation
public class Queue { private List first; private List last;
Binary Trees
Binary tree. Organize homogeneous collection of values (all same type). Associate two pointers with each value. Use pointers to access each branch of the tree.
! ! !
reference to first element in queue reference to last element in queue nested class
private class List { String item; List next; }
public boolean isEmpty() { return (first == null); } public void enqueue(String anItem) { List x = new List(); x.item = anItem; x.next = null; if (isEmpty()) { first = x; last = x; } else { last.next = x; last = x; } } public String dequeue() { String val = first.item; first = first.next; return val; } }
23
root Charles
Philip dad Andrew mom Alice
Elizabeth II
George VI
Elizabeth
delete first element George I Olga Louis Victoria George V Mary Claude Celia
24
Binary Tree: Java Implementation
Java implementation of a binary tree of strings is: A reference to the String. A reference to the left Tree. public class Tree { A reference to the right Tree.
! ! !
Parse Tree Demo
Tree a a.s a.left a.right Tree b b.s b.left b.right Tree c c.s c.left c.right Tree d d.s d.left d.right Tree e e.s e.left e.right
25
= = = = = = = = = = = = = = = = = = = =
new Tree(); "10"; null; null; new Tree(); "12"; null; null; new Tree(); "*"; a; b; new Tree(); "7"; null; null; new Tree(); "+"; c; d;
private String s; private Tree left; private Tree right;
10
12
null
null
null
null
null
null
26
Parse Tree Evaluation: Java Implementation
+
Preorder Traversal
How do we print out the information? Print string. Print left subtree recursively. Print right subtree recursively.
! ! !
Parse tree. Abstract representation of expression. Applications: compilers, computational linguistics.
! !
* + 8
Evaluating a parse tree. ((10 * 12) + (7)) = If string is an integer return it. Else, evaluate both subtrees recursively and return sum or product.
! !
10
12
127
No parentheses!
((4 + 5) + (6 * 7)) * 8 public class ParseTree { private String s; private ParseTree left; private ParseTree right;
represent data as a string, e.g., "+" or "1234" left subtree right subtree
public int eval() { if (s.equals("+")) return left.eval() + right.eval(); else if (s.equals("*")) return left.eval() * right.eval(); else return Integer.parseInt(s); } }
convert from string to integer
27
public String toString() { if (s.equals("+") || s.equals("*")) return s + " " + left + " " + right; else return s; } Preorder traversal: * + + 4 5 * 6 7 8
28
Parse Tree Construction
How do we read it back in and create the tree? Read string from standard input. If + or * operator, construct left and right subtrees recursively.
! !
Other Types of Trees
Other types of trees. Family tree. Parse tree. Unix file hierarchy.
! ! !
bin
lib
etc
constructor public ParseTree() { s = StdIn.readString(); if (s.equals("+") || s.equals("*")) { left = new ParseTree(); right = new ParseTree(); } }
aaclarke * files + 8 mandel stock
cs126
zrnye
grades
submit
% java ParseTree * + + 4 5 * 6 7 8 408
tsp
Point.java
TSP.java
tsp13509.txt
((4 + 5) + (6 * 7)) * 8
29 30
Other Types of Trees
Other types of trees. Family tree. Parse tree. Unix file hierarchy. Phylogeny tree.
! ! ! !
Other Types of Trees
Other types of trees. Family tree. Parse tree. Unix file hierarchy. Phylogeny tree. GUI containment hierarchy.
! ! ! ! !
Reference: http://java.sun.com/docs/books/tutori al/ui sw i ng/overvi ew /anatomy.html
31 32
Binary Search Tree
Other Types of Trees
Other types of trees. Family tree. Parse tree. Unix file hierarchy. Phylogeny tree. GUI containment hierarchy. Binary search trees. NCAA basketball tournament. Barnes-Hut tree for fast N-body simulation. ...
! ! ! ! ! ! ! ! !
33
35
Conclusions
Sequential allocation: supports indexing, fixed size. Linked allocation: variable size, supports sequential access. Linked structures are a central programming abstraction. Linked lists. Binary trees. Graphs. Sparse matrices. 'Haddocks' Eyes'
! ! ! !
Announcements
Thinking about majoring in Computer Science? Or doing the Certificate in Applications of Computing? Then: visit the all-new Life in the Computer Science Department: A Guide for the Humble Undergraduate: http://www.cs.princeton.edu/academics/ugradpgm/life.html a handy FAQ that answers many many questions
! !
'Ways and Means'
'The Aged Aged Man'
And/Or: Come talk to me AND CERTAINLY attend at least one of: C.S. open house for BSE freshmen Tuesday March 29, Friend Convocation Room, 5:45 (PM!): tours, demos, pizza (ABs welcome) C.S. open house for AB sophomores Tuesday April 5, C.S. Tea Room, 4 PM (but no pizza, and maybe fewer demos) (BSEs welcome)
! !
'A-sitting On A Gate'
Alice should have done this!
36 37
