[algorithm] 연결 리스트(Linked list)

연결리스트?

원소들을 저장할 때 데이터와 그 다음 원소의 위치를 포함하여 저장하는 자료구조이다

연결리스트는 실제 메모리 공간에서 아무런 규칙없이 저장되기에

각 node가 다음 원소의 위치를 화살표로 연결시켰다고하면 이해하기 쉽다

 

각 노드가 두개로 분리되어있는 이유는

데이터를 저장하는 변수와 다음 데이터를 가리키는 포인터 변수로 구성되어있기 때문이다

 

연결리스트의 성질만 우선 나열해보자면

1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함

2. 임의의 위치에 원소를 추가/제거는 O(1)가 필요함

 

배열과 비교하면

1. k번째 원소를 확인/변경 위해 O(1) 필요함

2. 임의의 위치에 원소를 추가/제거는 O(k)가 필요함

 

연결리스트는 2번 성질이 가장 큰 장점이고

연결리스트를 사용하는 이유이다

 

하지만 인덱싱이 불가능하다는 단점이 있다

 

연결리스트는

단일 연결리스트 / 이중 연결리스트 / 원형 연결리스트 등의 종류가 있다

이중 연결리스트는 각 노드가 다음 원소의 위치와 이전 원소의 위치 모두를 들고 있다

STL list로 연결리스트를 구현 시 이중 연결리스트로 나타난다

 

원형 연결리스트는 리스트의 끝이 처음과 연결되어 있어 순환되는 구조다

 

STL list로 연결리스트를 사용할 수 있다

int main(void) {
  list<int> L = {1,2}; // 1 2
  list<int>::iterator t = L.begin(); // t는 1을 가리키는 중
  L.push_front(10); // 10 1 2
  cout << *t << '\n'; // t가 가리키는 값 = 1을 출력
  L.push_back(5); // 10 1 2 5
  L.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입, 10 6 1 2 5
  t++; // t를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
  t = L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 반환
                  // 10 6 1 5, t가 가리키는 값은 5
  cout << *t << '\n'; // 5
  for(auto i : L) cout << i << ' ';
  cout << '\n';
  for(list<int>::iterator it = L.begin(); it != L.end(); it++)
    cout << *it << ' ';
}

 

각각에 노드에 접근하려면 인덱싱이 안되므로 iterator를 선언해서 접근해야하며

iterator를 역참조(de-reference)해서 해당 노드의 값에 접근한다

 

다음이나 이전 위치로 이동하려면 ++,-- 등으로 이동한다

여기서 ++,--는 1씩 더하고 뺀다는 의미가 아니라

다음/이전 노드가 있는 주소로 이동한다는 의미로 받아들여야 한다

 

추가로 list<int>::iterator i = l.begin() 이런식으로 선언하기 복잡하면

auto i = l.begin() 이런식으로도 가능하다

 

문제를 풀다보니 erase() 사용 시 반환값을 받아주지 않아서 오류가 났던 적이 많았다

erase() 함수 사용 시 다음 위치를 반환하므로

변수를 재할당해서 받아주는 것이 편하다