[자료구조] List
List 자료구조
데이터를 순차적으로 나란히 저장하며 중복된 데이터 또한 허용하는 자료구조이다.
✔ 리스트의 주요 특징
- 요소가 삽입된 순서를 유지한다.
- 배열/동적배열 기반 리스트는 인덱스를 통한 접근이 가능하여 탐색에 유리하다
- 연결리스트는 삽입과 삭제가 용이하다.
배열 기반 리스트
연속된 메모리 공간(배열, array)을 기반으로 데이터를 저장하는 리스트 자료구조
물리적으로 메모리 상에 연속적으로 배치된다.
✔ 장점
빠른 인덱스 접근: O(1) 시간 복잡도로 임의의 요소를 읽을 수 있음
캐시 효율성: 메모리 접근 패턴이 연속적이라 캐시 히트율이 높음
간단한 구현: 배열 기반 구조로 구현이 간단함
✔ 단점
삽입/삭제 비용: 중간 요소 삽입/삭제 시 요소들을 이동시켜야 하므로 O(n) 시간 소요
크기 제한: 초기 크기를 정해야 하거나, 동적 확장을 위해 새로운 배열을 할당하고 복사해야 함
메모리 단편화 가능성: 연속 메모리 할당이 필요하므로 메모리가 단편화될 수 있음
| 10 | 20 | 30 | 40 | 50 |
이런식으로 되어있음.
연결리스트 (Linked List)
각각의 노드가 데이터를 가지며 또한 포인터를 통해 다른 데이터(전 or 후)를 참조하는 형태이다.
각 노드의 포인터는 전 노드와의 연결을 담당한다.
- 단순 연결 리스트
각 노드가 데이터 공간과 포인터 공간이 있으며 다음 노드를 잇는다.
포인터가 1개라서 메모리가 효율적이며 단방향 탐색만 가능하다.
- 원형 연결 리스트
일반적인 연결 리스트의 마지막 노드와 처음 노드를 연결하여 원형으로 만든 구조이다.
단방향 탐색만 가능하며 포인터가 하나라서 메모리가 효율적이다.
하지만 끝에 대한 경계가 모호하므로 무한 루프에 주의해야 한다.
궁금해서 왜 굳이 원형으로 만드는 걸까 찾아보았다.
✅ 순환 구조 표현
- 리스트의 끝에 도달하면 처음으로 돌아가게 만들고 싶을 때 (예: 게임 턴, 음악 재생 리스트, 작업 스케줄러)
- 연결 리스트가 "끝"에서 다시 "시작"으로 자연스럽게 이어지는 구조가 필요할 때
✅ 메모리 재사용 및 연속 처리
- 일정한 작업 반복이나, 메모리를 재활용할 때 유리 (예: 스케줄러, 라운드 로빈)
✅ 게임, 음악 플레이어 등에서 반복 처리
- 마지막 노드에서 처음 노드로 자연스럽게 돌아가기 때문에 게임 플레이어, 음악 플레이어 같은 곳에서 사용
- 양방향 연결 리스트
포인터 공간이 두개가 존재하며 각각의 포인터는 전 노드와 후의 노드를 잇는다.
동적 메모리 할당이기 때문에 크기를 자유롭게 조절 할 수 있으며 데이터의 추가 삭제가 용이하다.
하지만 연속 메모리 할당방식은 아니기 때문에 배열기반 처럼 인덱스를 통한 임의접근이 불가능하여
탐색에 불리하다. (순차적으로 앞에서부터 접근해야 한다.)
포인터가 2개라서 메모리가 더 많이 필요하다.
| 연산 | 단순연결리스트 | 원형연결 | 양방향 |
| 탐색 | O(n) | O(n) | O(n) |
| 삽입/삭제 (중간) | O(1) (노드 위치 알고 있을 때) | O(1) (위치 알고 있을 때) | O(1) (위치 알고 있을 때) |
| 삽입/삭제 (탐색 포함) | O(n) | O(n) | O(n) |
| 앞 삽입 | O(1) | O(1) | O(1) |
| 끝 삽입 | O(n) (tail 필요) | O(1) (tail 유지) | O(1) (tail 유지) |
| 역방향 탐색 | 불가능 | 불가능 | 가능 |