연결 리스트란 원소를 저장할 때 그 다음 원소의 위치를 포함하는 방식으로 저장하는 자료구조이다. C++ STL에서는 list<>로 사용할 수 있고, 이는 이중 연결 리스트이다.
연결 리스트의 성질
- O(K)에 K번째 원소를 확인, 변경할 수 있다.
- O(1)에 임의의 원소를 추가, 삭제할 수 있다. 이 성질이 연결 리스트의 가장 큰 장점이자, 사용 이유이다.
- 이전, 이후 원소의 주소를 가리키는 포인터와 같은 추가적으로 소모되는 메모리 오버헤드가 O(N)으로 존재한다.
- 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만, 할당이 다소 쉽다.
연결 리스트의 종류
- 단일 연결 리스트: 각 원소가 자신의 다음 원소의 주소를 가지고 있다.
- 이중 연결 리스트: 각 원소가 자신의 이전, 다음 원소의 주소를 가지고 있다.
- 원형 연결 리스트: 리스트의 마지막 원소와 첫번째 원소가 연결되어 있다.
STL list의 멤버 함수
- list 선언
- list<변수 타입> 이름
- list 접근
- front(): list의 첫 번째 원소에 대한 참조를 반환한다.
- back(): list의 마지막 원소에 대한 참조를 반환한다.
- begin(): list의 첫 번째 원소를 가리키는 iterator(반복자)를 반환한다.
- end(): list의 마지막 원소의 다음을 가리키는 iterator(반복자)를 반환한다.
- list 삽입/삭제
- push_back(value): 리스트의 맨 뒤에 원소를 삽입한다. O(1)
- push_front(value): 리스트의 맨 앞에 원소를 삽입한다. O(1)
- pop_back(): 리스트의 맨 뒤의 원소를 삭제한다. O(1)
- pop_front(): 리스트의 맨 앞의 원소를 삭제한다. O(1)
- insert(iter, value): 지정된 반복자 위치에 원소를 삽입한다. O(1)
- erase(iter): 지정된 반복자 위치의 원소를 삭제한다. O(1)
- remove(value): 특정 값과 같은 원소를 전부 삭제한다.
- clear(): 리스트의 모든 원소를 삭제한다.
- list 정보
- empty(): 리스트가 비어 있으면 true를 반환한다.
- size(): 리스트의 원소 개수를 반환한다.
사용 예시
임의의 위치에 원소를 삽입, 삭제하는 시간 복잡도가 O(1)인 특징이 연결 리스트의 가장 큰 장점이다. 따라서 임의의 위치에 원소를 삽입, 삭제하는 연산이 많은 프로그램을 짤 때 연결 리스트를 사용한다.
대표적인 예시로는 텍스트 에디터인데, 임의의 커서의 위치에 텍스트를 삽입, 삭제해야 하므로 연결 리스트를 사용한다.
