c언어를 활용한 이중 연결 리스트

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct DListNode {
	element data;
	struct DListNode* llink;
	struct DListNode* rlink;
}DListNode;

void init(DListNode* phead) {
	phead->llink = phead;
	phead->rlink = phead;
}

void printDlist(DListNode* phead) {
	DListNode* p;
	for (p = phead->rlink; p != phead; p = p->rlink) {
		printf("<-| |%d| |-> ", p->data);
	}
	printf("\n");
}

void dinsert(DListNode* before, element data) {
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	newnode->data = data;
	newnode->llink = before;
	newnode->rlink = before->rlink;
	before->rlink->llink = newnode;
	before->rlink = newnode;
}

void ddelete(DListNode* head, DListNode* removed) {
	if (removed == head) return;
	head->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}

int main(void) {
	DListNode* head = (DListNode*)malloc(sizeof(DListNode));
	init(head);
	printf("추가 단계\n");
	for (int i = 0;i < 5;i++) {
		dinsert(head, i);
		printDlist(head);
	}
	printf("\n삭제 단계\n");
	for (int i = 0;i < 5;i++) {
		printDlist(head);
		ddelete(head, head->rlink);
	}
	free(head);
	return 0;
}

코드 설명

(1) head라는 노드를 동적으로 생성한다.

(2) 초기화 작업을 해준다.

(3) for문을 돌려서 0,1,2,3,4 head에 삽입한다.
삽입하는 함수에서도 동적으로 새로운 노드를 생성한 후,
생성한 노드에 데이터를 삽입하고 llink는 앞에 노드를, rlink는
앞에 노드가 가리켰던 노드를 가리키게 한다. (맨 앞에 노드를 삽입)

(4) 또다시 for문을 돌려서 삭제를 한다.
삭제하는 함수에서도 head가 NULL이면 return을 시키고, 앞에 노드 부터 삭제한다.
-> 삭제 함수에 매개변수로 head와 head 다음 노드를 보내서 head 의rlink가 매개변수로 온 head의 다음노드의 다음노드를 가리키게 하고 매개변수로 온 head의 다음노드의 rlink가 가리키는 노드이 llin가 head의 매개변수로 온 head의 다음노드의 llink를 가리키게 하면 head를 가리키게 되고 결국 매개변수로 온 head의 다음노드를 가리키는 노드는 아무것도 없게 되므로 free를 시켜준다.