Java程序辅导

Monday 3/7
Announcements:
 Lab 3 due Today
 Quiz 2 Wednesday, 3/9 (Sections 2.1-2.4     not 2.5 - SLL)
 Homework 5 and Lab 4 are posted
For Next Time
 Study for Quiz 2
 Do the Lab 4 Before Lab
 Read Section 2.6 (Double-Linked List)
Today
 Single-Linked List  (In-class Exercise) (15 Minutes)
 Double-Linked List
 Lab 4 Before Lab (15 Minutes)
Single-Linked List Examples
When writing code assume that the class Node is available.
1. Draw a memory diagram of a single-linked list that contains: 
“Barb” “Mary” “Liz” “Janet”
 With reference head pointing to the Node that contains 
String “Barb”
2. Write code to Add “Ronnie” to the front of the list
3. Write code to print all the elements in the list
4. Write code to add “Christine” to the end of the list
5. Remove the element at index 2
6. Remove the last element
“Barb”  |    “Mary”  |   head “Janet”  | null “Liz”  |   
15 minutes:
In-class Exercise Practice Single-Linked List
 Start Eclipse 
 Create Java Project PracticeSLL
 Download the file SLLPractice.java and put it 
into the source folder
Running Time:  Big-O 
List with n elements:  KWArrayList SingleLinkedList
• get(index)
• set(index, elem)
• size()
• add(elem)
• add(index, elem)
• remove(index)
• remove(elem)
• contains(elem)
• indexOf(elem)
• lastIndexOf(elem)
Single-Linked Lists
 Limitations of a Single-Linked List include:
We can traverse the list only in the forward 
direction
Removing and inserting a node requires a 
reference to the previous node
Insertion at the front is O(1); insertion at middle 
and beyond is O(n)
 We can overcome these limitations:
Add a reference in each node to the previous 
node, creating a double-linked list
lastIndexOf(item),   add(item)
Double Linked List
 Basic Building Block
Node
• Fields
• Constructor
null “Tom” “Dick” “Harry” “Sam” null
Node Class
private static class Node {
private E data;
private Node next = null;
private Node prev = null;
private Node(E dataItem) {
data = dataItem;
}
}
Insert Sharon Before Sam
next =
= prev
data = "Harry"
Node
next = null
= prev
data = "Sam"
Node
next =
= prev
data = "Sharon"
Node
Node sharon = new Node("Sharon");
sharon.next = sam; 
sharon.prev = sam.prev;
sam.prev.next = sharon;
sam.prev = sharon
from predecessor
to predecessor
sam
sharon
Remove Harry
next =
= prev
data = "Dick"
Node
next =
= prev
data = "Harry"
Node
next =
= prev
data = "Sharon"
Node
harry
harry.prev.next = harry.next
harry.next.prev = harry.prev
A Double-Linked List Class
 Like the single-linked class,
the Node class is a nested
class inside Double LinkedList
 What fields does Double LinkedList have?
 A double-linked list object has data fields:
head (a reference to the first list Node)
tail (a reference to the last list Node)
size 
 Insertion and deletion at either end is O(1); 
insertion/deletion in the middle is still O(n)
The LinkedList Class
There is also a removeFirst() and a removeLast()
Lab 4
 Questions about Lab 4
 Before Lab
Carefully read the lab, KWArrayList.java, and section 2.4 
Using eclipse create a Lab4 java project.
 Import  KWArrayList.java into your java project.
• Look over this code (really)
Create a TestWithMain.java 
Create a JUnit class and a JUnit test for the clear() method.   
It is OK if your JUnit test fails. In fact, I would expect it to 
fail.
Use a text editor or pencil and paper to describe object 
myList …