LinkedList

LinkedList(연결 리스트) 란?

-양방향 연결리스트를 구현한 클래스
-LinkedList 는 List 인터페이스와 Deque 인터페이스를 모두 구현하여 List, Queue, Stack의 기능을 모두 사용할 수 있음.
-Node(노드) 기반의 자료구조로, 각 Node는 데이터와 다음 및 이전 Node에 대한 참조를 가지고 있음

LinkedList의 주요 기능 및 사용법

-LinkedList 생성

LinkedList<Integer> list = new LinkedList<>();

-요소를 List의 특정 위치에 삽입

list.add(1);       // 리스트 끝에 추가
list.addFirst(0);  // 리스트의 첫 번째 위치에 추가
list.addLast(2);   // 리스트의 마지막 위치에 추가
list.add(1, 1);    // 리스트의 특정 위치(1번 인덱스)에 추가

-요소를 List의 특정 위치에서 제거

list.remove();      // 첫 번째 요소 제거
list.removeFirst(); // 첫 번째 요소 제거
list.removeLast();  // 마지막 요소 제거
list.remove(1);     // 특정 위치(1번 인덱스) 요소 제거

-특정 요소를 찾거나 List의 특정 위치에 있는 요소 검색

int first = list.getFirst(); // 첫 번째 요소 검색
int last = list.getLast();   // 마지막 요소 검색
int elements = list.get(1);  // 특정 위치(1번 인덱스) 요소 검색

-List의 길이를 얻거나, List 비우기

int size = list.size();           // 리스트의 길이 반환 
boolean isEmpty = list.isEmpty(); // 리스트가 비어 있는지 확인
list.clear();                     // 리스트의 모든 요소 제거

LinkedList의 시간복잡도

-List의 첫 번째 또는 마지막 위치에 대한 삽입 및 삭제 작업은 O(1)
-List의 중간 위치에 대한 삽입 및 삭제 작업은 해당 위치까지 Node를 탐색해야 하므로 O(n)
-특정 위치에 있는 요소를 검색하는 작업은 O(n)

결론) LinkedList는 데이터의 빈번한 삽입과 삭제가 필요한 경우 유용한 자료구조. 그러나 요소에 대한 임의 접근 시간이 O(n)으로 느리기 때문에, 데이터 접근이 빈번하게 일어나는 경우 ArrayList가 더 적합할 수 있고, 삽입과 삭제가 빈번하면 LinkedList가 더 효율적

BAEKJOON

1158 요세푸스 문제 풀이

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
    public static ArrayList<Integer> getJosephusPermutation(int N, int K) {
        Queue<Integer> queue = new LinkedList();
        ArrayList<Integer> result = new ArrayList();

        IntStream.range(1, N + 1).forEach(queue::offer);

        int cnt = 0;
        while (!queue.isEmpty()) {
            int data = queue.remove();
            cnt ++;

            if (cnt % K == 0) {
                result.add(data);
            } else {
                queue.add(data);
            }
        }
        return result;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        ArrayList<Integer> result = getJosephusPermutation(N, K);

        System.out.print("<");
        for (int i = 0; i < result.size(); i++) {
            if (i == result.size() - 1) {
                System.out.print(result.get(i));
            } else {
                System.out.print(result.get(i) + ", ");
            }
        }
        System.out.println(">");
    }
}