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

노드(head node), 꼬리 노드(tail node)라고 합니다. 또한 하나의 노드에 대해 바로 앞에 있는

노드를 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드를 다음 노드(successor node)라고 합
니다. 그림 9-2를 보면 노드 C의 앞쪽 노드는 노드 B이고, 다음 노드는 노드 D입니다. 이때
노드 C가 갖는 포인터는 다음 노드인 D를 가리킵니다.

배열로 선형 리스트 만들기

전화번호부를 선형 리스트로 저장하기 위해 간단한 배열로 구현하고 그림으로 나타내 보았
습니다(그림 9-3). 요소의 자료형이 Person인 배열 data의 요소 개수는 7개입니다. 즉, 최대 7
명의 회원 데이터를 삽입할 수 있습니다.

typedef struct { /*--- 회원 ---*/ a 삽입 전 b 삽입 후
int mem_no; /* 회원번호 */
char *name; /* 이름 */ ０ 12 12
char *phone; /* 전화번호 */ １ 33 55  삽입
/* … */ ２ ３ 57  33
57
69
} Person;
４ 41 69
５ 0 41
Person data[] = { ６ 0 0
{12, "John", "999-999-1234"},
{33, "Paul", "999-999-1235"},
{57, "Mike", "999-999-1236"}, 삽입한 위치 이후의 모든 요소를
{69, "Rita", "999-999-1237"}, 하나씩 뒤로 옮깁니다.
{41, "Alan", "999-999-1238"},
{ 0, "", ""},
{ 0, "", ""},
};
[그림 9-3] 배열에 의한 선형 리스트에 삽입

위의 삽입 전의 그림은 회원이 5명 저장되어 있고 data[5], data[6]은 아직 데이터가 등록되

지 않은 상태입니다. 오른쪽의 배열 그림에는 간단히 회원번호만 표시했습니다.

다음 노드 꺼내기

배열의 각 요소에는 연락할 순서대로 데이터가 저장되어 있습니다. 전화를 걸기 위해 필요한
‘다음 노드 꺼내기’는 1만큼 큰 인덱스를 갖는 요소에 접근하면 됩니다.

노드의 삽입과 삭제

회원번호가 55인 회원이 새로 가입했고 이 회원의 정보를 회원번호 12, 33 사이에 삽입하려

338 C 알고리즘