Project 2: Linked Lists

(Return to homepage)

In Project 2, you'll implement a Doubly Linked List, a list-like data structure that enables iteration in both forward and reverse directions.

The Doubly Linked List is just like the (Singly) Linked List, with a slight addition. The internal nodes inside the Doubly Linked List not only point forward to the next node like a Linked List, but also point backward to the previous node in the list. This enables clients of the Doubly Linked List to iterate in both directions. Furthermore, a node can be inserted and removed from the list-like with just a reference to the node itself, rather than the complete list, as a node can re-link both of its neighbors.

Your task is to implement a complete Doubly Linked List that provides an interface supporting operations like insertion, deletion, and iteration in both directions. This project not only involves extensive use of references to track and organize internal data nodes, but also offers several practical examples on how a data structure's performance (Big O) can vary based on a client's needs (i.e. insertion vs. iteration). For those two reasons, Linked Lists are commonly featured in technical interviews to evaluate a candidate's understanding of references, runtime, and the trade-offs between ways data can be organized.

Ready? It's interview day. Get the Project 2 starter code here! (jUnit dependencies included)

The project code should work out-of-the-box for IntelliJ (running and debugging), but if you're having trouble getting it working, try these IntelliJ setup instructions.

Classes

linkedlist.LinkedList<T>: A generic, concrete Doubly Linked List class. Implements Iterable.

• ListNode<T>: An internal concrete class that contains the state of a single node in the Linked List. Contains a generic payload value, and references to the next and previous nodes in the list.
  
  
• LinkedList(): Default Linked List constructor. Constructs an empty list with no values.
• LinkedList(Iterable<? extends T>): Iterates over elements of the Iterable argument to construct a list containing the same elements supplied by the Iterable, in the same order as iteration.
• T peekFront(): Returns the front element value of the list and null if no such element exists.
• T peekBack(): Returns the back element value of the list and null if no such element exists.
• T popFront(): Removes and returns the front element value of the list and throws NoSuchElementException() if no such element exists.
• T popBack(): Removes and returns the back element value of the list and throws NoSuchElementException() if no such element exists.
• void pushBack(T): Appends a new element to the back of the list containing the argument value.
• void pushFront(T): Appends a new element to the front of the list containing the argument value.
• void add(T): Same as pushFront(T).
• void add(int, T): Inserts an element with the argument value at the specified index, shifting the existing element and all successive elements at the given index forwards. If the index is less than zero or exceeds the size of the list, throws IndexOutOfBoundsException().
• T remove(): Same as popFront().
• T remove(int): Removes and returns an element at the specified index, shifting all successive elements backwards (in effect, the opposite of add(index, T)). If the index is less than zero or exceeds the size of the list, throws IndexOutOfBoundsException().
• int size(): Returns the size of the list.
  
  
• iterator<T>: Returns a new LinkedListIterator.
• LinkedListIterator: An Iterator that enables iteration over the Linked List instance. Implements hasNext(), next(), and remove(). See official Java Iterator documentation for details.
  
  
• reverseIterator<T>: Returns a new LinkedListReverseIterator.
• LinkedListReverseIterator: An Iterator that enables iteration over the Linked List instance, but in reverse order. Implements hasNext(), next(), and remove(). See official Java Iterator documentation for details.

Bonus Classes

This project features two additional classes that you may optionally implement for up to +15 bonus points. You are eligible to earn bonus points even if your Linked List implementation is not fully complete. These classes are the Stack and Queue, which are natural clients of the Linked List that can take advantage of O(1) append and remove. By implementing both, you will explore the differences between containment and extension, two different strategies of re-using a base class's behavior.

• Stack: A generic, concrete class describing a stack of items. A stack is a last-in-first-out (LIFO) queue. Elements are "pushed" onto the top and "popped" from the top in reverse order or their addition, much like a stack of dinner plates in real life.
  
  Stack should contain a LinkedList as a private variable, leveraging its public interface to support all Stack operations and store elements. Stack will provide the following public methods:
  • void push(T): Pushes an element onto the top of the stack.
  • T pop(): Removes and returns the element from the top of the stack.
  • T peek(T): Returns (but does not remove) the element from the top of the stack.
  • int size(): Returns the size of the stack.
• Queue: A generic, concrete class describing a queue of items. A stack is a first-in-first-out (FIFO) queue. Elements are "pushed" onto the queue and "popped" in the same order of addition, much like a queue of people in real life.
  
  Queue should extend LinkedList. as a private variable, leveraging its inherited methods to support all Queue operations and store elements. Queue will provide the following public methods:
  • void add(T): Pushes an element to the back of the queue.
  • T remove(): Removes and returns the element from the front of the queue.
  • T peek(T): Returns (but does not remove) the element from the front of the queue.
  • int size(): Returns the size of the queue.
  Unlike Stack, Queue may not reveal methods that modify its internal state and disrupt the expected behavior of the queue. Any methods, inherited or otherwise, that allow the queue to become inconsistent, should throw a RuntimeException().

Running Your Code

As with the previous projects, this project contains a full test suite (see the test package) that will evaluate your code.

A run script for the entire project test suite is included as run.bat (Windows) or run.sh (Mac/Linux). This will compile your entire project and produce a run report with your estimated grade, including bonus points. Your entire project must compile for the script to work, and your entire project must compile to receive a grade after submission.

You are welcome to modify the tests for debugging purposes, though keep in mind your project will be graded using an unmodified copy of the test suite.

Submission Instructions

See the submissions page for details. Have questions or need help? Post on Piazza!

Critical Analysis Questions

These questions aren't graded, but are similar to those you may see on an exam. You are welcome to discuss these with classmates offline on on Piazza.

• How would you reverse a singly linked list?
• How would you reverse a doubly linked list?
• Why are both Linked List append and remove considered O(1), even though indexing is O(n)?
• What use cases would Linked List be good for over ArrayList?
• Java's garbage collector automatically "frees" the memory of taken by Object instances which no longer have references pointing to them. However, it is still possible to have a memory leak: an build-up of memory usage, composed of unused Object instances never garbage collected. How might this happen in Java because of a poorly implemented Linked List method?
• What are the implementation and usage differences between containment (Stack) and extension (Queue)?
• Which of the SOLID principles we have covered thus far does the Queue violate?
• How might you implement Queue with only access to the Stack class?

(Return to homepage)