링크드 리스트(2) - 성능 개선

2023.04.20 - [자료구조/LINKED LIST 링크드 리스트] - 1. 링크드 리스트(Linked List) - 더블 링크드 리스트(메모리 풀 방식)

1. 링크드 리스트(Linked List) - 더블 링크드 리스트(메모리 풀 방식)

 

 

링크드 리스트

 

 

 

이전 글에서는 링크드 리스트가 무엇인지 알아보고 실제로 더블 링크드 리스트를 메모리 풀 방식으로 구현해봤습니다. 이번 글에서는 링크드 리스트의 성능을 개선할 수 있는 방법을 알아보도록 하겠습니다.

 

(1) 특정 노드에 빠르게 접근하기

링크드 리스트에서 특정 노드를 찾으려면 head부터 시작해서 순차적으로 순회하면서 원하는 노드를 찾아야 합니다. 그래서 노드 찾기에서 최악의 경우 O(N)의 시간복잡도를 가지게 됩니다. 하지만, 특정 노드를 찾을 때 O(1)으로 찾을 수 있는 방법이 있습니다. 노드의 고유한 데이터 값(id)을 key로 가지는 unorderedMap 또는 배열 테이블을 사용하면 됩니다(이전에 heap 특정 원소 수정 및 삭제에 대해 설명한 글에서 사용한 방법과 동일합니다.)

2023.03.12 - [자료구조/HEAP 힙] - 2. 업그레이드 된 HEAP 힙 (특정원소 삭제, 업데이트 O(logN)만에 가능)

2. 업그레이드 된 HEAP 힙 (특정원소 삭제, 업데이트 O(logN)만에 가능)

그래서 핵심 아이디어는 노드의 id를 기준으로 각각 노드의 주소값을 저장해놓고 필요할 때 id로 해당 주소값들을 찾아서 사용하는 것입니다!

 

반응형

 

(2) 소스 코드

- 아래 코드는 unorderedMap에 id를 기준으로 노드의 주소값을 저장한 예시코드입니다. 저번의 예시보다 좀 더 복잡한 예시로 준비했습니다. Node의 데이터로 Student라는 구조체를 가지도록 해주었습니다.

 

- 또한 링크드 리스트에서 p1큰 노드가 앞으로, p1이 같다면 p2 작은 노드가 앞으로 오도록 항상 정렬된 상태를 유지할 수 있도록 구현했습니다. 링크드 리스트에서 정렬된 상태를 유지하는 것은 삽입시에 정렬 기준에 맞는 위치에 삽입해주면 됩니다.

 

- 그래서 올바른 삽입 위치를 얻어오기 위해서 getNode()함수에서 노드 삽입시 어디에 삽입할지 위치를 받아올 수 있도록 하였습니다.

 

- 주의해야 할 부분은 노드 삭제시에 nodeRemove(ptr1->prev) 부분입니다. 왜냐하면 삭제 함수의 파라미터로 주어진 포인터는 삭제하려는 노드 이전 노드의 포인터이기 때문입니다.

 

- nodeInsert(), nodeRemove()함수에서 unorderedMap에 노드의 주소를 저장하고 삭제하는 부분이 있는 것도 확인하면서 보시면 좋을 것 같습니다.

 

#include<stdio.h>	//더블 링크드 리스트와 리스트에 바로 접근할 수 있도록 해시 맵 만듬
#include<unordered_map>
using namespace std;
const int MAXN = 1000;

struct Student {
	int p1;
	int p2;
};

struct Node {
	int id = -1;
	Student student;
	Node* prev;
	Node* next;
	Node* myAlloc(int _id, Student _student, Node* _prev, Node* _next) {
		id = _id;	student = _student;	prev = _prev;	next = _next;
		_next->prev = this;
		return this;
	}
}pool[MAXN];
int poolCnt = 0;
Node head, tail;

void nodeInit() {
	poolCnt = 0;
	head.next = &tail;
	tail.prev = &head;
}

unordered_map<int, Node*> myMap;	//(학생 id, 그 학생 노드를 가리킴)

//삽입,삭제,검색은 원하는 위치 이전 노드를 기준으로 함!

//삽입할 위치 이전 노드 찾기함수(p1 큰게 앞으로, p1이 같다면 p2작은게 앞으로)
Node* getNode(Student _student) {
	Node* ptr = &head;
	while (ptr->next && ptr->next->id != -1) {
		if ((_student.p1 > ptr->next->student.p1) || ((_student.p1 == ptr->next->student.p1) && (_student.p2 < ptr->next->student.p2)))break;
		ptr = ptr->next;
	}
	return ptr;
}

void nodeInsert(int id, Student student, Node* ptr) {
	ptr->next = pool[poolCnt++].myAlloc(id, student, ptr, ptr->next);

	//맵에 등록도 여기서 같이 해주자.
	myMap[id] = ptr->next;
}

void nodeRemove(Node* ptr) {
	Node* temp = ptr->next;
	ptr->next = temp->next;
	temp->next->prev = ptr;

	//맵에서 삭제도 여기서 같이 해주자
	myMap.erase(temp->id);
}

void printAll() {
	Node* ptr = &head;
	while (ptr->next && ptr->next->id != -1) {
		printf("id: %d, student.p1: %d, student.p2: %d\n", ptr->next->id, ptr->next->student.p1, ptr->next->student.p2);
		ptr = ptr->next;
	}
}

int main(void) {

	nodeInit();

	int p1 = 5; int p2 = 10;
	Student student;
	for (int i = 0; i < 10; i++) {
		student.p1 = p1;	student.p2 = p2;

		Node* ptr = getNode(student);
		nodeInsert(student.p2, student, ptr);

		if (i & 1) {	//홀수라면
			p1--;
		}
		p2--;
	}

	printAll();
	/*
	id: 9, student.p1: 5, student.p2: 9
	id: 10, student.p1: 5, student.p2: 10
	id: 7, student.p1: 4, student.p2: 7
	id: 8, student.p1: 4, student.p2: 8
	id: 5, student.p1: 3, student.p2: 5
	id: 6, student.p1: 3, student.p2: 6
	id: 3, student.p1: 2, student.p2: 3
	id: 4, student.p1: 2, student.p2: 4
	id: 1, student.p1: 1, student.p2: 1
	id: 2, student.p1: 1, student.p2: 2
	*/


	printf("\nid=8 인 노드 제거하기!!\n");
	Node* ptr1 = myMap[8];		//아이디로 맵에서 조회해서 해당 노드 주소 얻어서 노드 삭제하기
	nodeRemove(ptr1->prev);

	printAll();
	/*
	id: 9, student.p1: 5, student.p2: 9
	id: 10, student.p1: 5, student.p2: 10
	id: 7, student.p1: 4, student.p2: 7
	id: 5, student.p1: 3, student.p2: 5
	id: 6, student.p1: 3, student.p2: 6
	id: 3, student.p1: 2, student.p2: 3
	id: 4, student.p1: 2, student.p2: 4
	id: 1, student.p1: 1, student.p2: 1
	id: 2, student.p1: 1, student.p2: 2
	*/
}

 

(3) unordered_map vs 배열

노드의 id를 기준으로 노드의 주소값을 저장할 때 unordered_map을 사용할 수도 있고 배열을 사용할 수도 있습니다. 당연히 배열이 더 빠릅니다. 다만 id의 범위가 너무 크다면(ex.1억) 배열을 사용하기에는 무리가 있습니다. 그러므로 id의 범위가 너무 크면 unordered_map을 사용하고, id가 배열로 표현 가능한 범위라면 배열을 사용하는게 좋습니다.