연결 리스트 (Linked List)
쉽게 풀면
기차 칸을 떠올려 보세요. 각 객차는 바로 다음 객차와만 연결 고리로 이어져 있고, 객차 전체가 한 줄로 붙어있을 필요는 없습니다. 연결 리스트도 마찬가지입니다. 데이터를 담은 "칸(노드)" 하나하나가 메모리 어디에 흩어져 있어도 상관없이, 각 칸이 "다음 칸은 여기야"라는 화살표(포인터)만 갖고 있으면 전체가 하나의 줄로 이어집니다. 배열처럼 처음부터 자리를 예약해두지 않아도 되고, 중간에 새 칸을 끼워 넣거나 빼는 것도 앞뒤 화살표만 바꿔주면 되니 비교적 간단합니다. 다만 몇 번째 칸인지 바로 찾아가려면 처음부터 하나씩 따라가야 해서, 배열처럼 "몇 번째 칸"을 한 번에 짚어내지는 못합니다.
왜 중요한가
연결 리스트는 배열과 함께 자료구조 교육과 시스템 설계에서 가장 기본이 되는 선택지 중 하나이기 때문에, 자료구조·알고리즘 논문뿐 아니라 운영체제, 데이터베이스, 컴파일러 등 실제 시스템을 다루는 논문에서도 배경 설명이나 구현 세부사항으로 자주 등장합니다. 삽입·삭제가 잦고 크기를 미리 알 수 없는 데이터를 다뤄야 하는 상황에서 연결 리스트 기반 설계는 성능과 메모리 사용의 트레이드오프를 논의하는 출발점이 됩니다. 또한 스택, 큐, 해시테이블의 체이닝, 그래프의 인접 리스트 표현 등 더 복잡한 자료구조들이 연결 리스트 개념 위에서 만들어지기 때문에, 이를 정확히 이해하는 것이 다른 자료구조를 다루는 논문을 읽는 데도 도움이 됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 "해당 모듈이 배열이 아니라 노드들을 포인터로 연결한 구조를 사용했고, 그 덕분에 데이터를 추가하거나 제거하는 연산이 데이터 개수와 무관하게 일정한 시간에 끝난다"는 뜻입니다.
이 문장은 "메모리를 관리하는 프로그램이 비어 있는 메모리 조각들을 앞뒤 양쪽 모두를 가리키는 연결 리스트로 관리해서, 어떤 조각이 해제되면 바로 앞뒤 조각과 합칠 수 있다"는 뜻입니다.
이 문장은 "그래프를 표현할 때 각 노드마다 자신과 연결된 다른 노드들을 연결 리스트로 나열해 저장하는 방식이, 연결이 적은 그래프에서는 모든 쌍을 표로 저장하는 방식보다 메모리를 덜 쓴다"는 뜻입니다.
조금 더 깊게 보면
연결 리스트는 각 노드가 다음 노드만 가리키는 단일 연결 리스트(singly linked list)와, 앞뒤 노드를 모두 가리키는 이중 연결 리스트(doubly linked list), 마지막 노드가 다시 첫 노드를 가리켜 원형을 이루는 원형 연결 리스트(circular linked list)로 나뉩니다. 논문에서 구현 세부사항을 설명할 때는 어떤 변형을 사용했는지, 그리고 삽입·삭제·탐색 각 연산의 시간복잡도가 노드 개수에 따라 어떻게 달라지는지를 함께 언급하는 경우가 많습니다. 또한 실제 시스템에서는 캐시 지역성(cache locality) 문제 때문에 연결 리스트가 배열보다 느리게 동작할 수 있는데, 이는 노드들이 메모리 여기저기 흩어져 있어 CPU 캐시를 효율적으로 활용하기 어렵기 때문입니다.
주의할 점
연결 리스트는 삽입·삭제가 빠르다는 장점만 부각되기 쉽지만, 특정 위치의 데이터를 읽으려면 처음부터 순서대로 따라가야 하므로 임의 접근(random access) 속도는 배열보다 느립니다. 또한 각 노드가 다음 노드를 가리키는 포인터를 별도로 저장해야 해서 메모리도 더 사용합니다. 알고리즘의 효율을 판단할 때는 이런 시간복잡도와 빅오 표기법 차이를 함께 고려해야 합니다.