연결 리스트

장점: 리스트의 중간 지점에서도 자료의 추가와 삭제하는 속도가 빠름

단점: 특정 위치의 데이터를 검색하는 데에, 배열에 비해서 시간이 더 소요됨

 

<종류>

이중 연결 리스트(doubly linked list)

: 두 개의 포인터 존재, 한 개는 이전 노드 또 한 개는 다음 노드 가리킴

 

원형 연결 리스트(circular linkde list)

: 한 개의 포인터 존재, 다음 노드를 가리키고 있고 마지막 노드의 포인터는 처음 노드 가리킴

 

<list 컨테이너> 더블링크드리스트 형태

*멤버 함수(배열의 멤버함수들과 비슷 )

swap(list& l); //리스트의 모든 노드를 리스트 l과 교환

splice(const_iterator pos, list& l); //리스트 l의 모든 노드를 지정한 위치에 삽입(이어붙이기)

remove(const value_type& val); //리스트에서 val과 동일한 모든 노드 삭제

unique(); //리스트에서 인접한(양옆의) 중복되는 노드를 하나를 제외하고 삭제

reverse(); //리스트의 노드가 연결된 순서를 역으로 변경

sort(); //리스트의 모든 노드를 오름차순으로 정렬

merge(list& l); //리스트에 내부로 리스트 l의 모든 노드를 merge sort를 수행하며 복사

**두 리스트가 모두 반드시 정렬된 상태여야 merge 가능 (안그러면 런타임 에러 발생)**

***iterator 생성 시 list<int>:: iterator it; 처럼 namespace 명시해야 생성 가능***