[자료구조] 리스트

STL 시퀀스 컨테이너

요소들이 순차적으로 저장되는 컨테이너(선형구조)이다. 순차적으로 저장된다는 의미는 요소의 순서를 유지한다는 뜻이다.

 

리스트는 STL 시퀸스 컨테이너이다.

 

 

리스트는 큰 틀에서 두가지로 먼저 나뉜다.

 

1. 배열 기반 리스트 ( Array List )

배열을 기반으로 구현된 선형 자료구조이다. STL의 vector가 대표적인 예이다.

 

특징

- 연속적인 메모리 공간에 데이터를 저장하는 구조

- 동적 크기로 확장 가능

- 인덱스를 통해 빠른 임의 접근 기능 O(1)

- 중간 삽입, 중간 삭제는 느리다. 삽입한 곳에서 끝까지 밀어야하고(O(n)) 삭제한 곳에서 끝까지 당겨야한다. (O(n))

   하지만 맨 뒤 는 O(1)로 빠르다

 

 

장점

1. 빠른 임의 접근

arr[i] 형태로 인덱스를 통해 바로 접근 가능하다. O(1)

 

2. 캐시 친화적

메모리 상에 연속적인 공간에 저장되므로 캐시 효율이 좋다. 실제 실행 속도도 빠르다.

 

3. 메모리 낭비 적음

포인터 등의 추가정보 없이 값만 저장하므로 연결리스트보다 메모리 사용이 효율적이다

 

4. 간단한 구현

선형 메모리 구조이기 때문에 설계/구현이 상대적으로 간단하다

 

 

단점

1. 크기 제한 혹은 재할당이 필요

초기 크기를 넘으면 메모리 재할당을 하고 복사해주어야한다. 메모리할당 + O(n) 복사비용이 발생한다

 

2. 중간 삽입, 삭제 느림

요소들을 뒤로 밀거나 당겨야하므로 O(n) 시간이 걸린다. 하지만 마지막 요소에 대한 적용은 O(1)이다.

 

3. 공간 낭비

동적 확장을 위해 여분의 공간을 미리 확보해두기 때문에 일부 메모리는 사용되지 않을 수도 있다.

 

언제써야 이득인가?

- 요소에 자주 접근해야하고

- 삽입, 삭제는 주로 맨끝에서 이루어져야하고 메모리 사용량이 중요할 때

 

 

 

2. 연결기반 리스트 ( Linked List )

노드들이 포인터를 통해 연결된 선형 자료구조. 배열과 달리 연속된 메모리가 아니다. 캐싱효율이 떨어진다.

 

더미노드를 사용하여 구현하자 더미노드를 사용하는 것이 이득이다

 

3가지 종류가 있다.

 

1. 단일 연결 리스트

[Data|Next] → [Data|Next] → [Data|null]

단방향 이동만 가능하다.

 

 

2. 이중 연결 리스트

null ← [Prev|Data|Next] ↔ [Prev|Data|Next] → null

양방향 이동이 가능하다

 

 

3. 원형 연결 리스트

[Data|Next] → ... → [Data|Next] ↻ (다시 첫 노드로)

마지막 노드의 Next가 처음 노드를 가리킨다

 

 

장점

1. 동적 메모리 사용

크기를 동적으로 조절 가능하다. 배열처럼 미리 공간을 정할 필요가 없다

 

2. 중간 삽입, 삭제가 빠르다

포인터 다발만 교체해주면 되므로 O(1)시간에 가능하다.

 

3. 메모리 낭비 적음

요소 개수만큼만 공간을 차지한다.

 

 

단점

1. 랜덤 접근 불가

인덱스로 바로 접근이 불가하므로 탐색에 O(n) 시간이 걸린다

 

2. 포인터 오버헤드

각 노드마다 포인터 추가 공간이 8~16가 필요하므로 단일 노드에 메모리 할당이 크다

 

3. 탐색느림

원하는 위치까지 랜덤 접근이 불가하고 일일히 옮겨가야하므로 탐색에 불리하다.

 

 

연결기반 리스트는 캐시효율이 떨어진다.

 

캐시효율이란?

CPU는 메인 메모리(RAM)보다 훨씬 빠른 캐시(Cache)를 사용하여 데이터 접근 속도를 향상시킨다. 

배열기반은 연속적으로 메모리 배치가 되므로 공간지역성이 존재하고 캐시효율이 높다.

연결리스트기반은 연속적으로 데이터가 있는게 아니라 포인터로 노드를 연결하므로 캐시효율이 낮다.