배열과 링크드 리스트

주소        값
0x100      arr[0]
0x104      arr[1]
0x108      arr[2]
0x10C      arr[3]

Array-Access(A, i):
    return A[i]                    // O(1) - 주소 계산으로 바로 접근

Array-Insert(A, i, value):
    for j = length(A) down to i+1  // O(n) - 뒤 요소를 한 칸씩 이동
        A[j] = A[j-1]
    A[i] = value
    length(A) = length(A) + 1

Array-Delete(A, i):
    for j = i to length(A)-2       // O(n) - 앞으로 한 칸씩 이동
        A[j] = A[j+1]
    length(A) = length(A) - 1

// 배열 기본 연산
const arr = [10, 20, 30, 40, 50];

// 인덱스 접근 - O(1)
console.log(arr[2]); // 30

// 중간 삽입 - O(n): splice는 뒤 요소를 모두 이동
arr.splice(2, 0, 25); // [10, 20, 25, 30, 40, 50]

// 중간 삭제 - O(n): 뒤 요소를 앞으로 당김
arr.splice(2, 1);     // [10, 20, 30, 40, 50]

// 끝에 추가/삭제 - 평균 O(1)
arr.push(60);  // [10, 20, 30, 40, 50, 60]
arr.pop();     // [10, 20, 30, 40, 50]

head -> [A | next] -> [B | next] -> [C | next] -> null

각 노드는 메모리의 임의 위치에 저장됨:
  노드 A: 0x3A0 (next: 0x7F8)
  노드 B: 0x7F8 (next: 0x120)
  노드 C: 0x120 (next: null)

Node:
    data
    next

LinkedList-Access(head, i):
    current = head
    for j = 0 to i-1               // O(n) - 포인터를 따라 순회
        current = current.next
    return current.data

LinkedList-Insert(prev, value):     // prev 노드 뒤에 삽입
    newNode = Node(value)
    newNode.next = prev.next        // O(1) - 포인터 2개만 변경
    prev.next = newNode

LinkedList-Delete(prev):            // prev 다음 노드를 삭제
    target = prev.next
    prev.next = target.next         // O(1) - 포인터 1개만 변경

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  // 인덱스로 접근 - O(n)
  get(index) {
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
    return current.data;
  }

  // 특정 노드 뒤에 삽입 - O(1)
  insertAfter(node, data) {
    const newNode = new Node(data);
    newNode.next = node.next;
    node.next = newNode;
    this.size++;
  }

  // 특정 노드 뒤의 노드 삭제 - O(1)
  deleteAfter(node) {
    if (node.next === null) return;
    node.next = node.next.next;
    this.size--;
  }

  // 맨 앞에 삽입 - O(1)
  prepend(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }
}

// O(1) - 상수 시간: 입력 크기와 무관
function getFirst(arr) {
  return arr[0];
}

// O(n) - 선형 시간: 입력에 비례
function findValue(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// O(n^2) - 이차 시간: 중첩 루프
function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// 1. Packed (밀집) 모드 - C 배열처럼 연속 메모리 사용
const packed = [1, 2, 3, 4, 5];

// 2. Holey (구멍 있는) 모드 - 해시맵처럼 동작
const holey = [1, , , 4, 5];   // 빈 슬롯이 있음
packed[100] = 99;               // 갑자기 큰 인덱스 사용 -> Holey로 전환

// 성능 팁: V8이 Packed SMI를 유지하도록
const fast = [];
for (let i = 0; i < 1000; i++) {
  fast.push(i);     // SMI, Packed 유지 -> 최적화됨
}

// 피해야 할 패턴
const slow = new Array(1000); // Holey! 빈 슬롯 1000개
slow[999] = 1;                // 여전히 Holey