Chapter05 연결 리스트(Linked List) 3

2017/12/13 - [프로그래밍/자료구조] - Chapter04 연결 리스트(Linked List) 2

'양방향 연결 리스트(doubly linked list)' 또는 '이중 연결 리스트'라고 불리는 자료구조는 노드가 양쪽 방향으로 연결된 구조의 리스트이다.

양방향 연결 리스트의 선입견

일반적인 선입견은 양방향 연결 리스트가 단방향 연결 리스트보다 그 구조가 복잡하고 구현이 쉽지 않는다는 것!

하지만 이는 그림상의 오해! 실제로 코드가 덜 복잡하다! 나도 해당 부분은 어느정도 공감한다.

양방향 연결 리스트의 구현: 리스트의 초기화와 노드의 삽입

양방향 연결 리스트의 초기화를 담당하는 ListInit 함수의 정의

typedef struct _dbLinkedList
{
	Node *head;
	Node *cur;
	int numOfData;
} DBLinkedList;

데이터의 조회 목적으로 선언된 멤버가 cur 하나고, 단순 연결 리스트에는 있었던 before가 존재하지 않는다. 

문제 05-2 [더미 노드 기반의 양방향 연결 리스트의 구현]

구현해야하는 연결 리스트의 특징

- 양방향 연결 리스트 

- 더미 노드가 리스트이 앞과 뒤에 각각 존재한다

- 포인터 변수 head와 tail이 있어서 리스트의 앞과 뒤를 각각 가리킨다

CLinkedList.h

/*---- INCLUDES      --------------------------------------------------------*/

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/
#define FALSE		0
#define TRUE		1
typedef int Data;
/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/

typedef struct _node {
	Data data;				// typedef int Data;
	struct _node *next;
	struct _node *prev;
} Node;

typedef struct _dbDLinkedList {
	Node *head;
	Node *tail;
	Node *cur;
	int numOfData;
} DBDLinkedList;

typedef DBDLinkedList List;

void ListInit(List *plist);

void LInsert(List *plist, Data data);		// 꼬리에 노드를 추가한다.


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

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


Data LRemove(List *plist);					// 앞서 참조가 이뤄진 노드를 삭제한다.

int LCount(List *plist);

CLinkedList.c

 /*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include "CLinkedList.h"
/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/

void ListInit(List *plist) {
	plist->head = (Node *)malloc(sizeof(Node));
	plist->tail = (Node *)malloc(sizeof(Node));

	plist->head->next = plist->tail;
	plist->head->prev = NULL;

	plist->tail->next = NULL;
	plist->tail->prev = plist->head;

	plist->numOfData = 0;

}

void LInsert(List *plist, Data data) {
	// 꼬리에 노드를 추가한다.
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->prev = plist->tail->prev;
	plist->tail->prev->next = newNode;

	newNode->next = plist->tail;
	plist->tail->prev = newNode;

	(plist->numOfData)++;
}


int LFirst(List *plist, Data *pdata) {
	if(plist->head->next == plist->tail) {
		return FALSE;
	}
	plist->cur = plist->head->next;
	*pdata = plist->cur->data;
	return TRUE;
}

int LNext(List *plist, Data *pdata) {
	if(plist->cur->next == plist->tail) {
		return FALSE;
	}
	plist->cur = plist->cur->next;
	*pdata = plist->cur->data;
	return TRUE;
}


Data LRemove(List *plist) {
	// 앞서 참조가 이뤄진 노드를 삭제한다.
	Node *rpos = plist->cur;
	Data remv = rpos->data;

	rpos->prev->next = rpos->next;
	rpos->next->prev = rpos->prev;

	plist->cur = rpos->prev;		// cur의 위치를 재조정

	free(rpos);
	(plist->numOfData)--;
	return remv;
}

int LCount(List *plist) {
	return plist->numOfData;

}

DBDLinkedListMain.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include "CLinkedList.h"
/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/

int main(void) {
	List list;
	int data;
	ListInit(&list);

	LInsert(&list, 1);
	LInsert(&list, 2);
	LInsert(&list, 3);
	LInsert(&list, 4);
	LInsert(&list, 5);
	LInsert(&list, 6);
	LInsert(&list, 7);
	LInsert(&list, 8);
	LInsert(&list, 9);

	// 데이터 출력
	if (LFirst(&list, &data)) {
		printf("%d ", data);

		while(LNext(&list, &data)) {
			printf("%d ", data);
		}
		printf("\n");
	}

	// 3의 배수 삭제
	if(LFirst(&list, &data)) {
		if (data%3 == 0) {
			LRemove(&list);
		}
		while (LNext(&list, &data)) {
			if(data%3 == 0) {
				LRemove(&list);
			}
		}
	}

	// 데이터 재출력
	if(LFirst(&list, &data)) {
		printf("%d ", data);

		while(LNext(&list, &data)) {
			printf("%d ", data);
		}
		printf("\n");
	}
}