연결 리스트 (Linked List)

노드들이 포인터로 연결된 선형 자료구조

단일 연결 리스트:
[10|→] → [20|→] → [30|→] → null
 head

이중 연결 리스트:
null ← [←|10|→] ⇄ [←|20|→] ⇄ [←|30|→] → null
         head                        tail

면접에서 이렇게 나옵니다

Q.연결 리스트의 장단점을 설명해주세요

크기가 유연하고 삽입과 삭제가 싸지만, 임의 접근과 캐시 효율을 포기합니다.

흔한 실수: "삽입과 삭제가 O(1)"만 외우는 것. 그 위치를 찾는 비용이 따로 들고, 인덱스로 찾는다면 탐색이 O(n)이라 이득이 사라집니다. O(1)이 성립하는 것은 이미 그 노드를 참조하고 있을 때입니다.

Q.LRU 캐시를 연결 리스트로 구현하는 방법은?

이중 연결 리스트와 해시 맵을 함께 씁니다. 둘 다 있어야 모든 연산이 O(1)이 됩니다.

자료구조	역할
해시 맵	키에서 노드를 O(1)에 찾는다
이중 연결 리스트	최근 사용 순서를 유지한다. 맨 앞이 최신

동작	처리
조회	맵에서 노드를 찾아 리스트 맨 앞으로 옮긴다
저장	맨 앞에 넣는다. 용량을 넘으면 맨 뒤를 버리고 맵에서도 지운다

이중인 이유는 노드를 떼어낼 때 앞 노드를 알아야 하기 때문입니다. 단일 연결이면 앞 노드를 찾으려고 처음부터 훑어야 해서 O(n)이 됩니다.

흔한 실수: 해시 맵만으로 만들려는 것. 맵은 순서를 모르므로 무엇을 버릴지 고를 수 없습니다. 반대로 리스트만 쓰면 조회가 O(n)입니다.

Q.단일 vs 이중 연결 리스트 차이는?

노드가 다음만 가리키는지, 이전까지 가리키는지의 차이입니다. 그 차이가 삭제 비용을 가릅니다.

그래서 LRU 캐시나 OS의 대기 큐처럼 중간 노드를 자주 떼어내는 곳은 이중을 씁니다. 한 방향으로만 훑고 버리는 구조라면 단일이 가볍습니다.

흔한 실수: 단일 연결에서 노드 삭제가 불가능하다고 답하는 것. 지울 노드의 다음 값을 현재 노드에 복사하고 다음 노드를 떼는 우회법이 있습니다. 다만 마지막 노드에는 쓸 수 없습니다.

Q.연결 리스트에서 사이클을 검출하는 방법은?

두 포인터를 다른 속도로 움직입니다. 한 칸씩 가는 것과 두 칸씩 가는 것을 함께 보냅니다.

포인터	이동
느린 쪽	한 번에 한 칸
빠른 쪽	한 번에 두 칸

경우	결과
사이클이 없다	빠른 쪽이 끝에 먼저 닿는다
사이클이 있다	빠른 쪽이 고리를 돌다가 느린 쪽을 반드시 따라잡는다

매 걸음마다 둘의 간격이 1씩 줄어들기 때문에 고리 안에서는 반드시 만납니다. 시간은 O(n)이고 추가 메모리는 상수입니다.

방문한 노드를 집합에 담는 방법도 O(n)이지만 메모리를 n만큼 씁니다. 면접에서 원하는 답은 대개 두 포인터입니다.

흔한 실수: 만나는 지점을 사이클의 시작점이라고 답하는 것. 만난 뒤 한 포인터를 머리로 되돌리고 둘을 한 칸씩 움직이면 그때 만나는 곳이 시작점입니다.

먼저 스스로 답해보고 아래 답변과 견줘보세요. 막히는 부분은 문제로 확인할 수 있어요.

더 깊이 공부하기

읽었으면 문제로 확인해보세요

자료구조 문제를 풀면 틀린 문제가 자동으로 노트에 쌓입니다. 가입 없이 5문제를 먼저 풀어볼 수도 있어요.