[자료구조와 STL] 13. list (연결리스트)

3. list (연결리스트)

 

 STL에서 제공하는 선형 컨테이너에는 vector 와 list가 있는데 연결 리스트를 표현한 것입니다. 연결 리스트는 노드들의 선형 집합이며 노드는 데이터와 링크의 조합입니다. 연결 리스트는 자료를 보관할 때마다 별도의 노드를 생성하여 하나의 노드에 하나의 자료를 보관하며 노드의 링크를 통해 노드들이 서로의 위치를 선형적으로 유지하는 자료구조입니다.

 

[그림 7] 연결 리스트 구조

 

 연결 리스트는 링크의 개수에 따라 하나만 있는 단일(혹은 단순)연결 리스트, 두 개가 있는 이중 연결 리스트로 나눌 수 있습니다. 그리고 마지막 노드가 시작 노드의 위치 정보를 알고 있게 링크를 설정하는 연결 리스트를 원형 연결 리스트라 합니다. 이처럼 링크의 개수나 유형에 따라 연결 리스트를 구분하지만, 이는 연결 리스트를 만드는 개발자에 관련된 사항일 뿐 사용하는 개발자는 큰 의미를 있지는 않습니다.

 

 STL에서 제공되는 list는 이중 연결 리스트로 되어 있습니다. 그리고 list는 vector와 제공되는 멤버들이 대부분 비슷합니다. 차이가 있는 부분은 인덱스 연산자([ ])를 사용할 수 없다는 것입니다. vector는 요소들을 보관하는 저장소가 연속된 메모리 하나로 되어 있으므로 저장소 시작 주소에서 상대적 거리를 계산하는 것이 효과적이지만 list에서는 각 요소가 별도의 노드에 보관되기 때문에 인덱스 연산자를 제공하지 않습니다. 또한, 저장소의 용량을 갱신하기 위해 제공했던 reserve 메서드와 용량을 얻어오기 위한 capacity 메서드를 제공하지 않습니다. 그렇지만 여전히 resize 메서드와 size 메서드는 제공하고 있습니다. list를 사용하는 방법은 vector를 사용하는 방법과 큰 차이가 없어서 이 책에서는 list를 사용하는 방법에 대해서는 별도로 논의하지 않겠습니다. 여기에서는 STL에서 제공되는 list와 비슷한 구조를 갖는 템플릿 클래스를 구현하는 것과 list와 vector를 이용하는 간단한 응용을 만들어 보기로 합시다.