Linked List

특징

노드 컨테이너로 이루어져 있다

 

탐색의 경우 처음부터 끝까지 하나씩 탐색해야하기 때문에 O(n)

=>인덱스를 지원하기 하지 않기 때문에 랜덤한 접근이 불가능하다

 

데이터의 어느곳이든지 삽입 삭제가 빠르다 O(1)

=>순서 변경도 마찬가지

 

컨테이너의 크기가 고정이 아닌 동적으로 이루어진다

 

근데 이 또한 vector처럼 동적할당으로 이루어지는데

자주 크기가 조정 될 시에 메모리단편화라는 단점이 거론되지 않는가 궁금했다.

추측인데 vector는 데이터가 메모리에 연속적으로 있어야 하지만

List는 각 데이터 하나 하나가 꼭 붙어 있지 않아도 되기에 미리 나누어져있는 메모리를 할당받을 확률이 높다고 생각한다.

 

※캐시라인이라는 개념으로 vector와 비교되는데 나중에 다시 찾아보기

---

결론

 

연결 리스트도 vector와 마찬가지로 가변성이 가장 큰 특징이라 생각이 들어

vector와 차이를 많이 못느꼈었는데

 

어느곳에서나 데이터의 삽입 삭제에 빠르며 메모리의 크기 조정 또한 빠르다

"변화에 강함" 이게 핵심인거 같다.

 

---

사용처

 

[작성중]

그 아이템 뺑뺑이 돌아가는거