list

vector와 대부분 비슷한 기능이 구현되어있다.

vector와의 차이점?

vector - 동적 배열

list - 이중 원형 연결 리스트

원형 연결 리스트라고 했지만 실제로 동작은 이중 연결 리스트와 같이 동작한다.

원형 연결 리스트의 경우 마지막 노드가 첫 번째 노드와 연결된 형태이다. 하지만 list에서는 마지막 노드로 더미 노드를 두어 마지막이 어디인지 체크함과 동시에 그 다음으로 넘어가는 것을 막아두었다. 즉, 코드로 보면 아래와 같다.

list<int> li;
li.push_back(1);
li.push_back(2);
li.push_back(3);

list<int>::iterator itBegin = li.begin(); // 1
list<int>::iterator itEnd = li.End(); // 마지막을 가리키는 노드 [DummyNode]

// li의마지막데이터 [3] <-> itEnd <-> liBegin [1]  => 원형 이중 연결 리스트의 형태지만
itEnd++; => liBegin이어야 하지만 막혀있다!
itEnd--; => DummyNode의 이전값 3
liBegin--; => DummyNode를 가리키게 될 것 같지만 실제로는 막혀있다!

 

list의 경우 vector와 다르게 노드로 구성되어 있고 간단하게 표현하면 아래 코드와 같이 구성되어 있다고 할 수 있다. 다음과 이전의 노드를 포인터로 들고있어 다음 노드로 이동하기 위해서 포인터의 주소를 활용하여 이동하는데 만약 데이터를 삽입할 경우 포인터들의 주소만 변경해주면 되니 처음, 중간, 삽입 삭제가 빠른편이다.

class Node
{
public:
	Node* _next;
	Node* _prev;
	int _val;
};

 

하지만 vector와 달리 임의 접근같은 경우 상대적으로 느릴 수 밖에 없다. vector는 동적 배열이고 요소들이 연달아서 저장되어 있기 때문에 빠르게 접근이 가능하지만, list의 경우 다음 노드의 주소를 확인하고 그 주소로 이동하는 작업은 상대적으로 느릴 수 밖에 없다. 그러면 만약 n번째 데이터를 삽입/삭제 한다고 가정했을 때 의문점이 하나 든다.

n번째 데이터 삽입/삭제 과정

1. n번째 노드를 찾는다.
2. n - 1번째 노드의 주소와 n + 1번째 노드 주소를 삽입/삭제할 노드와 연결하거나 해제한다.

위 두 단계를 거치면서 2번은 vector와 달리 배열을 복사하거나 하는 과정이 필요가 없으므로 빠르게 동작하는게 맞다. 하지만 1번은? vector가 훨씬 빠르게 동작할 것이다. 여기서 알 수 있는 것이 list의 삽입/삭제가 빠른 것은 맞지만 임의 접근이 느리므로, 해당 노드의 주소를 알고있을 때가 전제가 되어야한다는 것이다.

list<int>::iterator it = li.begin();
list<int>::iterator specialIt;
for (int i = 0; i < 100; i++)
{
	if (i == 50)
		specialIt = li.insert(it++, i + 1);
	else
		li.insert(it++, i + 1);
}
li.erase(specialIt);

 

list는 push_back으로 데이터를 삽입 할 수도 있지만, insert를 통해 삽입하면 iterator를 반환하고 이 iterator를 따로 저장하고 있다가 그 iterator를 활용하여 삽입/삭제를 할 수 있다. 따라서 삽입/삭제의 속도와 임의 접근의 속도를 구분해서 알아야 할 필요가 있다.