연결 리스트(Linked List)란 무엇인가?
연결 리스트(Linked List)는 여러 개의 데이터 구조가 링크(link)를 통해 서로 연결되어 있는 선형 데이터 구조입니다. 각 항목은 다음 항목에 대한 참조(reference)를 가지고 있어, 배열과 달리 물리적으로 연속된 메모리 공간에 저장되지 않고도 데이터를 순차적으로 관리할 수 있습니다.
연결 리스트는 삽입과 삭제가 빈번하게 일어나는 상황에서 특히 유용하여, 실무에서 가장 널리 사용되는 데이터 구조 중 하나로 꼽힙니다.
연결 리스트의 핵심 구성 요소
자바스크립트에서 연결 리스트를 구현할 때 반드시 알아야 할 기본 용어는 다음과 같습니다.
1. 노드(Node)
노드는 연결 리스트를 이루는 각각의 요소를 의미합니다. 하나의 노드는 두 부분으로 구성됩니다.
- Data(데이터): 리스트에 저장하고자 하는 실제 값입니다.
- Next(다음 참조): 리스트에서 다음 요소를 가리키는 참조입니다.
2. 링크(Link)
노드가 가진 next 참조 하나하나를 링크라고 부릅니다. 이 링크를 통해 개별 노드들이 서로 연결되어 하나의 리스트 형태가 만들어집니다.
3. 헤드(Head)
헤드는 연결 리스트의 첫 번째 요소에 대한 참조입니다. 모든 탐색은 헤드부터 시작되기 때문에, 헤드는 연결 리스트의 진입점(entry point) 역할을 합니다.
4. 테일(Tail)
테일은 리스트의 마지막 노드를 가리키며, 테일 노드의 next 참조는 보통 null입니다. 이는 리스트의 끝을 판별하는 기준이 됩니다.
연결 리스트의 장점
- 빠른 삽입과 삭제: 배열과 달리 요소를 추가하거나 제거할 때 나머지 요소를 이동할 필요가 없습니다.
- 동적 크기 조절: 필요에 따라 노드를 자유롭게 추가할 수 있어 크기가 고정되지 않습니다.
- 메모리 효율: 사용하는 만큼만 메모리를 할당합니다.
이처럼 연결 리스트는 노드와 링크의 조합으로 이루어진 유연한 데이터 구조로, 자바스크립트에서 스택, 큐 등 다른 자료구조를 구현하는 기반이 되기도 합니다.