3.2 연결리스트와 list
연결리스트는 보관하는 자료마다 별도의 노드에 보관하며 노드에 링크를 이용해 논리적으로 선형을 유지하는 자료구조입니다. 따라서 연결리스트를 노드의 선형 집합이라고 말합니다.
배열은 자료를 보관하는 메모리가 연속적인 형태를 지녀 순차리스트라 부르는 순차 자료구조입니다. 이에 반해 연결리스트는 자료 하나를 보관하는 노드마다 별도의 메모리를 할당하여 실제 메모리는 불연속적인 형태입니다. 따라서 연결리스트는 순차 자료구조가 아닙니다.
하지만 노드는 자료와 링크로 구성하는데 링크를 통해 연결리스트를 구성하는 노드들의 논리적인 구조를 선형의 모습으로 표현할 수 있습니다. 이러한 이유로 연결리스트를 선형 자료구조라 말하는 것입니다.
링크는 노드의 위치 정보를 말하며 노드에 링크가 하나인 연결리스트를 단일 혹은 단순 연결리스트라고 부릅니다. 그리고 노드에 링크가 두 개 있어 앞쪽 노드의 위치와 뒤쪽 노드의 위치를 알 수 있게 만든 것을 이중 연결리스트라 부릅니다. 또한 맨 마지막 노드의 링크가 맨 앞 노드를 가리키는 연결리스트를 원형 혹은 환형 연결리스트라 부릅니다.
STL에서는 이와 같은 연결리스트를 list 템플릿 클래스로 제공하고 있습니다.
여기에서는 간략하게 연결리스트를 이해하기 위한 수준으로 만들어 본 후에 STL에서 제공하는 list 사용방법을 프로그래밍 실습을 통해 알아볼 거예요.
이 후에 STL에 vector를 모델로 자신의 vector를 만들고 난 후에 STL에 list를 모델로 자신의 list를 만들기로 할게요.
'언어 자료구조 알고리즘 > [C++]디딤돌 자료구조와 알고리즘' 카테고리의 다른 글
| 3.4 큐(Queue) [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
|---|---|
| 3.3 스택(Stack) [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 3.2.3 list 사용 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 3.2.2 이중 연결리스트 만들기 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 3.2.1 단순 연결리스트 만들기 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 3.1.5 vector를 인덱스 연산으로 사용 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 3.1.4 vector에 특정 키 순으로 보관 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 3.1.2 vector에 순차적으로 보관 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 3.1.1 이 책에서 공통으로 사용하는 것들 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 3.1 배열과 vector [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |