Lists and Trees
> Click or hit Control-Enter to run Example.main above
Linked Lists: Iteration
public class LinkedList {
private Item start;
}
public class Item {
public int value;
public Item next;
}We can iterate through our LinkedList using a for loop.
-
Start at
start -
Update by
current = current.next -
Stop when
current == null
> Click or hit Control-Enter to run Example.main above
But How Do We Insert?
LinkedList Insertion Algorithm
-
Find the right spot.
-
Set the reference on the preceding item to point to the new item.
-
Set the reference on the new item to point to the former next item.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
But wait, now we can’t change the preceding reference.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
Singly Linked Lists
public class Item {
public int value;
public Item next;
Item(int setValue, Item setNext, setPrevious) {
this.value = setValue;
this.next = setNext;
}
}
public class LinkedList {
private Item start;
}What we’ve been discussing is known as a singly linked list.
Doubly Linked Lists
public class Item {
public int value;
public Item next;
public Item previous;
}
public class DoublyLinkedList {
private Item start;
private Item end;
}You can also have both forward and backward links. This is known an a doubly linked list.
Doubly Linked Lists
public class Item {
public int value;
public Item next;
public Item previous;
}
public class DoublyLinkedList {
private Item start;
private Item end;
}Time v. Space
public class ArrayList {
private int[] data;
}
public class Item {
public int value;
public Item next;
public Item previous;
}
public class DoublyLinkedList {
private Item start;
private Item end;
}ArrayList v. LinkedList also represents a time v. space tradeoff.
-
LinkedListis faster for certain operations… -
but consumes more space to store the same amount of information.
Time v. Space
public class ArrayList {
private int[] data;
}
public class Item {
public int value;
public Item next;
public Item previous;
}
public class DoublyLinkedList {
private Item start;
private Item end;
}To store n ints:
-
ArrayList: nvalues -
LinkedList: 3n (1value, 1next, 1previous)
Questions About Lists?
Trees
In computer science, a tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.
Trees: Parent and Child
Each parent has one or more children.
Trees: Parent and Child
Each parent has one or more children. Each child has one parent.
Trees: Root and Leaves
We refer to the top of the tree as the root.
Trees: Root and Leaves
We refer to the top of the tree as the root. We refer to nodes without any children as leaves.
Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
The depth or height of a tree is the maximum distance from root to leaf.
What Are Trees For?
What kinds of data can we represent using trees?
-
The Java class hierarchy 1
-
Files on your computer
-
Domain names on the internet
-
Any data that has a hierarchical structure.
Java Class Hierarchy
public class Pet { }
public class Dog extends Pet { }
public class Cat extends Pet { }
public class OldDog extends Dog { }Your Computer’s Files
$ cd / && ls -l
System
Library
Users
$ cd Users && ls -l
challen
Shared
$ cd challen && ls -l
classes
wwwDomain Name Translation
Binary Trees
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
public class Tree {
Object value;
Tree right;
Tree left;
}We are rarely interested in trees only for their structure. Usually we use them to structure data.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Today is the Drop Deadline
I would much rather you drop than fail.
Announcements
-
MP4 is due today at 5PM.
-
We’ve added an anonymous feedback form to the course website. Use it to give us feedback!
-
Strike is over! (I think.) Three cheers for the fantastic CS 125 course staff.
-
My office hours continue today at 11AM in the lounge outside of Siebel 0226.