Linked Lists
LEARNING OBJECTIVES
After this lesson, you will be able to:
- Explain the benefits of Lists over Arrays
- Explain how LinkedLists work
- Explain the difference between a LinkedList and an ArrayList
STUDENT PRE-WORK
Before this lesson, you should already be able to:
- Implement Arrays, ArrayLists, and LinkedLists
INSTRUCTOR PREP
Before this lesson, instructors will need to:
- Open/run the starter and solution code and adapt as needed
- Create a gist to share the code needed for the independent practice and be sure to remove the answers to the discussion questions within the code
Opening (5 mins)
Arrays and Lists have been used throughout the course, but it is important that we have a solid understanding of all of the advantages and disadvantages of each, since they play a crucial role in programming, as well as interview questions.
Introduction: Shortcomings of Arrays (10 mins)
Arrays are very useful for creating collections of objects or primitives. Arrays can be built and accessed very quickly, and every element is indexed for your convenience, making them a great way to organize data.
Check: Have the students take 2 minutes to discuss at their tables any limitations or disadvantages of arrays.
Arrays are great if you know exactly how much data you need to organize. In Java, the size of an array is fixed once it has been created.
Check: Show the code below to the students, and ask students to talk with the person next to them about what error it would cause (IndexOutOfBoundsException).
private int[] myIntArray = new int[3];
int[0] = 12;
int[1] = 13;
int[2] = 14;
int[3] = 15;
//or...
private int[] myOtherIntArray = new int[]{12, 13, 14};
int[3] = 15;
Both attempts to insert the number 15 will cause an IndexOutOfBoundsException. This is because both arrays are fixed at length 3. In order to add the number 15, you must either replace one of the other elements, or create a whole new array. To create a collection of objects that can be added to without needing to re-copy itself continuously, we can use a LinkedList.
Check: Have the students take 1 minute to come up with examples where an array would be the best choice to hold data. Ask student groups to share out.
Introduction: Linked Lists (15 mins)
The simplest form of the linked list is the singly linked list. In this data structure, each element knows about only 2 objects: itself, and the next in the list.
Check: Ask the students if they remember the differences between an ArrayList and a LinkedList
The simplest form of the LinkedList is the singly LinkedList. In this data structure, each element knows about only two objects: itself and the next object in the list.
Typically, LinkedLists are thought of to contain Nodes. A basic Node class for a linked list looks like this:
public class Node {
Node next;
Object data;
public Node(Object data) {
this(data, null);
}
public Node(Object data, Node next) {
this.next = next;
this.data = data;
}
public Object getData() {
return this.data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return this.next;
}
public void setNext(Node nextNode) {
this.next = nextNode;
}
}
As you can see, a Node object contains a reference to another Node called Next. This is the next Node in the LinkedList. The last element in the LinkedList always has a Next pointing to null. If a Node is added onto the end, the previous last Node's Next now points to the new Node. The new Node's Next is now null.
But how is a Node actually used in the LinkedList?
public class LinkedList {
private Node head;
private int size;
}
Check: Ask the students to explain to each other what would happen if you remove an element from the LinkedList at 1. the head 2. the middle 3. the tail
Demo: Utilizing java.util.LinkedList (15 mins)
For a quick example of how to use the standard Java Linked List, consider the following:
public static void main(String[] args) {
List<Integer> intList = new LinkedList<>();
intList.add(12);
intList.add(13);
intList.add(14);
intList.add(15);
for(int i = 0; i < intList.size(); i++) {
System.out.println("For Loop: " + intList.get(i));
}
intList.add(1, 20);
//A linked list has its own Iterator, which it uses to traverse
//through the nodes. `it.hasNext()` will return `true` until it
//reaches the last Node. Once `Node.next()` returns `null`, the
//while loop exits.
ListIterator<Integer> it = intList.listIterator(0);
while(it.hasNext()) {
System.out.println("From Iterator: " + it.next());
}
intList.remove(0);
//Newer versions of Java allow you to use `foreach`
//loops, which basically simplify the iterator code
//into a single statement.
for(Integer myInt : intList) {
System.out.println("For Each: " + myInt);
}
}
Notice how the LinkedList can be read using a standard for loop. While it may look like a LinkedList is indexed (like an array), it is actually iterated using its size (remember the small LinkedList implementation above). That means that, unlike an array, you cannot go directly to a specified element. Instead, you must iterate through the list until you reach the desired location. This may not seem like a lot of effort, but it is something to consider if you start working with large amounts of data. So how do we have a collection of undetermined size that is also indexed? For that, we use an ArrayList.
Check: Ask the students to take a minute and come up with an example where we would use a LinkedList (1 mins). Have students share out.
Introduction: Array Lists (10 mins)
Let's look at the above code again, but this time using an Array List. As the name implies, ArrayLists are Lists backed by an array data collection.
public static void main(String[] args) {
List<Integer> intList = new ArrayList<>();
intList.add(12);
intList.add(13);
intList.add(14);
intList.add(15);
for(int i = 0; i < intList.size(); i++) {
System.out.println("For Loop: " + intList.get(i));
}
intList.add(1, 20);
ListIterator<Integer> it = intList.listIterator(0);
while(it.hasNext()) {
System.out.println("From Iterator: " + it.next());
}
intList.remove(0);
for(Integer myInt : intList) {
System.out.println("For Each: " + myInt);
}
}
Both blocks of code are valid, and both use the same method names. That is because both java.util.LinkedList and java.util.ArrayList implement the List interface. That means they appear to behave exactly the same to an outside class. Internally, however, they behave very differently.
An ArrayList is actually backed by an array of finite size. If the array becomes full, it then copies itself into a larger array. As the array grows larger, the cost of this copying also grows. The array is usually expanded by a factor of itself, so it grows by a larger amount each time to avoid doing extra copy operations. Essentially, it trades memory for speed, as the backer array allows for each element to be indexed.
Check: Ask the students to come up with an example where we would use an ArrayList (1 min). Have students share out.
Independent Practice Practice: LinkedList vs ArrayList (20 mins)
In groups, look over this code. With your group, discuss each question found within in the code around strengths and weaknesses of LinkedLists and ArrayLists.
Instructor Note: Share this code with students (potentially as a gist, but be sure to strip out the answers under each discussion question.)
public static void main(String[] args) {
List<Integer> linkedList = new LinkedList<>();
linkedList.add(12);
linkedList.add(13);
linkedList.add(14);
linkedList.add(15);
List<Integer> arrayList = new ArrayList<>();
arrayList.add(12);
arrayList.add(13);
arrayList.add(14);
arrayList.add(15);
// Discuss what operation has the possibility to be slower and why.
linkedList.add(20);
arrayList.add(20);
//Both lists will contain the exact same values.
//However, if the arrayList had a capacity of
//only 4, it had to create a new array of size
//5 or greater and copy the elements over. The
//linkedList, on the other hand, simply had to
//create a new pointer from the element containing
//the number 15 to the number 20.
// Discuss what operation is slower and why.
int listInt = linkedList.get(4);
int arrayInt = arrayList.get(4);
//In this example, listInt == arrayInt == 20. However, in
//order to get listInt, we had to iterate past the
//first 4 elements to reach the 4th. In the arrayList,
//we were able to go directly to the 5th index of the
//array.
// Discuss which of these operations is slower and why
linkedList.remove(3);
arrayList.remove(3);
//In order to remove the item at index 3 (the 4th element)
//in the linked list, we have to iterate until we reach
//the proper location. However, after that, all that needs
//to be done is point the Node.next() value to the next index
//in the list (20 in this list). In the array list, we have to
//move each item after index 3 (15) back one place. In this
//example, that requires moving only one integer. But in
//larger collections, this may become more intensive.
}
Check: Discuss the answers with the class during the last 5 minutes of the activity.
Conclusion (5 mins)
The Linked List is a very useful data structure. It allows for unlimited operations to be done on a single collection. However, no data structure is always the correct choice. Sometimes an array is best; other times it is a LinkedList. Sometimes, it is a combination of both, calling for an ArrayList. Always consider how you will be using your data when choosing the data structure to hold it.