2016-09-09_조재찬_스터디일지_C언어-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;

}