Doubly Linked List

Doubly Linked List (양방향 연결리스트)

typedef struct _node

{

Data data;

struct _node * next;

struct _node * prev;    // 이전 노드를 가리키는 멤버가 추가됨

} Node;

양방향 연결리스트의 LNext

왼쪽 노드의 주소값을 얻을 수 있기 때문에,

단순 연결리스트와 달리 before를 유지할 필요 없음

int LPrevious(List * plist, Data * pdata);

첫번째 노드 추가

newMode->next = NULL;

-> newMode->next = plist->head;

첫번째 노드를 추가할 때 plist->head는 NULL이기 때문에 위의 바뀐 문장으로 두가지 역할을 할 수 있다. 

두번째 노드의 추가는 다음과 같이 이뤄진다.

void LInsert(List * plist, Data data)

{

Node * newNode = (Node*)malloc(sizeof(Node));

newNode->data = data;

newNode->next = plist->head;        // (1) 새 노드의 next가 이전 노드에 연결

if(plist->head != NULL)                    // NULL이 아니기 때문에

plist->head->prev = newNode; // (2) 이전 node의 prev가 새 노드에 연결

(...생략)

}

void LInsert(List * plist, Data data)

{

Node * newNode = (Node*)malloc(sizeof(Node));

newNode->data = data;

(...생략)

newNode->prev = NULL;    // (1)

plist->head = newNode;    // (2)

(plist->numOfData)++;

}

데이터 조회

LFirst, LNext는 사실상 차이가 없으며

LPrevious함수는 prev를 통해 이전 노드의 위치를 쉽게 가리킬 수 있다는 점에서 차이가 있다.

int LPrevious(List * plist, Data * pdata)

{

if(plist->cur->prev == NULL)

return FALSE;

plist->cur = plist->cur->prev;

*pdata = plist->cur->data;

return TRUE;

}

원형 연결 리스트의 활용 예제

: 직원 정보 등록 프로그램 (원형 연결리스트 기반)

- 직원 정보 등록 가능

직원 정보는 사번과 이름으로 구성

- 직원 정보를 담을 구조체 정의

구조체를 기반으로 네명의 직원정보를 원형 연결리스트에 저장 (임의 결정, 입력받지 않고 미리 결정해도 됨)

직원 사번은 int형 변수에 담음

원형 연결리스트에는 구조체 변수의 주소 값을 저장

- 직원은 순서대로 돌아가며 당직근무

등록순서대로 당직근무

(A,B,C순 직원등록시 당직근무도 A-B-C-A-B...)

- 직원 이름과 숫자를 이용해 당직자 확인

직원의 이름과 숫자를 인자로 전달받는 함수 정의

- 이 함수는 다음과 같은 직원의 정보 반환

예를 들어 '이수정'과 숫자 7이 전달되면 이수정의 당직근무 7일후

누가 당직근무를 하는지에 대한 정보 반환