Lab 3: Linked Lists
In Lab 2 and Project 2 you stored data in a 2D array: a fixed block of memory where any
location can be reached instantly with grid[row][col]. This week you will build
a very different structure, a singly-linked list, in which each item lives in
its own small object (a Node) and each Node knows only where the
next Node is.
You will work in a scaffolded LinkedList.java. Each task has methods marked
TODO, with comments, diagrams, and hints. After completing a task, run
LinkedListTester.java. The tester works in order, so it will help you focus on the
first task that still needs work. When you finish the lab, you will start Project 3, where your LinkedList will hold
every agent in an agent-based simulation, so it needs to be correct.
The chain of Nodes
A linked list stores only two things: a reference to the first Node (head) and a count (size).
head | v [ 4 | next ]--->[ 3 | next ]--->[ 2 | next ]--->[ 1 | null ] index 0 index 1 index 2 index 3 size = 4
There is no [ ] indexing. To reach index 3, you must start at head
and follow next three times. That one fact explains the cost (in terms of Big-O) of almost every method
you will write.
Keep asking yourself two questions: Which Node is my reference pointing at right now? and
After this change, is every Node still reachable from head? Draw boxes and
arrows on paper before you write a line of code.
java.util.Iterator, which is already imported for you.
Setup
In your personal Google Drive Projects folder, create a new folder named Project3. Download both files into it. Do not rename them.
Testing Your Own Code with main()
LinkedListTester.java checks your work, but you should also test your methods yourself.
The main() method at the bottom of LinkedList.java is your testing space.
For example, once Task 2 is written:
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(1);
list.add(2);
list.add(3);
System.out.println(list + " size = " + list.size()); // predict this first!
}
Compile and run LinkedList.java directly:
javac LinkedList.java java LinkedList
Experiment Before Running the Tester
Do not use the tester as your first way of finding out whether your method works.
Before running the tester, call your method from main(). Try an empty list, a list
with one item, and a list with several items. Try the first position, a middle position, and the
last position. Those are exactly the cases where linked-list code breaks.
When you are convinced that your method is working properly, then run the tester.
Run the Tester
Compile LinkedList.java and LinkedListTester.java together, then run the tester:
javac LinkedList.java LinkedListTester.java java LinkedListTester // runs Task 1, 2, 3, ... and stops at the first task that needs work java LinkedListTester 4 // runs only Task 4
You do not need the -ea flag, and the tester will not crash. For every check it
prints [PASS] or [FAIL]; a failure shows what was expected, what your code
produced, and a hint. If your code throws an exception, you will see [CRASH] with the
method and line number where it happened. If your code gets stuck in an infinite loop, you will see
[TIMEOUT].
------------------------------------------------------------
Task 3 - get(int index)
------------------------------------------------------------
[PASS] get(0) on the list [0, 1, 2, 3, 4] -> 0
[FAIL] get(1) on the list [0, 1, 2, 3, 4]
expected: 1
got: 2
hint: To reach index 1, step forward from head one time.
main() → predict and inspect the results → run LinkedListTester.
Core Lab Tasks
Lab 3 has nine tasks. The lab checkpoint comes after Task 6: show the tester output to a TA or instructor, then keep going. Tasks 7–9 complete the list you will need for Project 3.
Task 1 — The Node class, the constructor, size(), isEmpty()
BUILD — create the container and an empty list.
Node is a private class written inside LinkedList. Code
outside the list never sees Nodes, only the items stored in them. Because Node is inside
LinkedList<T>, it can use the type T.
- Add a field of type
TtoNodeto hold its item. Node(T item)stores the item and setsnexttonull.getData(),setNext(Node n), andgetNext()read and change the fields.LinkedList()creates an empty list: no head Node, zero items.size()returns the number of items;isEmpty()returns whether there are none.
<T> in public class LinkedList<T> is a
placeholder for a type. new LinkedList<Integer>() makes a list of Integers;
new LinkedList<Agent>() will make a list of Agents in Project 3. You write the code
once, and it works for any type.
Task 2 — add(T item) and toString()
MODIFY THE HEAD — insert at the front.
before: head --> [B] --> [C] --> null add(A): head --> [A] --> [B] --> [C] --> null
Make a new Node, point it at the current head, then move head to the new Node.
Ask yourself: what happens if you do those two steps in the opposite order? And:
does it still work when the list is empty?
toString() walks from head to the end and returns the items in exactly this format:
empty list "[]" one item "[7]" several items "[4, 3, 2, 1, 0]"
This is your first traversal: start a current reference at head
and move it with current = current.getNext() until it becomes null.
Task 3 — get(int index)
TRAVERSE — walk to a position.
list: [0, 1, 2, 3, 4] get(0) → 0 get(3) → 3 get(4) → 4
To reach position index, start at head and step forward index times.
Use a separate current reference to walk; never move head just to look
at the list. You may assume 0 <= index < size().
Task 4 — add(int index, T item)
MODIFY THE MIDDLE — splice a new Node into the chain.
list: [A, C] add(1, B) → [A, B, C]
head --> [A] --> [C] --> null
^
the Node BEFORE the insertion point (position index - 1)
step 1: newNode.setNext(before.getNext()); [B] --> [C]
step 2: before.setNext(newNode); [A] --> [B] --> [C]
Index 0 is a special case: which method you already wrote inserts at the front? Index
size() is allowed and means “at the end.” Don't forget size.
Before coding: draw what happens if you do step 2 before step 1.
Task 5 — contains(Object o)
SEARCH — traverse and compare.
Return true if some item in the list satisfies item.equals(o).
== versus .equals(): With objects, == asks
“are these the very same object in memory?” and .equals() asks
“do these represent the same value?” The tester checks with two different
String objects that hold the same letters, so == will not pass.
Task 6 — remove() and clear()
MODIFY THE HEAD — remove from the front, and reset.
list: [0, 1, 2] remove() returns 0 list becomes [1, 2]
remove()removes the first item and returns it. If the list is empty, returnnull.clear()empties the list. You do not need a loop: what do the fields of an empty list look like?
After removing the last item, the list must still be usable: add() should work again.
Lab checkpoint
When the tester prints LAB CHECKPOINT REACHED! after Task 6, call a TA or instructor over and show them the output. Then please stay and keep going — Tasks 7–9 are needed for Project 3.
Finishing the List
Task 7 — remove(int index)
MODIFY THE MIDDLE — unlink a Node from the chain.
list: [A, B, C] remove(1) returns B → [A, C]
head --> [A] --> [B] --> [C] --> null
^
before
before.setNext(before.getNext().getNext()); [A] --------> [C]
Like add(index, item), you need the Node before the one you are removing.
Save the removed Node's item before you unlink it. Test removing the first, a middle, and the
last item.
Task 8 — equals(Object o)
COMPARE — walk two lists side by side.
Return true if o is a LinkedList containing equal items in the
same order. The parameter is an Object because this method overrides the
equals method that every Java object inherits. Start by checking the type:
if (!(o instanceof LinkedList)) {
return false;
}
// If I have reached this line, o must be a LinkedList
LinkedList<?> other = (LinkedList<?>) o;
Then compare sizes, and compare the items one pair at a time. equals must not change
either list.
Task 9 — The Iterator
ITERATE — let other code walk your list with a for-each loop.
Look at the class header in the scaffold:
public class LinkedList<T> implements Iterable<T>
implements Iterable<T> is a promise that the class has a method
iterator(). Keeping that promise is what makes this possible:
for (Integer value : list) {
System.out.println(value);
}
Complete the private class LLIterator implements Iterator<T> inside LinkedList:
- One field of type
Node: the Node whose item will be returned by the next call tonext(). LLIterator(Node head)starts that field at the given head.hasNext()returnstrueif that Node is notnull.next()returns that Node's item and moves the field forward one Node.remove()does nothing (it is optional for an Iterator).
Finally, complete iterator() in the LinkedList class (not in LLIterator):
// Return a new LLIterator pointing to the head of the list
public Iterator<T> iterator() {
return new LLIterator(this.head);
}
get(i) for every i walks
from the head again on every call, so visiting all n items costs about
n2/2 steps. An iterator remembers where it is, so a for-each loop costs only
n steps. In Project 3 you will loop over hundreds of agents thousands of times — this
difference will be very noticeable.
Lab 3 complete
When the tester reports all nine tasks complete, you have a working generic linked list: you have
practiced traversal, insertion and removal at the head, middle, and end, searching with
.equals(), overriding equals, and implementing an Iterator.
Notice that the bottom of LinkedList.java contains two more methods marked
Project 3. Leave them for now; they are the first task of the project.
Submission
Before the end of the lab period, make sure your completed LinkedList.java is in your
personal Google Drive folder Projects/Project3.
Your Project 3 folder should begin like this
Projects/
└── Project3/
├── LinkedList.java
└── LinkedListTester.java
Your LinkedList.java must be in this folder for grading, and Project 3 depends on it.
Add the Project 3 files to this same Project3 folder.
Ready for Project 3?
Return to the CS231 course page, navigate to the Projects page, and open Project 3: Agent-Based Simulation, or go directly to the project.