"If you think that we're all done with the List interface, then you're mistaken. We're just getting started. Let me tell you about the LinkedList and ArrayList collections."

"I'll start with the ArrayList collection."

"Here is how this collection's inheritance diagram looks:"

"Interfaces are green."

"Abstract classes are purple."

"Ordinary classes are red."

"Solid lines represent inheritance, and dashed lines represent interface implementations."

"This is the simplest collection. Inside an ArrayList, elements are stored in a simple array."

"This collection's primary advantage over an array is its ability to expand, i.e. its ability to increase its length as needed."

"If the array runs out of space, then a second larger array is created and all of the elements from the first array are copied to it. Then the second array takes the place of the first, and the first is discarded (it will be destroyed by the garbage collector)."

"How much larger does the array get?"

"The new array's length is calculated as (3*n)/2+1, where n is the old array's length. In other words, if the old array was 100 elements long, then the new one will be 300/2+1 = 151."

"When adding an element to the middle of an ArrayList, all elements to the right of where the new element will be inserted are copied 1 position to the right, and then the new element is added to the empty cell."

"When removing an element from the middle, all elements to the right of that element are copied 1 position to the left."

"Are you saying that the ArrayList makes itself longer when you add elements to it, and that it makes itself shorter when you remove elements?"

"No, the array inside of an ArrayList never makes itself shorter by itself; however, you can force an ArrayList to shrink its internal array to the smallest possible size by calling the trimToSize() method."

"And, of course, I'll tell you about LinkedList."

"Here's what its inheritance diagram looks like:"

"Interfaces are green."

"Abstract classes are purple."

"Ordinary classes are red."

"Solid lines represent inheritance, and dashed lines represent interface implementations."

"As you already know, LinkedList stores elements as a linked list."

"I hear that all of the time, but could you tell me what it is?"

"Sure. "It's simple."

"A linked list consists of elements that a) store data and b) store references to the next and previous elements."

"This is how the class for such an element would look if it stored Strings:"

Example Description
class LinkedListElement
String data;
LinkedListElement next;
LinkedListElement previous;
The data field stores the element's String value.
The next field stores a reference to the next element in the list.
The previous field stores a reference to the previous element in the list.

"And if we use a generic type declaration, then it would look something like this:"

A class for a linked list element with a generic type declaration
class LinkedListElement<T>
 T data;
 LinkedListElement<T> next;
 LinkedListElement<T> previous;

"Makes sense."

"To understand it better, let's write code where we add 10 elements to a doubly-linked list:"

public static void main(String[] args)
 LinkedListElement<Integer> tail; // The tail (very last element) of the list

 for(int i = 0; i < 10; i++)
  LinkedListElement<Integer> element = new LinkedListElement<Integer>();
  element.data = i;

  if (tail == null) // If the tail doesn't exist, then make our element the last element
   tail = element;
  else // if there is a tail, add the element
   tail.next = element; // Set the next field on the tail element
   element.previous = tail; // Add a reference to the tail to the new element
   tail = element; // Make the new element the tail

"Imagine that we have 10 elements in the list. Here's how to insert an element into the middle:"

Implementations of the List interface - 3

"The links that have changed are highlighted bright red. They now point to the new element."

"New links are highlighted bright purple. They are the new element's links to its neighbors."

"And now as code:"

Insert an element into the middle of a linked list
// This field stores the element that is the head of the list
LinkedListElement<Integer> head = …

// Get the 4th element (counting from zero)
LinkedListElement<Integer> element4 = head.next.next.next.next;
// Get the 5th element
LinkedListElement<Integer> element5 = element4.next;

// Create the new element that we will insert
LinkedListElement<Integer> newElement = new LinkedListElement<Integer>();
newElement.data = -18;

// Replace the references in the element on the left
newElement.previous = element4;
element4.next = newElement;

// Replace the references in the element on the right
newElement.next = element5;
element5.previous = newElement;

"Thank you, Ellie. I definitely learned a lot of new things about lists."