Deque Collections and Sorting in Java

Master the Deque interface, ArrayDeque, LinkedList as Deque, queue and stack operations, and sorting collections for the OCP 21 exam.

Table of Contents

1. Deque Interface

A Deque (double-ended queue) is a linear collection that supports element insertion and removal at both ends. It extends the Queue interface.

1.1 Deque Characteristics

  • Double-Ended: Can add/remove from both ends
  • Queue Operations: Supports FIFO (First-In-First-Out)
  • Stack Operations: Supports LIFO (Last-In-First-Out)
  • No Index Access: Cannot access elements by index
  • Null Elements: May allow null (implementation-dependent)

1.2 Common Deque Implementations

  • ArrayDeque : Resizable array implementation (recommended)
  • LinkedList : Doubly-linked list implementation

2. ArrayDeque

ArrayDeque is a resizable array implementation of the Deque interface. It's faster than Stack and LinkedList for stack/queue operations.

2.1 Creating ArrayDeque

Example: 
import java.util.*;
// Create empty ArrayDeque Deque<
String>
deque1 = new ArrayDeque<
>
();
// Create with initial capacity Deque<
String>
deque2 = new ArrayDeque<
>
(16);
// Create from collection Deque<
String>
deque3 = new ArrayDeque<
>
(Arrays.asList("A","B","C"));
// Use as Queue Queue<
String>
queue = new ArrayDeque<
>
();
// Use as Stack (preferred over Stack class) Deque<
String>
stack = new ArrayDeque<
>
();

2.2 ArrayDeque Features

  • Resizable array implementation
  • O(1) time for add/remove at both ends
  • More efficient than LinkedList for most operations
  • Does not allow null elements
  • Not thread-safe
  • Recommended over Stack class

3. LinkedList as Deque

LinkedList implements both List and Deque interfaces, so it can be used as a deque.

3.1 Using LinkedList as Deque

Example: 
import java.util.*;
// Create LinkedList as Deque Deque<
String>
deque = new LinkedList<
>
();
// LinkedList allows null elements (unlike ArrayDeque) deque.add(null);
// Allowed // Can also use as List List<
String>
list = (List<
String>
) deque;
list.get(0);
// Access by
index
Note: ArrayDeque is generally preferred over LinkedList for deque operations due to better performance.

4. Queue Operations

Queue operations follow FIFO (First-In-First-Out) principle.

4.1 Queue Methods

Example: 
Queue<
String>
queue = new ArrayDeque<
>
();
// Add to end (enqueue) queue.add("First");
// Throws exception if capacity exceeded queue.offer("Second");
// Returns false if capacity exceeded // Remove from front (dequeue) String first = queue.remove();
// Throws exception if empty String second = queue.poll();
// Returns null if empty // Peek at front (without removing) String peek = queue.element();
// Throws exception if empty String peek2 = queue.peek();
// Returns null if empty // Example: FIFO behavior queue.offer("A");
queue.offer("B");
queue.offer("C");
queue.poll();
//"A" (first in, first out) queue.poll();
//"B" queue.poll();
//"C"

4.2 Queue Method Comparison

Operation Throws Exception Returns null/false
Add add() offer()
Remove remove() poll()
Examine element() peek()

5. Stack Operations

Stack operations follow LIFO (Last-In-First-Out) principle.

5.1 Stack Methods

Example: 
Deque<
String>
stack = new ArrayDeque<
>
();
// Push to top (add) stack.push("First");
// Same as addFirst() stack.addFirst("Second");
// Same as push() // Pop from top (remove) String top = stack.pop();
// Throws exception if empty String top2 = stack.removeFirst();
// Same as pop() // Peek at top (without removing) String peek = stack.peek();
// Returns null if empty String peek2 = stack.peekFirst();
// Same as peek() // Example: LIFO behavior stack.push("A");
stack.push("B");
stack.push("C");
stack.pop();
//"C" (last in, first out) stack.pop();
//"B" stack.pop();
//"A"

5.2 Stack vs Stack Class

Important: The Stack class is legacy. Use ArrayDeque instead for stack operations. ArrayDeque is faster and more efficient.

6. Deque Operations

Deque provides methods to add/remove from both ends.

6.1 First End Operations

Example: 
Deque<
String>
deque = new ArrayDeque<
>
();
// Add to first deque.addFirst("A");
// Throws exception if capacity exceeded deque.offerFirst("B");
// Returns false if capacity exceeded // Remove from first String first = deque.removeFirst();
// Throws exception if empty String first2 = deque.pollFirst();
// Returns null if empty // Peek at first String peek = deque.getFirst();
// Throws exception if empty String peek2 = deque.peekFirst();
// Returns null if
empty

6.2 Last End Operations

Example: 
Deque<
String>
deque = new ArrayDeque<
>
();
// Add to last deque.addLast("A");
// Throws exception if capacity exceeded deque.offerLast("B");
// Returns false if capacity exceeded // Remove from last String last = deque.removeLast();
// Throws exception if empty String last2 = deque.pollLast();
// Returns null if empty // Peek at last String peek = deque.getLast();
// Throws exception if empty String peek2 = deque.peekLast();
// Returns null if
empty

6.3 Deque Method Summary

Operation First End Last End
Add (throws) addFirst() addLast()
Add (returns false) offerFirst() offerLast()
Remove (throws) removeFirst() removeLast()
Remove (returns null) pollFirst() pollLast()
Peek (throws) getFirst() getLast()
Peek (returns null) peekFirst() peekLast()

7. Sorting Collections

Java provides several ways to sort collections: Collections.sort() , List.sort() , and sorted collections.

7.1 Collections.sort()

Example: 
import java.util.*;
List<
String>
list = new ArrayList<
>
();
list.addAll(Arrays.asList("Banana","Apple","Cherry"));
// Sort using natural ordering (Comparable) Collections.sort(list);
// list = [Apple, Banana, Cherry] // Sort using Comparator Collections.sort(list, Comparator.reverseOrder());
// list = [Cherry, Banana, Apple] // Sort with custom Comparator Collections.sort(list, (a, b) -> a.length() - b.length());
// Sort by
length

7.2 List.sort()

Example: 
List<
String>
list = new ArrayList<
>
();
list.addAll(Arrays.asList("Banana","Apple","Cherry"));
// Sort using natural ordering list.sort(null);
// null = natural order // list = [Apple, Banana, Cherry] // Sort using Comparator list.sort(Comparator.reverseOrder());
// Sort with custom Comparator list.sort((a, b) -> a.length() -
b.length());

7.3 Comparable Interface

Example: 
// Class implementing Comparable class Person implements Comparable<
Person>
{
    private String name;
    private int age;
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
@Override public int compareTo(Person other) {
    return this.age - other.age;
    // Compare by age }
@Override public String toString() {
    return name +"(" + age +")";
}
} List<
Person>
people = new ArrayList<
>
();
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 25));
people.add(new Person("Charlie", 35));
Collections.sort(people);
// Sorted by age // [Bob(25), Alice(30),
Charlie(35)]

7.4 Comparator Interface

Example: 
List<
Person>
people = new ArrayList<
>
();
// Using Comparator.comparing() people.sort(Comparator.comparing(Person::getName));
people.sort(Comparator.comparing(Person::getAge));
// Reverse order people.sort(Comparator.comparing(Person::getAge).reversed());
// Multiple criteria (thenComparing) people.sort(Comparator .comparing(Person::getAge) .thenComparing(Person::getName));
// Custom Comparator people.sort((p1, p2) -> p1.getAge() - p2.getAge());
// Using Comparator methods people.sort(Comparator.naturalOrder());
// Requires Comparable
people.sort(Comparator.reverseOrder());

7.5 Sorting Arrays

Example: 
import java.util.Arrays;
String[] arr = {"Banana","Apple","Cherry"};
// Sort array (modifies original) Arrays.sort(arr);
// arr = [Apple, Banana, Cherry] // Sort with Comparator Arrays.sort(arr, Comparator.reverseOrder());
// Sort range int[] numbers = {5, 2, 8, 1, 9};
Arrays.sort(numbers, 1, 4);
// Sort indices 1-3 // numbers = [5, 1, 2, 8,
9]

8. Exam Key Points

Critical Concepts for OCP 21 Exam:

  • Deque Interface: Double-ended queue, supports queue and stack operations
  • ArrayDeque: Resizable array, O(1) operations, no null elements, preferred
  • LinkedList: Implements Deque, allows null elements, less efficient
  • Queue Operations: FIFO - add/offer (end), remove/poll (front)
  • Stack Operations: LIFO - push/addFirst (top), pop/removeFirst (top)
  • addFirst()/offerFirst(): Add to first end
  • addLast()/offerLast(): Add to last end
  • removeFirst()/pollFirst(): Remove from first end
  • removeLast()/pollLast(): Remove from last end
  • peekFirst()/getFirst(): Peek at first end
  • peekLast()/getLast(): Peek at last end
  • push(): Same as addFirst()
  • pop(): Same as removeFirst()
  • Collections.sort(): Sorts list in place
  • List.sort(): Instance method to sort list
  • Comparable: Natural ordering, compareTo() method
  • Comparator: Custom ordering, compare() method
  • Arrays.sort(): Sorts array in place
  • Comparator.comparing(): Create comparator from method reference
  • thenComparing(): Chain comparators for multiple criteria
  • Stack Class: Legacy, use ArrayDeque instead
  • Exception Methods: add(), remove(), element(), getFirst(), getLast()
  • Null-Returning Methods: offer(), poll(), peek(), peekFirst(), peekLast()
Tags:

Post a Comment

0 Comments