정의
- list는 스택, 큐와 같이 선형 자료구조이다.
- 스택, 큐는 접근이 전단이나 후단에 제한되어 있는 것과 달리, 리스트는 임의의 위치에서도 삽입과 삭제가 가능하다. 즉, 자료 중간에 자료를 삽입, 삭제가 가능하다.
시간 복잡도
- list는 삽입과 삭제에 O(1) 복잡도를 가진다.
(단, 삽입/삭제하고 싶은 위치의 주소를 알고 있을 경우)
- n번째 원소에 접근할 때 O(n) 복잡도를 가진다.
list 기본 함수
추가 및 삭제
- insert(iterator, element): iterator 위치에 새로운 item을 삽입
- assign(size, element): 원소를 size 할당
- erase(iterator): iterator 위치에 있는 요소를 삭제
- clear(): 리스트의 모든 요소를 삭제
- replace(iterator, element): iterator 위치에 있는 요소를 새로운 item으로 바꿈
- push_front(element): 리스트 제일 앞에 원소 추가
- pop_front(): 리스트 제일 앞 원소 삭제
- push_back(element): 리스트 제일 뒤에 원소 추가
- pop_back(): 리스트 제일 뒤에 원소 삭제
조회
- getEntry(pos): 리스트의 pos 위치에 있는 요소를 반환
- find(item): 리스트에 요소 item이 있는지 확인
- display(): 리스트 안의 모든 요소 출력
- *iterator: iterator가 가리키는 원소 접근
기타
- isEmpty(): 리스트가 비어있는지 검사
- isFull(): 리스트가 가득 차 있는지 검사
- size(): 리스트 안의 요소의 개수 반환
::iterator
- begin(): 맨 앞의 원소를 가리키는 iterator 반환
- end(): 맨 뒤의 다음 원소를 가리키는 iterator 반환
- rbegin(): 맨 뒤의 원소를 가리키는 iterator 반환, 기본 iterator과 달리 뒤에서부터 순차적으로 접근할 때 사용
- rend(): 맨 앞 이전 원소를 가리키는 iterator 반환
임의 접근
- front(): 첫번째 원소를 반환
- back(): 마지막 원소를 반환
vector와의 차이점
1) 메모리 할당
- vector는 미리 일정 크기의 메모리를 할당해놓고 그 이상의 값들이 추가되면 새로운 더 큰 메모리를 할당한다.
- list는 값을 넣을 때마다 메모리를 할당하게 된다.
2) 메모리 사용량
- list의 각 요소는 포인터로 연결되어 있으므로 메모리 상에 연속적으로 존재하지 않아도 된다.
- vector는 연속적인 주소에 할당되므로 next의 주소 등의 변수들을 가지고 있을 필요가 없어 list보다 적은 메모리를 사용한다.
3) vector와 list를 사용하는 경우
- 순서와 상관없이, 순차적으로 추가, 삭제되면 vector 사용이 효율적
- 중간에 값이 추가, 삭제되면 list 사용
참고 사이트
https://luv-n-interest.tistory.com/962
