list

list는 vector와 비슷하게 데이터를 선형적으로 저장하는 컨테이너이다. 하지만 vector와는 다르게 내부 데이터가 하나의 메모리 공간에 연속적으로 나열된 것은 아니다.

list의 동작 원리

list는 노드라는 객체를 쭉 이어놓은 형태의 컨테이너이다. 여기서 노드란, 데이터를 가지고 있고, 다음으로 연결 되는 노드를 가르키는 포인터를 가지는 객체이다.

Node

노드는 보통 자료구조를 구현할때 필수적으로 사용되는 객체이다. list도 사실 이중 리스트, 연결 리스트 등의 자료구조를 컨테이너로 구현 해 놓은것인데, 이 또한 Node들을 이어놓은 형태이다.

Node는 일반적으로 내부에 data, nextNode, prevNode를 지닌다. data는 말그대로 데이터를 저장하고, next는 다음 노드의 주소값, prev는 이전 노드의 주소값이다.

template <typename T>
class Node{
public:
    Node() : _data(T()), _next(nullptr), _prev(nullptr){}
    Node(const T& data) : _data(data), _next(nullptr), _prev(nullptr){}
public:
    T _data;
    Node* _next;
    Node* _prev;
};

Node는 보통 위와 같은 형태로 구현되는데, 단순히 데이터를 저장하는 객체이기 때문에 비교적 단순한 구조를 지닌다.

list의 원소 삽입과 삭제

list는 Node가 이어져 있는 형태이기 때문에 중간에 원소를 삽입하거나 삭제하는 동작의 성능이 좋다. 이는 단순이 Node 내부의 포인터들이 가르키는 Node의 정보만 바꾸어 주면 되기 때문이다.

하지만, 원소들이 메모리 공간에 순차적으로 나열되어 있는 것이 아니기 때문에 원소의 임의 접근이 불가능하다. 원하는 원소를 찾기 위해선 반드시 첫 원소부터 순회해서 원하는 원소를 찾아야 한다.

list에는 일치하는 원소를 모두 삭제해주는 remove 함수도 존재하는데, 이는 원소의 삭제가 효율적으로 동작 하기 때문에 존재하는 함수이다.

list의 반복자

list는 begin, end를 통해 처음과 끝 위치의 노드를 가르키는 반복자를 얻을 수 있다. list는 특이하게, 제일 마지막 노드 뒤에 header라는 더미 노드가 존재하는데, 이 노드는 다음 노드로 제일 첫 노드를 가르킨다. end를 통해 얻은 반복자는 제일 마지막 노드 다음의 노드인 header를 가르키는 반복자이다.

header는 list의 범위 체크를 용이하게 하는 역할을 한다. list를 반복자를 통해 순회 하다가 header를 만나게 되면, 해당 list의 마지막에 도달했다는 의미이다.

list의 반복자는 ++, --를 통한 증감 연산은 가능하지만, iter + idx 와 같은 연산은 불가능 하다. 이는 list가 vector와 같이 연속적으로 나열된 데이터가 아니기 때문에, +, - 연산자를 통한 반복자 연산은 비효울적으로 동작하기 때문이다.

list의 중간 삽입/삭제가 빠른 이유

list는 원소의 임의 접근이 불가능한데, 원소의 중간 삽입/삭제는 빠르다. 이는 원소의 중간 삽입/삭제를 하는 동작 자체가 빠르다는 의미이고, 원하는 원소의 반복자를 순차적으로 순회해서 찾은 과정은 빠르지 않다.

다시말해서 원하는 원소의 삽입 혹은 삭제하는 과정 전체가 빠른것이 아니고, 단순히 원소를 삽입/삭제하는 동작 자체가 빠르다는 것이다. 이러한 특징을 이용해서 빠른 삽입/삭제를 하기 위해선, insert, erase 작업 이후 반환된 반복자를 저장 해놓고, 해당 반복자를 이용하는 것이 효율적이다.