[자료구조] 이중 연결 리스트 (Double Linked List) C/C++ 구현 - 알고리즘

2020/10/30 - [자료구조] - [자료구조] 연결 리스트 (Linked List) C/C++ 구현 - 알고리즘

[자료구조] 연결 리스트 (Linked List) C/C++ 구현 - 알고리즘

이전에는 단방향 연결리스트에 대한 구현하는 방법을 소개했습니다. (다음 노드의 위치만 저장하고 있었죠)

이중연결리스트란 

이중 연결 리스트는 연결이 양방향으로 내 앞, 뒤의 노드 위치를 저장하고 있습니다. 아래 그림의 형태처럼 생각하시면 됩니다. 즉 순환하는 구조로 구성된다고 생각하시면 됩니다.

이중 연결 리스트는 이전 노드를 의미하는 prev와 다음 노드를 의미하는 next 저장할 데이터 3개의 최소 요소를 갖습니다.

---

이중연결리스트 기능

이중 연결리스트는 삽입, 삭제, 데이터 접근 세가지 이외에 다양한 기능 구현이 가능합니다. (연결 리스트와 동일합니다)

insert(head, data)

리스트 head의 맨 뒤 노드에 data를 삽입합니다.

getData(head, index)

리스트 head로부터 index 만큼 떨어진 노드에 저장된 데이터를 반환합니다. 인덱스가 범위를 넘어가면 -1을 반환합니다.

remove(head, index)

리스트 head로부터 index 만큼 떨어진 노드를 삭제합니다. 인덱스가 범위를 넘어가면 아무런 수행도 하지 않습니다.

---

이중연결리스트 구현

연결리스트 구조체는 다음의 멤버들로 구성됩니다.

struct node {
	node* next;
	node* prev;
	int data;
};

아래는 이중연결리스트가 제공하는 기능을 구현한 각 메소드 (method)입니다.

node* init(node* tmp) {
	tmp = new node();
	tmp->prev = NULL;
	tmp->next = NULL;
	tmp->data = 0;
	return tmp;
}

node* insert(node* head, int data) {
	if (head == NULL) { // 첫 삽입인 경우
		head = init(head);
		head->data = data;
		head->next = head; // 다음 노드를 자신으로 설정
		head->prev = head; // 이전 노드도 자신으로 설정
		return head;
	}

	node* last_node = head->prev; // head의 prev는 마지막 노드를 가리킴

	node* new_node = NULL;
	new_node = init(new_node); // 새로운 노드 생성

	last_node->next = new_node; // 현재 마지막 노드에 생성된 노드 연결
	new_node->prev = last_node; // 생성된 노드의 이전 노드를 연결 
	new_node->next = head; // 마지막 노드의 다음을 헤드와 연결
	head->prev = new_node; // 헤드의 이전 노드를 새로만든 노드를 가리킴

	new_node->data = data;
	return head;
}

int getData(node* head, int index) {
	node* cur_node = head;
	for (int i = 0; i < index; i++) {
		cur_node = cur_node->next;
		if (cur_node == head) { // 다시 head로 오면 인덱스를 벗어난 것이다
			break;
		}
	}
	if (cur_node == NULL) {
		return -1; // 범위를 넘어감
	}
	return cur_node->data;
}

node* remove(node* head, int index) { // index 번째 위치한 노드 삭제
	node* cur_node = head;
	for (; index; index --) { 
		cur_node = cur_node->next;
		if (cur_node == head) { // 다시 head로 오면 인덱스를 벗어난 것이다
			break;
		}
	}
	if (index) { // 범위를 벗어남
		return head; // 아무것도 안함
	}
	if (cur_node->prev == cur_node->next) { // 이전 노드와 다음 노드가 같은 경우
		return init(head); //노드가 head뿐인 경우 head 초기화 후 반환
	}
	cur_node->prev->next = cur_node->next; // 현재노드의 이전노드의 다음은 현재노드의 다음노드
	cur_node->next->prev = cur_node->prev; // 현재노드의 다음노드의 이전은 현재노드의 이전노드
	if (cur_node == head) { // 지우는 노드가 head라면
		head = head->next; // 다음 노드를 헤드로 지정
	}
	return head;
}

이중연결리스트 생성, 초기화, 사용 방법 예시에 대한 전체 코드입니다.

void print(node* head) {
	node* cur_node = head;
	while (1) {
		cout << cur_node->data << " ";
		cur_node = cur_node->next;
		if (cur_node == head) {
			break;
		}
	}
	cout << "\n";
	return;
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	node* list = NULL;
	list = insert(list, 1);
	list = insert(list, 2);
	list = insert(list, 3);
	list = insert(list, 4);
	list = insert(list, 3);
	list = insert(list, 2);
	list = insert(list, 1);
	print(list);
	
	list = remove(list, 0);
	print(list);

	list = remove(list, 3);
	print(list);

	list = remove(list, 4);
	print(list);
}