Chapter 4-6 : List (Doubly Linked Lists)

Doubly Linked List는 이중연결리스트 입니다.

Singly Linked List가 일방적인 방향으로 연결되었다면 반대로 Doubly Linke List는 양방향으로 연결되어

node의 연결을 용이하게 합니다.

Doubly Linked List는 Circular로 구현할 수 있고 아닐 수 도 있습니다.

typedef struct node* node_pointer;
typedef struct node {
	node_pointer llink; //왼쪽 포인터
	int item; //data
	node_pointer rlink; //오른쪽 포인터
};

위의 그림은 Doubly Linked List의 header node입니다. 특징은 왼쪽 부분은 포인터 가운데 부분은 data 

오른쪽 부분도 포인터 입니다. 따라서 양쪽의 포인터로 새로들어올 node를 가리키게 됩니다.

처음에는 왼쪽 포인터는 자기자신을 가리키고 오른쪽 포인터도 자기 자신을 가리키게 됩니다.

위의 그림과 같은 모습을 하게 됩니다.

---

Insertion into a doubly linked circular list

이중연결리스트에서 중간의 새로운 노드를 삽입하는 함수입니다.

void dinsert(node_pointer node, node_pointer newnode) {
	newnode->llink = node;
	newnode->rlink = node->rlink;
	node->rlink->llink = newnode;
	node->rlink = newnode;
}

먼저 newnode의 llink를 원래 있던 node의 rlink와 연결합니다.

그 다음 newnode의 rlink를 node의 rlink가 가리키는 곳을 가리킵니다.

그 다음 node의 rlink가 가리키는 곳의 llink를 newnode와 연결 시켜줍니다.

마지막으로 node의 rlink를 newnode와 연결시켜줍니다.

---

Deletion from a doubly linked circular list

중간에 node를 삭제하는 함수입니다.

void ddelete(node_pointer node, node_pointer deleted) {
	if (node == deleted)
		printf("Deletion of head node not permitted\n");
	else {
		deleted->llink->rlink = deleted->rlink;
		deleted->rlink->llink = deleted->llink;
		free(deleted);
	}
}

먼저 deleted의 llink가 가리키는 곳의 rlink를 delete의 rlink가 가리키는 곳에 연결시켜줍니다.

그 다음 deleted의 rlink가 가리키는 곳의 llink를 deleted의 llink가 가리키는 곳에 연결시켜줍니다.

마지막으로 free함수를 이용해 deleted node를 삭제시켜 줍니다.