Page 340 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

09-2 포인터로 연결 리스트 만들기

이번 절에서는 다음 노드를 가리키는 포인터를 각 노드에 포함시키는 연결 리스트를 살펴보
겠습니다.

포인터로 연결 리스트 만들기
연결 리스트에 데이터를 삽입할 때 노드용 객체를 만들고, 삭제할 때 노드용 객체를 없애면

앞에서 제시한 데이터를 밀고 당기는 문제를 해결할 수 있습니다. 그림 9-4에 여기서 구현할
노드의 구조를 나타냈습니다.
구조체의 이름을 태그 이름 __node와 typedef 이름 Node처럼 두 가지 방법으로 정한 이유는 보충수업 9-1에서 설명
하겠습니다.

Node Node
typedef struct __node { data
Member data; /* 데이터 */ next
struct __node *next; /* 다음 노드를 가리키는 포인터 */
} Node; 자신과 같은 자료형의 객체를 가리킵니다.

[그림 9-4] 연결 리스트를 구현하기 위한 노드의 구조

이 구조체는 다음의 두 멤버, data와 next로 구성되어 있습니다.

1. data … 데이터를 저장하는 멤버입니다.
2. next … 자기 자신과 같은 구조체를 가리키는 포인터입니다.

이와 같이 자기 자신과 같은 자료형의 객체를 가리키는 데이터를 가지고 있는 자료구조를 자

기 참조(self-referential)형이라고 합니다. 그림 9-4처럼 멤버 next에 넣어두는 값은 해당 노
드의 다음 노드를 가리키는 포인터입니다. 다음 노드를 갖지 않는 꼬리 노드의 next 값은 널
(NULL) 값을 대입합니다. 앞으로 ‘다음 노드에 대한 포인터’를 뒤쪽 포인터라고 부르겠습니

다. 이제 노드의 자료형이 구조체 Node형인 연결 리스트 프로그램을 작성해 보겠습니다. 실
습 9-1은 헤더, 실습 9-2는 소스입니다.

340 C 알고리즘