연결리스트

1. 배열 기반 연결 리스트

int[] prev = new int[n];
int[] next = new int[n];
boolean[] deleted = new boolean[n];

• prev[i]는 i 이전 노드의 인덱스

• next[i]는 i 다음 노드의 인덱스

• deleted[i] 는 삭제 여부

1. Node 클래스 기반 연결 리스트

class Node {
    int index;
    Node prev;
    Node next;
}

🎯 결정 기준

질문	배열 방식	Node 방식
n이 고정인가요?	✅	❌
삭제된 객체의 위치와 내용도 기억해야 하나요?	❌	✅
노드마다 다양한 데이터가 필요한가요?	❌	✅
성능이 중요한가요 (O(1) 삭제/복원)?	✅	✅
디버깅이 쉬워야 하나요?	✅	❌