STL list 정리

c++에서의 list는 연결리스트를 의미함

배열과 달리 "각각의 데이터가 일자로 쭈~욱" 있는게 아니라 "메모리상에 따로 떨어져" 있어도 노상관

 

list의 종류

- 연결 리스트

[ node ] --> [ node ] --> [ node ] --> [ node ]

- 이중 연결 리스트

[ node ] <---> [ node ] <---> [ node ] <---> [ node ]

- 원형 연결 리스트

[ tail ] <---> [ node ] <---> [ node ] <---> [ header] <---> [ tail ]

 

node 안의 정보

- 연결 리스트

현재 노드에 담겨 있는 데이터와 다음 노드의 주소

 

- 이중 연결 리스트

현재 노드에 담겨 있는 데이터와 다음 노드의 주소와 이전 노드의 주소

 

- 원형 연결 리스트

현재 노드에 담겨 있는 데이터와 다음 노드의 주소와 이전 노드의 주소 ( 리스트의 시작과 끝이 연결 되어있음 )

 

 

삽입/ 삭제의 속도

list는 삽입과 삭제의 속도가 좋은편임

데이터 삽입시 이전 노드 주소와 다음 노드 주소만 세팅해주면 끝

삭제시에도 주소만 세팅하고 delete해주면 되기 때문에 굉장히 빠르다고 할 수 있음

 

하지만 조건이 하나 있음 

그것은 삽입하려는 위치에 있는 node를 따로 가지고 있어야함

그렇지 않으면 그 위치를 찾으러 한칸한칸 거슬러 올라가야 하기 때문..