연결 리스트 (Linked list)

메모리 상에 띄엄띄엄 노드들이 위치하고 이들이 연결되어 있는 구조

• C++의 STL에는 있으나 Python에는 기본 자료형으로 없음 (필요하면 직접 구현해야 함)
• 배열과 반대되는 특성이 있음
• 삽입/삭제: $O(1)$
• 탐색: $O(N)$
  • 임의 접근(random access)이 불가능해서 탐색이 느림

• 배열의 경우 중간의 원소를 삭제하거나, 값을 삽입할 때 굉장히 비효율적이다.
• 하지만 연결 리스트는 원소의 삽입 및 삭제가 빈번한 문제에서 유리하다.

헤더

#include <list>

생성자

list lt

• 비어있는 list 컨테이너 lt 를 생성합니다.

list lt(10)

• default(0)값으로 초기화 된 원소 10개를 가진 list를 생성합니다.

list lt(3, 2)

• 2값으로 초기화 된 원소 3개를 가진 list를 생성합니다.

list lt2(lt1)

• list lt1을 lt2로 복사합니다

멤버 함수

lt.begin()

• 맨 앞의 원소를 가리키는 iterator를 반환합니다.

list<int>::iterator iter;
iter = lt.begin();

lt.end()

• 맨 마지막의 다음 원소를 가리키는 iterator를 반환합니다.

list<int>::iterator iter;
iter = lt.end();

lt.insert(iter, k)

• iter가 가리키는 부분의 앞(이전)에 원소 k를 삽입합니다.
• 삽입한 원소를 가리키는 iterator를 반환합니다.

lt.erase(iter)

• iterator가 가리키는 원소를 삭제합니다.
• 반환값은 삭제한 원소의 다음 원소를 가리키는 iterator를 반환합니다.

lt.size()

• 원소의 개수를 반환합니다.

lt.remove(k)

• k 와 같은 원소를 모두 제거합니다 (편리..)

lt.remove_if(Predicate)

• 단항 조건자 predicate에 해당하는 원소를 모두 제거합니다 (더! 편리..)

lt.sort()

• 모든 원소를 default(오름차순) 으로 정렬합니다.
• 소트의 파라미터로 이항조건자가 올수 있습니다. 그때는 그 기준으로 정렬합니다.

lt.unique()

• 인접한(양옆의) 원소가 같으면 유일하게 만듭니다.(하나만빼고 삭제)

lt.push_back(k)

• 뒤쪽으로 원소 k 를 삽입합니다.

lt.push_front(k)

• 앞쪽으로 원소 k 를 삽입합니다.

lt.pop_back()

• 맨 마지막 원소를 제거합니다.

lt.pop_front()

• 맨 첫번째 원소를 제거합니다.

출처: https://blockdmask.tistory.com/76 [개발자 지망생]

https://blockdmask.tistory.com/76