4장 - 이중 연결 리스트

지금까지의 연결 리스트는 한 노드에 링크가 하나였다.

이중 연결 리스트는 이전 노드, 다음 노드를 가리키는 링크가 각각 하나씩, 링크가 총 두개인 노드로 이루어져 있다.

struct node {
	struct node* llink;
	int data;
	struct node* rlink;
};

물론 이중 연결 리스트도 체인형, 원형 둘 다 구현 가능하다

---

원형 이중 연결 리스트에 노드 추가

 

void dinsert(struct node* node, struct node* newnode) {
	//newnode를 node의 오른쪽에 추가
	newnode->llink = node;
	newnode->rlink = node->rlink;
	node->rlink->llink = newnode;
	node->rlink = newnode;

}

---

원형 이중 연결 리스트에서 노드 삭제

void ddelete(struct node* deleted) {
	deleted->llink->rlink = deleted->rlink;
	deleted->rlink->llink = deleted->llink;
	free(deleted);
}

삭제할 노드의 왼쪽,오른쪽을 서로 연결시켜주고 삭제할 노드 free 해주기.