연결 리스트
2 min read
연결 리스트는 추상적 자료형인 리스트를 구현한 자료구조이다.
데이터와 다음 노드의 위치 정보를 담는 노드를 이용해 데이터를 저장하며,
이를 통해 배열의 제약을 극복하고 데이터를 유연하게 관리할 수 있다.
연결 리스트 탄생 배경
연결 리스트는 배열의 단점을 극복하기 위해 탄생하였다.
배열은 연속된 메모리 공간을 요구하고, 초기 크기 설정이 어려울 때 메모리 낭비가 발생할 수 있는 단점이 있다. 반면, 연결 리스트는 데이터를 메모리 공간에 분산하여 할당하고, 이 데이터들을 논리적으로 연결하여 배열의 단점을 극복하였다.
연결 리스트의 종류
연결 리스트는 다양한 형태로 구현될 수 있으며, 주요 종류는 다음과 같다.
- 단순 연결 리스트 (Singly Linked List):
- 각 노드가 다음 노드만을 가리킨다.
- 노드의 삽입과 삭제가 간단하지만, 이전 노드로의 접근이 불가능하다.
- 이중 연결 리스트 (Doubly Linked List):
- 각 노드가 이전 노드와 다음 노드를 모두 가리킨다.
- 노드의 삽입과 삭제가 더 유연하며, 이전 노드로의 역방향 탐색이 가능하다.
- 원형 연결 리스트 (Circular Linked List):
- 마지막 노드가 첫 번째 노드를 가리킵니다.
- 리스트의 시작과 끝을 연결하는 순환 구조로, 리스트의 끝에서 시작으로의 전환을 간단하게 한다.
현재 글에서는 단순 연결 리스트를 중심으로 설명한다.
연결 리스트의 메모리 구조
연결 리스트는 노드라는 기본 단위로 구성된다.
노드의 구조
- 데이터를 담는 변수와 다음 노드를 가리키는 변수 하나로 구성
- 필요한 데이터만큼 노드를 만들어서 저장하고 다음 노드를 가리켜 저장한다
- 첫번째 노드의 주소만 알고 있으면, 연쇄적으로 모든 노드에 접근할 수 있다.
연결 리스트의 장단점
| 장점 | - 빈 메모리 공간 어디든 데이터를 생성하고 연결하면 되기 때문에 초기 크기 설정이 불필요하다 - 가리키는 노드만 바꿔주면 되기 때문에 중간에 데이터 삽입/삭제 시 작업이 간단하다 |
|---|---|
| 단점 | - 데이터가 메모리 상에 연속적이지 않아 특정 인덱스에 바로 접근할 수 없다. - 첫번째 노드부터 차례로 이동하기 때문에 참조가 O(n)의 성능을 가진다. - - 노드 중 하나가 잘못되는 경우 이후의 모든 데이터에 접근할 수 없다. |
배열 vs 연결 리스트
| 배열 | 연결리스트 | |
|---|---|---|
| 크기 | 고정 | 동적 |
| 주소 | 연속 | 불연속 |
| 데이터 참조 | O(1) | O(n) |
| 삽입과 삭제 | O(n) | O(n) |
전체적인 데이터의 수가 자주 바뀌지 않고 참조 위주로 발생 시 - 배열
데이터의 삽입과 삭제가 자주 일어나는 경우 - 연결 리스트