[실전 알고리즘] 연결 리스트

정의와 성질

 

연결 리스트: 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조

연결리스트의 성질

1. k번째 원소를 찾기 위해 O(k)의 시간이 필요

2. 임의의 위치에 원소를 추가하거나 임의 위치의 원소 제거가 O(1)

3.  원소들이 메모리상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 쉬움

 

 

배열 vs 연결리스트

 

기능과 구현

STL의 List가 이중 연결 리스트

 

STL List 예시

#include <bits/stdc++.h>
using namespace std;

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 << ' '; //C++ 11 이상
  cout << '\n';
  for(list<int>::iterator it = L.begin(); it != L.end(); it++) //C++ 11 이전
    cout << *it << ' ';
}

 

 

 

 

 

 

 

참고

BaaaaaaaarkingDog | [실전 알고리즘] 0x04강 - 연결 리스트 (encrypted.gg)

[실전 알고리즘] 0x04강 - 연결 리스트