2.2연결 리스트 구현

이제 노드를 이용해 연결 리스트를 구현해 보겠습니다. 연결 리스트에는 여러 종류가 있습니다. 단일 연결 리스트의 노드에는 참조가 하나만 있습니다. 한 방향만 참조하므로 단인 연결 리스트라고 부릅니다. 이중 연결 리스트의 노드에는 다음 노드를 가리키는 참조와 이전 노드를 가리키는 참조가 있습니다. 그래서 이름이 이중 연결 리스트입니다. 이중 연결 리스트는 힙 세그먼트를 구현하는 큰 틀을 제공합니다. 이 책에서는 단일 연결 리스트를 구현해 보겠습니다. 먼저 단일 연결 리스트의 구조를 그림으로 살펴봅시다(그림 12-30).

그림 12-3 단일 연결 리스트

단일 연결 리스트 클래스의 멤버는 연결 리스트의 첫 번째 데이터를 가리키는 head, 마지막 데이터를 가리키는 tail, 리스트에 저장된 데이터의 개수를 나타내는 d_size로 구성됩니다.