링크드리스트

종류

1. 싱글리 (단일)
2. 더블리 (이중)
3. 서큘러 (원형)

배열 vs 링크드리스트

• k번쨰 원소의 접근 : O(1) / O(k)

• 임의 위치에 원소 추가 제거 : O(n) / O(1)

• 메모리 상의 배치 : 연속 / 불연속

• 추가적으로 필요한 공간(Overhead) : x / O(n) => 싱글리 : 다음원소의 주소, 더블리 : 이전,다음원소의 주소

구현

• 구조체, 포인터를 활용하는 방법 => 기술면접
• STL list => 코딩테스트

STL list

int main(void)
{
  list<int> l = {1,2}; // 1 2 
  list<int>::iterator t = l.begin();  // auto t = l.begin(); 가능
  l.push_front(10);  // 10 1 2 
  cout << *t << '\n'; // t가 가리키는 값 1을 출력
  t++;
  l.push_back(5); // 5
  l.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입.  10 6 1 2 5
  t++; // 2 를 가리킴
  t = l.erase(t);
  cout << *t << '\n';
  for(auto i : l)
    cout << i << ' ';
  cout << '\n';
  
  for(list<int>::iterator it = l.begin(); it != l.end(); it++)
    cout << *it << ' ';
}