[C로 쓴 자료구조] 이중 연결 리스트 (Doubly Linked Lists)

이중 연결 리스트

 

한 노드에 이전 노드, 다음 노드를 가리키는 포인터 두 개를 가지고 있다

덕분에 단일 연결리스트 처럼 한 방향이 아닌 양 방향으로 이동 가능하다

 

이중 연결 리스트 노드 생성

 

struct node {
	struct node *llink; // 이전 노드를 포인트
	int data;
	struct node *rlink; // 다음 노드를 포인트
};

 

 

이중 연결 리스트의 종류

 

 

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

 

 newnode를 node의 오른쪽에 추가하는 연산

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);
}