소소한팁 - 삭제가 많은 Linked List 관리

Linked List로 데이터를 관리할 때 검색보다 삭제가 빈번하게 발생하는 경우가 있습니다. 예를 들어서 삭제하는 함수는 50000번 호출되는 반면 검색은 100번 이내인 경우입니다. 기존 Linked List에서 삭제를 해주려면 삭제하려는 데이터를 찾을 때까지 순회해야 하므로 호출 횟수가 많다면 전체 시간이 오래 걸립니다. 이럴 때 추가된 Node와 삭제된 Node를 별도로 관리하고 검색할 때 하나로 합쳐주면 시간을 줄일 수 있습니다.

추가된 Node와 삭제된 Node를 별도로 관리하는 Linked List

#define MAX_NODE 100000

struct Node {
	int id;
	Node* add_node;
	Node* del_node;
};

Node node_arr[MAX_NODE];

Node* get_node(int id) {
	node_arr[id].id = id;
	return &node_arr[id];
}

void add_node(Node* node1, Node* node2) {
	if (node1->add_node == 0) {
		node1->add_node = node2;
	} else {
		node2->add_node = node1->add_node;
		node1->add_node = node2;
	}
}

void del_node(Node* node1, Node* node2) {
	if (node1->del_node == 0) {
		node1->del_node = node2;
	} else {
		node2->del_node = node1->del_node;
		node1->del_node = node2;
	}
}

void print_node(Node* node) {
	// 1. 마킹할 배열 초기화
	int child_node_list[MAX_NODE];
	for (int i = 0; i < MAX_NODE; i++) {
		child_node_list[i] = 0;
	}

	// 2. 추가 되었던 node 전부 +1
	Node* add_list = node->add_node;
	while (add_list != 0) {
		child_node_list[add_list->id]++;
		add_list = add_list->add_node;
	}

	// 3. 삭제 되었던 node 전부 -1
	Node* del_list = node->del_node;
	while (del_list != 0) {
		child_node_list[del_list->id]--;
		del_list = del_list->del_node;
	}

	// 4. 찾기
	for (int i = 0; i < MAX_NODE; i++) {
		if (child_node_list[i] > 0) {
			printf("%d ", i);
		}
	}
}

메인 함수

int main() {

	// root 노드 생성
	Node* root = get_node(0);

	// node 추가
	add_node(root, get_node(1));
	add_node(root, get_node(2));
	add_node(root, get_node(3));
	add_node(root, get_node(4));
	add_node(root, get_node(5));
	add_node(root, get_node(6));
	add_node(root, get_node(7));
	add_node(root, get_node(8));
	add_node(root, get_node(9));
	add_node(root, get_node(10));

	// node 삭제
	del_node(root, get_node(2));
	del_node(root, get_node(4));
	del_node(root, get_node(6));
	del_node(root, get_node(8));
	del_node(root, get_node(10));

	// node 출력
	print_node(root);

	return 0;
}

출력

1 3 5 7 9