9-4. STL - List (1)

벡터와 비슷하지만 차이점이 있으며 차이점에 대해서 명확히 알고 있어야 한다.

 

vector : 동적 배열. 연속된 공간을 할당받아 사용. 사이즈가 캐퍼시티를 초과하면 메모리를 확장 후 기존 데이터를 복사 붙여넣기 함. 임의 접근 가능.

 

 

1. list의 동작 원리

(1) 단일 연결 리스트

각 노드(데이터를 저장하는 칸)가 서로 다른 메모리 영역에 저장되어 있고 서로 어디에 있는지만 알 수 있도록 연결되어 있음.

 

이미 알고 있는 클래스에 비유하여 만들면 이렇게 나타낼 수 있다.

class Node
{
public:
    Node* _next; // 다음 노드의 주소를 담은 포인터, 노드 다음에는 노드가 있음(Node 형)
    int _data; // 각 노드의 값

};

노드(8 또는 12바이트) 안에서는 다음 노드의 주소를 가진 포인터(4 또는 8바이트)와 노드 자신의 데이터(int형 4바이트)를 가지고 있다.

 

(2) 이중 연결 리스트

노드 안에서는 이전 노드와 다음 노드의 주소를 가진 포인터들과 자신의 데이터를 가지고 있다.

 

 

(3) 원형 연결 리스트

노드 안에서는 다음 노드의 주소를 가진 포인터들과 자신의 데이터를 가지고 있다.

그리고 마지막 노드가 첫 노드를 가리키는 포인터를 가진다.

 

 

2. vector와 list의 차이 -> list에서는 ...

(1) push_front 지원

 

(2) capacity(용량)의 개념이 없음

 

(3) front와 back이 존재

 

(4) 임의 접근이 불가능 ( li[3] = 13; 같은 문법 불가능 )

 

(5) 반복자를 사용하지만 다르게 작동

 

(6) 첫 값을 제거하는 pop_front 사용 가능

 

(7) remove 기능 제공

li.remove(10); // 해당 값과 일치하는 모든 원소 삭제