Discussion 7: Linked Lists

In lecture, we introduced several sorting algorithms implemented on arrays, each with its own benefits and drawbacks. However, arrays are not the only linear data structure we may want to sort! Today, we will focus on developing a merge sort implementation for singly-linked lists.

Unlike arrays, linked lists do not provide an \(O(1)\) random access guarantee. This limitation makes sorting algorithms, such as Quicksort, that depend on direct access to specific positions in the structure fairly cumbersome. Merge sort, however, is well-suited to linked lists because of its divide-and-conquer structure. As a reminder, the algorithm consists of three main steps:

1. Split the list into two halves.
2. Recurse on each half to sort them independently.
3. Merge the two sorted halves back together into a single sorted list.

While array-based merge sort requires creating temporary arrays during the merge step, linked lists allow us to split and re-link nodes directly. In this discussion, you’ll develop an algorithm that leverages these properties while strengthening your ability to traverse and manipulate linked structures.

Learning Outcomes

• Draw object (or node) diagrams to visualize linked data structures.
• Implement methods on linked data structures.
• Develop recursive methods in Java given their specifications.
• Determine the number of recursive calls and the maximum depth of the call stack of a recursive method and use these to compute its time and space complexities.
• Compare the performance of List operations implemented with dynamic arrays and linked chains. Determine which is preferable for a given use case.

Reminder: Discussion Guidelines

The work that you complete in discussion serves as a formative assessment tool, meaning it offers the opportunity to assess your understanding of the material and for our course staff to get a “pulse” on how things are going so we can make adjustments in future classes. Your grade in discussion is based entirely on attendance and participation; if you show up and you are actively engaged with the activity (working on the activity on your computer, discussing the activity with your group, asking and answering questions, etc.) for the entire 50-minute section period, you will earn full credit. If you complete the activity early, helping other students is a great way to further your own understanding. You do not need to submit any of the work that you complete during discussion.

Since discussion activities are not graded for correctness, we do not place any restrictions on resources that you may use to complete them, which include notes, books, unrestricted conversations with other students, internet searches, and the use of large language models or other generative AI. We advise you to be pragmatic about your use of these resources and think critically about whether they are enhancing your learning. Discussion activities are intended to serve as “strength training” for programming tasks we will expect on assignments and exams (and that you will encounter in future courses and careers), and their main benefit comes from critically thinking to “puzzle” them out.

Working together in small groups is encouraged during discussion!

1
2
3
4
5

/**
 * Splits the linked list starting at `head` into two halves. Returns the head of the second
 * half. If the list has an odd number of nodes, the extra node goes in the first half.
 */
static Node<Integer> split(Node<Integer> head) { ... }

1
2
3
4
5

/**
 * Splits the linked list starting at `head` into two halves. Returns the head of the second
 * half. If the list has an odd number of nodes, the extra node goes in the first half.
 */
static Node<Integer> split(Node<Integer> head) { ... }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * Splits the linked list starting at `head` into two halves. Returns the head of the second
 * half. If the list has an odd number of nodes, the extra node goes in the first half.
 */
static Node<Integer> split(Node<Integer> head) {
  Node<Integer> slow = head;
  Node<Integer> fast = head.next;

  while (fast.data != null) {
    fast = fast.next;
    if (fast.data != null) {
      fast = fast.next;
      slow = slow.next;
    }
  }

  Node<Integer> mid = slow.next;
  slow.next = new Node<>(null, null);

  return mid;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * Splits the linked list starting at `head` into two halves. Returns the head of the second
 * half. If the list has an odd number of nodes, the extra node goes in the first half.
 */
static Node<Integer> split(Node<Integer> head) {
  Node<Integer> slow = head;
  Node<Integer> fast = head.next;

  while (fast.data != null) {
    fast = fast.next;
    if (fast.data != null) {
      fast = fast.next;
      slow = slow.next;
    }
  }

  Node<Integer> mid = slow.next;
  slow.next = new Node<>(null, null);

  return mid;
}

1
2
3
4
5

/**
 * Returns the head of the merged list containing all nodes from the lists `head1` 
 * and `head2`, in sorted order. Requires that `head1` and `head2` are sorted.
 */
static Node<Integer> merge(Node<Integer> head1, Node<Integer> head2) { ... }

1
2
3
4
5

/**
 * Returns the head of the merged list containing all nodes from the lists `head1` 
 * and `head2`, in sorted order. Requires that `head1` and `head2` are sorted.
 */
static Node<Integer> merge(Node<Integer> head1, Node<Integer> head2) { ... }

1
2
3
4

/**
* Sorts the entries of `head` using the merge sort algorithm. 
*/
static void mergeSort(Node<Integer> head) { ... }

1
2
3
4

/**
* Sorts the entries of `head` using the merge sort algorithm. 
*/
static void mergeSort(Node<Integer> head) { ... }