Linked List
링크드 리스트는 연속된 메모리를 포기하는 대신 삽입/삭제에 따른 복사 비용을 줄이는 것에 초점을 둔 컨테이너다.
장단점이 Vector와 거의 정반대에 가깝다.
각 원소는 데이터와 다음 원소의 주소를 가지고 있으며, 이 한 쌍을 노드라고 부른다.
노드와 노드를 연결하여 사용하는 방식이다.
// node structure
template<typename T>
stuct Node
{
data T;
Node* next;
}
// example
Node a, b;
a.next = &b;링크드 리스트는 연속된 메모리를 사용하지 않기 때문에 아래와 같은 특징이 있다.
- 중간 삽입/삭제 로직만은 복사 비용이 없음
특정 노드를 찾는데까지 O(n)이 걸리기 때문에 특정 노드를 찾으면 포인터를 이용해 상수 시간에 끝낼 수 있다. - 크기 변경이 굉장히 자유로움
그에 반해 단점은 아래와 같다.
- 캐시 효율이 안 좋음
노드의 메모리들이 여기저기에 흩어져 있어서 지역성이 굉장히 나쁘다.
그래서 CPU의 캐시 라인을 거의 활용하지 못한다. - 인덱스 기반 접근 불가능
순차 탐색으로 항상 O(n)의 복잡도를 가진다. - 추가 메모리(포인터) 존재
정말 필요한 데이터 외에도 포인터를 필수적으로 가져야한다. - 외부 메모리 단편화 발생 가능
노드들이 개별적으로 할당되므로, 실제 메모리는 충분함에도 연속적이지 못하여 할당을 받을 수 없는 경우가 생길 수도 있다.
시간 복잡도
단일 링크드 리스트를 기준으로 한다.
- 탐색, 접근 : O(n)
첫 노드부터 하나씩 따라가야하므로 for문과 다를게 없는 O(n) - 삽입 / 삭제(특정 노드를 알 고 있을 때) : O(1)
포인터의 연결만 바꾸면 되는 상수 시간 복잡도를 가진다.
특정 노드를 모를때는 어쩔 수 없이 순회가 필요한데, 이 경우에는 O(n)이 되기도 한다.
언제 사용해야 하는가
- 삽입/삭제의 노드를 알고 있을 때, 삽입/삭제가 활발할 경우
- 원소의 순서가 자주 바뀔때
- 순차 접근 위주
언제 피해야 하는가
- 인덱스 접근이 필요한 경우
- 캐시 효율이 중요한 경우
- 빈번히 순회하는 경우
- 데이터 크기가 큰 경우
- 성능이 중요한 경우
그래서 게임에서는 잘 안쓰이는 것 같다..
정리
랜덤 접근이 불가능하고, 캐시 효율이 나쁘기 때문에 성능부분에서 기대하기는 힘들다.
그래서 사실 사용한 적이 한 번도 없다... 진짜 쓸 상황이 안 생겼다.....!
그러면 왜 아직도 이 리스트가 레거시되고 있지 않는 이유가 궁금했는데,
바로 다른 시스템과 결합된 형태로 많이 사용된다고 한다.
- intrusive list
- free list
- LRU cache
각 부분은 나중에 알아보겠다.
구현
노드
template<typename T>
struct Node
{
T data;
Node* next;
};데이터와 연결된 노드를 저장할 포인터 2가지로 이루어진 기본 노드 구성
멤버 변수
private:
Node<T>* m_head;
size_t m_size;리스트의 시작 부분 포인터와 크기가 정의된다.
탐색
Node<T>* find(const T& value) const
{
// Head부터 순차 탐색한다.
Node<T>* cur = m_head;
while (cur)
{
if (cur->data == value)
return cur;
cur = cur->next;
}
return nullptr;
}
삽입
먼저 가장 앞에 삽입하는 경우다.
void push_front(const T& value)
{
// 삽입될 노드 생성
Node<T>* node = new Node<T>(value);
// 노드의 다음을 head로 연결
node->next = m_head;
// 시작점을 삽입 된 노드로 변경
m_head = node;
// 크기 갱신
++m_size;
}
그 후 중간에 삽입하는 경우다.
template<typename T>
bool push(size_t index, const T& value)
{
// 찾으려는 인덱스가 존재하는 데이터 개수보다 많은 경우 종료
if (index > m_size)
return false;
// 맨 앞에 넣을 경우 push_front호출
if (index == 0)
{
push_front(value);
return true;
}
// Head부터 index - 1 까지 순차 탐색
Node<T>* cur = m_head;
for (size_t i = 0; i < index - 1; ++i)
{
cur = cur->next;
}
// 삽입하려는 노드 생성
Node<T>* node = new Node<T>(value);
// 삽입하려는 노드 앞 뒤로 연결
node->next = cur->next;
cur->next = node;
++m_size;
return true;
}중간에 순차 탐색할 때 index - 1을 하는 이유는 뒤에 있는 노드는 알 수 없기 때문이다.
마지막에 삽입하는 경우는 생략한다.
삭제
일반적인 삭제 로직에서는 삭제할 노드가 첫 번째 노드일 때와 중간 노드일 때의 처리가 다르다.
해당 방식을 동일하게 처리하고자, head 앞에 빈 공간인 dummy노드를 이용했다.
bool remove(const T& value)
{
// stack으로 head의 앞에 빈 공간을 만든다.
Node<T> dummy;
dummy.next = m_head;
Node<T>* cur = &dummy;
// value값을 가진 노드의 이전 노드를 찾는 과정
while (cur->next)
{
if (cur->next->data == value)
{
// 지울 노드를 저장 후 삭제 처리
Node<T>* delTarget = cur->next;
cur->next = delTarget->next;
delete removeVal;
// 혹시 Head를 지웠을 경우의 대비
m_head = dummy->next;
// 사이즈 갱신 후 종료
--m_size;
return true;
}
cur = cur->next;
}
return false;
}
제일 깔끔한 방법으로는 double pointer를 사용하는 방법도 있다. (근데 좀 헷갈림;)
bool remove(const T& value)
{
// head를 가리키는 포인터의 주소
Node<T>** pp = &head;
while (*pp)
{
if ((*pp)->data == value)
{
// delTarget = 삭제해야하는 노드
Node<T>* delTarget = *pp;
// 포인터 자체를 교체!
*pp = delTarget->next;
delete delTarget;
--m_size;
return true;
}
pp = &((*pp)->next);
}
return false;
}간단하게 설명하면 pp는 처음에는 노드 그자체를 가리킨다.
하지만 pp = &((*pp)->next); 실행 후 부터는 노드의 next를 가리키는 포인터가 된다.
즉, 사실상 이전 노드라고 생각하는게 편할 수도 있다.