9-5. STL - List (2)

Crat3 ㅣ 2023. 6. 14. 18:45

이중 연결 리스트를 중점에 둔다.

list는 데이터가 연속적으로 존재할 필요가 없기 때문에 vector에 비해 삽입과 삭제가 효율적으로 작동한다.

1. 중간 삽입 / 삭제

vector에서는 중간 삽입을 위해 삽입 위치의 오른쪽 값들을 한 칸씩 복사 붙여넣기하는 비효율적 과정이 필요했으나

list에서는 보다 효율적으로 작동하게 된다.

중간에 노드를 추가하고 이전 노드와 다음 노드의 포인터를 가지게 한다.

2. 처음과 끝 삽입 / 삭제

list에서는 처음과 끝에 노드를 삽입하거나 삭제할 때 포인터에만 유의하면 된다.

3. 임의 접근 ; i번째 데이터에 접근하기(불가능)

vector와 다르게 불연속적이고 capacity의 개념이 없기 때문에 임의 접근이 어려움.

(노드에서 다른 노드로, 다른 노드에서 또 다른 노드로 이동해야하기 때문)

4. Head 노드와 Tail 노드

(1) Head 노드

리스트의 첫 번째 노드를 가리키는 포인터. 데이터를 가지지 않으며 직접 접근이 불가능하다.

(2) Tail 노드

리스트의 마지막 노드를 가리키는 포인터. 데이터를 가지지 않으며 직접 접근이 불가능하다.

(3) 반복자 활용

마지막을 가리키는 반복자에 증가 연산자를 적용하면 오류가 발생한다.

또한 반복자에 어떤 숫자를 더하는 것 또한 오류가 발생한다.

5. 임의 접근은 불가능한데 중간 삽입 / 삭제는 빠르게 작동한다??

50번째 인덱스에 있는 데이터를 삭제하는 코드를 구상해보자.

list<int>::iterator it = li.begin;
for (int i = 0; i < 50; i++)
	++it;
    
li.erase(it);

erase 문법은 빠르게 작동하지만 it를 49번 증가시키는 과정은 느리게 작동한다.

즉 데이터를 제거하는 것 자체는 빠르다는 것이고

그 데이터를 찾기 위해 반복자를 증가시키는 것은 느리다는 것이다.

=> 몇 번째 데이터(반복자를 증가)를 삭제(erase)하는 것은 느리다는 것이다!!

Crat