연결 리스트(Linked List) 종류: 단방향, 양방향, 원형 리스트 비교

배열(Array)은 메모리 공간에 데이터들이 빈틈없이 다닥다닥 붙어 살아야 하는 엄격한 아파트 구조입니다. 101호 다음은 무조건 102호여야 하죠. 그래서 몇 번째 집인지 알면 단번에 찾아갈 수 있지만, 중간에 새로운 집을 하나 지어 넣으려면 그 뒤에 있는 수만 개의 집들을 모조리 뒤로 한 칸씩 밀어내야 하는 치명적인 성능 저하($O(N)$)가 발생합니다. 반면, '연결 리스트(Linked List)'는 각 데이터(노드)가 메모리상에 물리적으로는 뿔뿔이 흩어져 있지만, 다음 데이터가 어디 있는지 그 '주소(포인터)'를 실처럼 묶어 연결해 놓은 기차 구조입니다. 중간에 객차를 끊고 새 객차를 끼워 넣기만 하면 끝나는 이 유연한 구조의 세 가지 진화 형태를 살펴봅니다.

1. 단방향 연결 리스트 (Singly Linked List): 일방통행 기차

가장 기본적이고 뼈대가 되는 단순한 형태입니다. 하나의 노드(객차)는 자신의 '데이터'를 담는 방과, '다음 노드의 주소(Next Pointer)'를 기억하는 방 두 개로만 이루어져 있습니다. 기차의 머리(Head)부터 시작해서 무조건 다음 칸으로, 또 다음 칸으로 직진만 할 수 있습니다.

• 장점: 메모리를 가장 적게 차지하며, 구조가 단순해서 구현하기 쉽습니다. 스택(Stack)을 메모리 제한 없이 동적으로 구현할 때 훌륭한 재료가 됩니다.
• 치명적 단점: 앞으로 가는 것만 가능하고, 지나쳐 온 뒤로 되돌아가는 것은 절대 불가능합니다. 만약 기차의 맨 뒤(Tail)에 있는 노드를 지우고 싶다면, 머리부터 시작해서 꼬리 바로 앞 칸까지 다시 $O(N)$의 시간을 달려가야 하는 엄청난 수고로움이 발생합니다.

2. 양방향 연결 리스트 (Doubly Linked List): 전진과 후진의 마법

단방향 리스트의 끔찍한 답답함을 단번에 해소하기 위해, 각 노드에 '이전 노드의 주소(Prev Pointer)'를 저장하는 방을 하나 더 뚫어준 형태입니다. 이제 기차는 다음 칸으로(Next) 갈 수도 있고, 이전 칸으로(Prev) 후진할 수도 있습니다.

• 압도적인 장점: 삭제하려는 노드의 위치만 알고 있다면, 그 노드의 앞뒤 연결 고리를 싹둑 자르고 서로 직접 이어주는 작업이 단 $O(1)$ 만에 완벽하게 끝납니다. 우리가 흔히 쓰는 웹 브라우저의 '뒤로 가기 / 앞으로 가기' 버튼이나, 워드 프로세서의 Ctrl + Z (실행 취소) 기능, 그리고 스마트폰의 최근 실행 앱 목록 등이 바로 이 양방향 구조로 구현됩니다.
• 단점(대가): 이전 주소를 기억하기 위한 포인터 공간이 추가로 필요하므로 메모리를 더 많이 소모하며, 코드를 짤 때 포인터 2개를 동시에 조작해야 하므로 버그가 나기 쉽습니다.

3. 원형 연결 리스트 (Circular Linked List): 꼬리를 무는 뱀

기차의 맨 마지막 칸(Tail)이 허공(Null)을 가리키며 끝나는 대신, 그 포인터가 다시 맨 앞의 머리(Head) 칸과 연결되어 끊임없이 둥근 고리를 이루는 구조입니다. 단방향 리스트의 꼬리를 머리에 묶을 수도 있고, 양방향 리스트의 꼬리를 머리에 묶어 완벽한 회전목마를 만들 수도 있습니다.

• 활용의 정점: 여러 명의 플레이어가 둥글게 앉아 순서대로 턴을 영원히 반복 진행하는 보드게임을 프로그래밍하거나, 컴퓨터 운영체제가 여러 개의 실행 중인 프로그램(프로세스)에 CPU 사용 시간을 빙글빙글 돌려가며 공평하게 분배하는 '라운드 로빈(Round Robin)' 스케줄링 알고리즘에서 없어서는 안 될 핵심 뼈대로 활약합니다. 꼬리와 머리가 닿아 있어 어느 노드에서 시작하든 결국 모든 노드를 순회할 수 있다는 것이 최고의 장점입니다.

[핵심 요약]
1. 단방향 연결 리스트(Singly Linked List)는 다음 노드의 주소만 기억하여 한 방향으로만 탐색할 수 있으며, 메모리가 가장 적게 들지만 뒤로 갈 수 없는 단점이 있습니다.
2. 양방향 연결 리스트(Doubly Linked List)는 이전과 다음 노드의 주소를 모두 가져 탐색과 노드 삭제($O(1)$)가 매우 유연하여 웹 브라우저 방문 기록 등에 쓰입니다.
3. 원형 연결 리스트(Circular Linked List)는 마지막 노드가 첫 번째 노드를 가리켜 무한 루프를 도는 구조로, CPU 스케줄링 등 순환적인 데이터 처리에 최적화되어 있습니다.