[자료구조] Doubly Linked List (이중 연결 리스트) C언어로 구현하기

포인터가 양방향으로 두개인 연결 리스트이다.

• 앞 뒤로 이동할 수 있어서 좀 더 효율적
• 삽입, 삭제가 좀 더 쉽다
• 포인터 할당을 위한 extra memory가 발생

---

이중 연결 리스트 C언어로 구현하기

typedef struct Node {
	int element;
	struct Node* prev;
	struct Node* next;
} Node;

이중 연결 리스트의 구조체는 위와 같다.

일반 연결 리스트에서 prev(이전 노드) 만 추가한 것이다.

 

 

이중 연결 리스트 Insertion(삽입) 함수 구현하기

마찬가지로, 어디에 새로운 노드를 삽입하느냐에 따라 함수가 달라진다.

 

1. 리스트의 맨 처음에 노드를 삽입하는 경우

// insertion beggining
void insertAtHead(Node** head_ref, int new_data) {

	// 새로운 노드 선언하고 값 할당
	Node* new_node = (Node*)malloc(sizeof(Node));
	new_node->element = new_data;

	// 새로운 노드의 next가 현재 head를 가리킴
	new_node->next = (*head_ref);

	// 새로운 노드의 prev가 NULL을 가리킴
	new_node->prev = NULL;

	// 삽입 전 head의 prev가 새로운 노드를 가리킴
	(*head_ref)->prev = new_node;

	// head를 새로운 노드로 설정
	(*head_ref) = new_node;
}

 

2. 리스트의 맨 끝에 노드를 삽입하는 경우

// insertion at the end
void insertAtEnd(Node* head, int new_data) {

	// 새로운 노드 선언하고 값 할당
	Node* new_node = (Node*)malloc(sizeof(Node));
	new_node->element = new_data;

	// 새로운 노드의 next가 NULL을 가리킴
	new_node->next = NULL;

	// head의 마지막 노드를 찾기
	Node* last = head;
	while (last->next != NULL)
		last = last->next;

	// 새로운 노드의 prev가 마지막 노드를 가리킴
	new_node->prev = last;

	// 마지막 노드의 next가 새로운 노드를 가리킴
	last->next = new_node;
}

 

3. 리스트의 중간에 새로운 노드를 삽입하는 경우

// insertion at the middle, key 값 뒤에 삽입
void insertAfterPosition(Node* head, int new_data, int key) {

	// 새로운 노드 만들기
	Node* new_node = (Node*)malloc(sizeof(Node));
	new_node->element = new_data;

	// position을 찾기
	Node* position = head;
	while (position->element != key)
		position = position->next;

	// 새로운 노드의 next가 position 노드의 next를 가리킴(삽입해야 되니까)
	new_node->next = position->next;

	// 새로운 노드의 prev가 position을 가리킴
	new_node->prev = position;

	// position 노드의 next가 new_node를 가리킴
	position->next = new_node;
    
    // 새로운 노드의 next의 prev가 new_node를 가리킴
   	new_node->next->prev = new_node;
}

 

 

이중 연결 리스트 Deletion(삭제) 함수 구현하기

맨 앞을 삭제할 경우, 맨 뒤를 삭제할 경우, 중간을 삭제할 경우 모두 고려해야 한다.

일반 연결 리스트가 2가지 경우만 고려했다면, 이번엔 3가지 경우를 고려해야 하는 것!

void deleteNode(Node** head_ref, int key) {

	// head가 비어있지 않으면 함수 실행
	if ((*head_ref) != NULL) {

		// 삭제가 맨 앞에서 이루어질 경우
		if ((*head_ref)->element == key) {
			Node* temp = (*head_ref);
			(*head_ref) = (*head_ref)->next;
			// 새로운 head의 prev를 NULL로 설정하기
			(*head_ref)->prev = NULL;
			free(temp);
		}

		// 삭제가 중간 혹은 끝에서 이루어질 경우
		else {
			Node* prev_node = *head_ref;
			Node* cur_node = (*head_ref)->next;

			// 삭제 지점 찾기 cur_node
			while (cur_node != NULL && cur_node->element != key) {
				prev_node = cur_node;
				cur_node = cur_node->next;
			}

			// key 값이 없으면(삭제 지점 못찾으면)
			if (cur_node->element != key)
				printf("삭제 지점 찾지 못함");

			// 삭제 지점 찾으면
			else {
				Node* temp = cur_node;
				Node* next_node = cur_node->next;

				// 이전 노드의 next를 다음 노드로 설정
				prev_node->next = next_node;

				// 삭제 지점이 맨 끝이 아니면 다음 노드의 prev를 이전 노드로 설정
				if (next_node != NULL)
					next_node->prev = prev_node;

				free(temp);
			}
		}
	}
	else
		printf("링크드 리스트가 없음");
}