배열 vs 연결 리스트

/* ── 고정 배열 — 인덱스 직접 접근 ─────────────────────── */
int[] arr = new int[5];          // 크기 고정, 연속 메모리 할당
arr[0] = 10; arr[1] = 30;        // O(1) 임의 접근

/* ── 중간 삽입: O(n) — 원소 이동 필요 ──────────────────── */
public static void insertAt(int[] arr, int idx, int val, int size) {
    // 뒤에서부터 한 칸씩 오른쪽으로 이동
    for (int i = size - 1; i >= idx; i--) {
        arr[i + 1] = arr[i];
    }
    arr[idx] = val;
}

/* ── 동적 배열 ArrayList — 내부는 배열, 크기 자동 조정 ──── */
List<Integer> list = new ArrayList<>();
list.add(10);                      // Amortized O(1) — 공간 초과 시 2배 재할당
list.add(1, 20);                  // O(n) — 이후 원소 이동
list.get(0);                      // O(1) — 인덱스 직접 접근
list.remove(0);                   // O(n) — 이후 원소 앞으로 이동

// ArrayList 내부 재할당 원리
// DEFAULT_CAPACITY = 10, 초과 시 newCapacity = oldCapacity * 1.5
// Arrays.copyOf()로 새 배열에 복사 후 참조 교체

/* ── 배열 이진 탐색 — 정렬된 배열에서 O(log n) ─────────── */
int[] sorted = {10, 20, 30, 40, 50};
int idx = Arrays.binarySearch(sorted, 30); // idx = 2

/* ── 단순 연결 리스트 노드 ──────────────────────────────── */
class Node<T> {
    T data;
    Node<T> next;
    Node(T data) { this.data = data; }
}

/* ── 중간 삽입: O(1) — 포인터 교환만 필요 ──────────────── */
public void insertAfter(Node<Integer> prev, int val) {
    Node<Integer> newNode = new Node<>(val);
    newNode.next = prev.next;  // 새 노드가 다음 노드 가리킴
    prev.next    = newNode;    // 이전 노드가 새 노드 가리킴
    // 포인터 2번 변경으로 완료 — 원소 이동 없음
}

/* ── 탐색: O(n) — 순차 순회 필요 ───────────────────────── */
public Node<Integer> findNode(Node<Integer> head, int val) {
    Node<Integer> cur = head;
    while (cur != null) {
        if (cur.data == val) return cur;
        cur = cur.next;
    }
    return null;
}

/* ── Java LinkedList — 이중 연결 리스트 ─────────────────── */
LinkedList<Integer> linked = new LinkedList<>();
linked.addFirst(10);             // O(1) — head 포인터 변경
linked.addLast(50);              // O(1) — tail 포인터 변경
linked.add(1, 20);               // O(n) 탐색 + O(1) 삽입
linked.get(2);                   // O(n) — 순차 탐색
linked.removeFirst();             // O(1) — head 포인터 변경

/* ── Deque로 사용 시 — 양끝 O(1) ───────────────────────── */
Deque<Integer> deque = new LinkedList<>();
deque.offerFirst(1);             // 앞에 추가
deque.offerLast(2);              // 뒤에 추가
deque.pollFirst();               // 앞에서 제거