Sorted List and compareTo

Intermediate Algorithms and Data Structures English

Also available: Deutsch

Created by Best · 16.08.2026 at 09:13 UTC

A sorted list maintains the invariant that consecutive elements are in non-decreasing order with respect to a given order. Insertion searches for the position and appends the node.

In Java, Comparable.compareTo provides the natural order. Comparator allows an external order without having to change the element class.

Example: Inserting 5 into 1-3-8 results in 1-3-5-8.

Complexity: Search $O(n)$ in the linked list, followed by $O(1)$ for rearranging.

Where used

Small sorted collections, merging streams, priorities without a full heap, when n remains small. compareTo/Comparator is the same order that TreeMap, sorting, and PriorityQueue use.

Depth

A sorted list maintains the invariant after each modification that consecutive elements do not decrease according to the comparison relation. The insertion position is the first place where the new element is no longer greater than the current value.

compareTo returns a negative, zero, or positive result. The specific magnitude has no portable meaning. A consistent order should be transitive and antisymmetric in sign; otherwise, searching and inserting can yield contradictory positions.

In a linked structure, the search for the position remains linear. Sorting does not improve random access there but can enable early termination during searching and ordered merging of two lists.

Difficulty levels

Correctly interpreting the sign of comparison results.
Determining an insertion position under duplicate rules.
Analyzing sequences of a non-transitive comparison relation.

Pitfalls

Code must not assume that the result is exactly -1, 0, or 1. Additionally, an order that is inconsistent with equals can produce surprising duplicate semantics.

University approvals: 0

Tasks

Question 1

When is it worthwhile to implement Comparable on the element class?

If only one natural order exists and is often used

If every sorting requires a different order

If the list is to remain unsorted.

If generics are banned

Question 2

Implement insertSorted for an ascending sorted singly linked list of integers.

Hint

For primitive int values, <, <=, and > are sufficient. A new node can be created with a successor directly in the constructor.

public class SortedSingly {
  static class Node {
    int value; Node next;
    Node(int value, Node next) { this.value = value; this.next = next; }
  }
  Node head;
  public void insertSorted(int value) {
    // TODO
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Question 3

What can portable code use from x.compareTo(y)?

Only the sign of the result

Always the exact value -1, 0, or 1

The object address of x

The difference of the hash values

Card Info

Topic: Algorithms and Data Structures
Difficulty: Intermediate
Completed: 0 users

Creator

Best

BestBuddy