정의
원소 저장 시 그 다음 원소가 있는 위치를 포함하는 방식으로 저장하는 자료구조
성질
- k번째 원소를 확인/변경하기 위해 O(k)가 필요하다.
- 임의의 위치에 원소를 추가/제거할 때 O(1)이 필요하다.
- 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉽다.
종류
- 단일 연결 리스트: 각 원소가 자신의 다음 원소의 주소를 가리키는 연결 리스트
- 이중 연결 리스트: 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 가리키는 연결 리스트 →
STL의 list 컨테이너 - 원형 연결 리스트: 단일 연결 리스트 or 이중 연결 리스트 구조에서 끝이 처음과 연결된 연결 리스트
배열 vs 연결 리스트
둘 다 선형 구조이다.
1 byte = 8 bits- 연결 리스트는 다음 원소 or 이전과 다음 원소의 주소값을 추가적으로 가지고 있어야 하기 때문에 64bit 컴퓨터의 경우 주소값이 64bit(= 8byte) 비트 단위니 8Nbyte가 추가로 필요하다.
- 즉, 가지고 있는 주소의 개수 N에 비례하는 만큼의 메모리를 추가로 사용한다.
기능
임의의 위치에 있는 원소를 확인/변경 = O(N)
배열과 다르게 임의의 위치에 있는 원소로 가기 위해서는 그 위치에 도달할 때까지 첫 번째부터 순차적으로 방문해야 한다.
- K번째 원소를 보기 위해서는 O(K)의 시간이 필요하고 전체에 N개의 원소가 있다고 가정하면 평균적으로 N/2의 시간이 걸리니 O(N)만큼 걸린다.
임의의 위치에 원소를 추가 = O(1)
- 배열처럼 원소들을 일일히 옮길 필요 없이 다음 원소의 주소값을 변경한다.
- 단, 추가하고 싶은 위치의 주소를 알고 있을 경우만 해당된다.
임의의 위치에 있는 원소를 제거 = O(1)
- 해당 위치의 이전 원소가 가지고 있는 주소값을 변경한다.
- 메모리 누수를 막기 위해 할당을 해제한다.
- 단, 제거하고 싶은 위치의 주소를 알고 있을 경우만 해당된다.
임의의 위치에 원소를 추가 / 임의의 위치의 원소 제거 수행 시 연결 리스트를 사용하는 것이 효율적이다.
