자바 - Queue의 LinkedList 이야기와 이걸로 코테 푸는 법

LinkedList는 List걸로도 쓸 수 있고 Queue걸로도 쓸 수 있고 Deque걸로도 쓸 수 있다.

e.g. Deque<Integer> numbers = new LinkedList<>(); <- 이렇게 하면 링크드리스트가 가진 기본 메서드를 다 쓰면서 덱만의 메서드를 쓸 수 있고 리스트나 큐가 가진 메서드는 쓸 수 없다.

상황에 따라 선택하면 된다.

 

여기서는 큐를 구현한 링크드리스트를 알아 보자!

 

Java에서 LinkedList 클래스는 List와 Deque 인터페이스를 구현하는데, 이를 통해 이중 연결 리스트(double-linked list) 구조를 제공합니다. LinkedList를 사용하는 주된 이유 중 하나는 그것이 큐(queue), 더블 엔디드 큐(deque), 그리고 리스트(list) 기능을 모두 제공하기 때문입니다. 다음은 LinkedList가 큐로 사용될 때의 특징과 관련 기능에 대한 자세한 설명입니다.

 

그림을 보면 이해가 더 빠르다.

https://howtodoinjava.com/java/collections/java-linkedlist-class/

자바의 LinkedList의 특징

1. 이중 연결 리스트: 각 요소는 앞과 뒤의 요소를 참조하는 포인터를 가집니다. 이를 통해 양방향 탐색이 가능합니다.
2. 동적 크기 조절: 요소가 추가되거나 제거될 때 내부적으로 크기가 조절됩니다. 고정 크기의 제약이 없습니다.
3. 빠른 삽입 및 삭제: 인덱스를 통하지 않는 삽입 및 삭제 연산에서는 O(1) 시간 복잡도를 가집니다. 그러나 특정 인덱스에서의 접근은 O(n)입니다.

Queue 인터페이스 구현

LinkedList는 Queue 인터페이스를 구현하여 다음과 같은 메서드를 제공합니다:

• offer(E e): 큐의 끝에 요소를 추가합니다. 성공하면 true를 반환하고, 실패하면 false를 반환합니다.
• poll(): 큐의 헤드를 제거하고 반환합니다. 큐가 비어 있으면 null을 반환합니다.
• peek(): 큐의 헤드를 반환하지만 제거하지 않습니다. 큐가 비어 있으면 null을 반환합니다.

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        
        System.out.println(queue.peek());  // 출력: 1
        System.out.println(queue.poll());  // 출력: 1
        System.out.println(queue.peek());  // 출력: 2
    }
}

 

기본 사용 예.

성능 고려사항

• LinkedList는 빈번한 인덱스 기반 접근이 필요한 경우에는 적합하지 않습니다. 각 접근이 리스트를 순차적으로 탐색하기 때문에 성능 저하가 발생할 수 있습니다.
• 대량의 데이터 삽입 및 삭제가 주로 리스트의 양 끝에서 발생하는 경우 LinkedList는 매우 효율적입니다.

큐로 구현한 링크드리스트로 코테를 잘 풀기 위해 추가적으로 알아야 하는 메서드는 더 없을까?

덱을 따로 설명할 거여서 위에 일부러 안 적었었는데 이 부분에 대한 설명을 넣어야겠다.

위에 적은 큐에서 구현된 메서드 외에 덱에서 구현된 메서드도 기억해 두면 좋겠다.

Deque 인터페이스의 추가 메서드

LinkedList는 Deque 인터페이스를 구현하므로, 큐의 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 추가 메서드를 제공합니다:

1. void addFirst(E e) 및 void addLast(E e):
   1. 각각 요소를 리스트의 시작과 끝에 추가합니다. addLast(e)는 offer(e)와 동일합니다.
2. boolean offerFirst(E e) 및 boolean offerLast(E e):
   1. addFirst(e)와 addLast(e)와 유사하지만, 요소 추가에 실패할 경우 false를 반환합니다.
3. E removeFirst() 및 E removeLast():
   1. 리스트의 첫 번째와 마지막 요소를 제거하고 해당 요소를 반환합니다. 요소가 없을 경우 NoSuchElementException을 발생시킵니다.
4. E pollFirst() 및 E pollLast():
   1. removeFirst()와 removeLast()와 유사하지만, 리스트가 비어 있을 경우 null을 반환합니다.
5. E getFirst() 및 E getLast():
   1. 각각 리스트의 첫 번째와 마지막 요소를 반환합니다. 리스트가 비어 있을 경우 NoSuchElementException을 발생시킵니다.
6. E peekFirst() 및 E peekLast():
   1. getFirst()와 getLast()와 유사하지만, 리스트가 비어 있을 경우 null을 반환합니다.

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(10);
        queue.offer(20);
        System.out.println(queue.peek());  // 10
        System.out.println(queue.poll());  // 10
        System.out.println(queue.peek());  // 20

        LinkedList<Integer> deque = new LinkedList<>();
        deque.addFirst(5);
        deque.addLast(15);
        System.out.println(deque.peekFirst());  // 5
        System.out.println(deque.peekLast());  // 15
    }
}

 

Queue<Integer> queue = new LinkedList<>(); <- 인터페이스 참조 타입이 큐라서 offer, poll이 사용 가능하다. 그러나 덱이나 리스트 인터페이스의 메서드는 쓸 수 없다.

LinkedList<Integer> deque = new LinkedList<>(); <- 인터페이스 참조 타입이 링크드리스트라서 큐, 덱, 리스트 인터페이스에서 제공하는 모든 메서드를 쓸 수 있다.

---

설명이 너무 길었던 거 같다.

바로 문제 풀러 가자.

문제: Sliding Window Maximum

문제 설명: 주어진 배열 nums와 정수 k에 대해, 각 슬라이딩 윈도우의 최대값을 계산하고 이를 배열로 반환합니다. 슬라이딩 윈도우는 배열의 첫 요소부터 시작하여 k개의 길이로 한 칸씩 오른쪽으로 이동합니다.

 

예시:

• 입력: nums = [1,3,-1,-3,5,3,6,7], k = 3
• 출력: [3,3,5,5,6,7]
• 설명:
  • Window position -> 최대값
  • [1 3 -1] -3 5 3 6 7 -> 3
  • 1 [3 -1 -3] 5 3 6 7 -> 3
  • 1 3 [-1 -3 5] 3 6 7 -> 5
  • 1 3 -1 [-3 5 3] 6 7 -> 5
  • 1 3 -1 -3 [5 3 6] 7 -> 6
  • 1 3 -1 -3 5 [3 6 7] -> 7

최적의 솔루션

Java의 LinkedList를 사용하여 이 문제를 풀 수 있는 방법은 "Deque"을 사용하여 윈도우의 가능한 최대 값을 유지하는 것입니다. Deque 내부에서는 윈도우의 최대값 후보들의 인덱스를 저장하며, 큐의 앞부분은 항상 윈도우의 최대값의 인덱스를 가리키도록 합니다.

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {
            // Remove numbers out of range k
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            // Remove smaller numbers in k range as they are useless
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            // Deque contains index... r contains content
            deque.offer(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peek()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] results = maxSlidingWindow(nums, k);
        for (int result : results) {
            System.out.print(result + " ");
        }
    }
}

 

위 풀이에 쓰인 기법은 슬라이딩 윈도우 알고리즘이다.

https://www.geeksforgeeks.org/window-sliding-technique/

 

슬라이딩 윈도우는 배열 또는 리스트의 '일정 범위'의 요소를 연속적으로 이동하면서 처리할 때 사용하는 기법이다.

이 코드에서는 Deque을 사용하여 각 슬라이드에서 최대값을 빠르게 찾는다.

 

코드 다 봤는데 이해는 했다만 이걸 내 손으로 바로 짜라하면 못 짤 것 같다. 🥹

언젠가는 되겠지.