6-2 이중 연결 리스트

03. 이중 연결 리스트

단순 연결 리스트의 단점

- 어떤 노드를 찾았을 경우, 그 특정 노드의 후행 노드는 쉽게 찾을 수 있었지만, 

'어떤 특정 노드의 선행 노드'를 찾으려면 복잡한 방법이 필요함

 

- X 노드의 선행노드를 찾는 방법 (단순 연결 리스트)

- X 노드의 선행노드를 찾는 방법 (이중 연결 리스트)

- 원형 이중 연결 리스트 (완결)

 

이중 연결 리스트의 노드 구조

- 양쪽 방향으로 순회할 수 있도록 링크 필드가 두 개 필요함

>> 시작점(head)도 두개의 링크가 필요

 

- 이중 연결 리스트의 노드 구조 : 두 개의 링크 필드와 한개의 데이터 필드

typedef struct ListNode {
//이중 연결 리스트의 노드 구조 정의
	struct ListNode*Llink;
	int data;
	struct ListNode*Rlink;
}listNode;
typedef struct{//이중 연결 리스트의 헤드 노드 구조 정의
	listNode*Lhead;
	listNode*Fhead;
}linkedList_h;

linkedList_h* createLinkedList_h(void){
	//원형 연결 리스트의 헤드 노드 생성
	linkedList_h*H;
	H = (linkedList_h*)malloc(sizeof(linkedList_h));
	H → Lhead = NULL;
	H → Fhead = NULL;
	return H;
}

 

삽입 연산

void addDNode(linkedList_h*H, listNode* prevNode, intx){
//이중 연결 리스트 노드 삽입 연산, x값은 200이라고 가정함
	listNode *NewNode;
	NewNode = (listNode*)malloc(sizeof(listNode));
	NewNode → Llink =NULL;
	NewNode → data = x;
	NewNode → Rlink =NULL;
    
	NewNode → Rlink = prevNode → Rlink;
	prevNode → Rlink = NewNode;
	NewNode → Llink = prevNode;
	NewNode → Rlink → Llink = NewNode;		}

이중 연결 리스트의 노드 삭제

void deleteDNode(linkedList_h*H, listNode* delNode){
//이중 연결 리스트에서 데이터의 값이 300인 노드(delNode)를
삭제하는 연산

	delNode → Llink → Rlink = delNode → Rlink;
	delNode → Rlink → Llink = delNode → Llink;
	free(delNode);  		}

 

- 결과