[Algorithm] C/C++에서 단순 연결 리스트(Singly Linked List) 구현하기

업데이트(2019.02.03) : 코드 일부 수정 및 개선

C++에서 단순 열결 리스트(Singly Linked List)를 구현해보자


환경

  • C++


Singly Linked List란?

개념

  • 아래처럼 하나의 노드에 필요한 정보를 담고 다음에 해당하는 노드를 가리키고 있는 자료구조로 포인터를 이용해 자료들을 선형으로 연결할 자료구조이다.
  • 배열과 비교했을 때 추가 및 삭제가 쉽다는 장점이 있지만 접근할 때 O(n)만큼 걸린다는 단점이 있습니다.



구현

공통

  • 구현을 편리하게 하기위해 전역으로 하나의 리스트만 만들었습니다.
  • 큰 틀은 아래와 같으면 추가, 삭제 그리고 순회의 경우에 필요한 부분들을 수정하면 됩니다.
  • list는 리스트의 처음을 가리킵니다.
#include <stdio.h>
#include <stdlib.h>

// Node
struct Node {
	int data;
	Node * next;
};

// Global list
Node * list;


추가/삭제 공통

  • 추가와 삭제의 경우에 첫번째 노드인지 아닌지를 고려해주면 구현이 편합니다.
  • 리스트의 중간에서 자료의 추가나 제거가 이루어질 때 현재 노드를 가리키는 cur와 이전 노드를 가리키는 prev가 있으면 추가 및 삭제가 편합니다.
  • 삭제의 경우에 삭제하고자 하는 노드가 있으면 true를 반환하고 없다면 false를 반환합니다.
  • 함수 ascending_order_add의 경우에는 오름차순으로 리스트를 생성하는 예제 함수입니다.


추가

  • 아래처럼 추가하려는 노드의 위치를 찾은 후에 새 노드의 next를 다음 노드를 가리키고 이전 노드가 추가하려는 노드를 가리키게 합니다.
  • 코드는 크게 3가지 방식이 있습니다.
  • add : 새로 추가하는 방법
  • ascending_order_add : 중간에 추가하는 방법
  • add_unique : 중복된 값 없이 추가하는 방법



// Add - one by one
void add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	// Check first element
	if (list == NULL) {
		list = new_node;
	}
	else {
		// Add new node to head
		new_node->next = list;
		list = new_node;
	}
}
// Add - add ascending order
void ascending_order_add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {

		Node * cur = list;
		Node * prev = NULL;

		// If first element is larger than key
		if (cur->data > new_node->data) {
			new_node->next = cur;
			list = new_node;
		}
		// Other cases
		else {
			while (cur != NULL && cur->data < new_node->data) {
				prev = cur;
				cur = cur->next;
			}
			// Add in middle
			if (cur != NULL) {
				new_node->next = cur;
				prev->next = new_node;
			}
			// Add to end
			else {
				prev->next = new_node;
			}
		}
	}
}
// Add - add only unique value
void add_unique(int key) {
	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {
		Node * cur = list;

		// Duplication check
		while (cur != NULL) {
			if (cur->data == key) {
				return;
			}
			cur = cur->next;
		}

		new_node->next = list;
		list = new_node;
	}
}


삭제

  • 아래처럼 삭제하려는 노드의 위치를 찾은 후에 이전노드가 삭제하려는 노드의 다음 노드를 가리키도록 하면 됩니다.
  • 똑같이 처음을 주의해주고 쉽게 구현하기 위해 curprev을 이용합니다.



// Remove
bool remove(int key) {

	if (list == NULL) {
		return false;
	}

	if (list->data == key) {
		Node * cur = list;
		list = list->next;
		free(cur);
		return true;
	}
	else {
		Node * cur = list->next;
		Node * prev = list;
		while (cur != NULL && cur->data != key) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}


코드

#include <stdio.h>
#include <stdlib.h>

// Node
struct Node {
	int data;
	Node * next;
};

// Global list
Node * list;

// Init
void init() {

	if (list == NULL) {
		return;
	}
	else {
		Node * cur;
		cur = list;

		while (cur != NULL) {
			list = cur->next;
			free(cur);
			cur = list;
		}
	}
}

// Add - one by one
void add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	// Check first element
	if (list == NULL) {
		list = new_node;
	}
	else {
		// Add new node to head
		new_node->next = list;
		list = new_node;
	}
}

// Add - add ascending order
void ascending_order_add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {

		Node * cur = list;
		Node * prev = NULL;

		// If first element is larger than key
		if (cur->data > new_node->data) {
			new_node->next = cur;
			list = new_node;
		}
		// Other cases
		else {
			while (cur != NULL && cur->data < new_node->data) {
				prev = cur;
				cur = cur->next;
			}
			// Add in middle
			if (cur != NULL) {
				new_node->next = cur;
				prev->next = new_node;
			}
			// Add to end
			else {
				prev->next = new_node;
			}
		}
	}
}

// Add - add only unique value
void add_unique(int key) {
	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {
		Node * cur = list;

		// Duplication check
		while (cur != NULL) {
			if (cur->data == key) {
				return;
			}
			cur = cur->next;
		}

		new_node->next = list;
		list = new_node;
	}
}

// Remove
bool remove(int key) {

	if (list == NULL) {
		return false;
	}

	if (list->data == key) {
		Node * cur = list;
		list = list->next;
		free(cur);
		return true;
	}
	else {
		Node * cur = list->next;
		Node * prev = list;
		while (cur != NULL && cur->data != key) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}

// Traverse
void traverse() {

	Node * cur = list;
	while (cur != NULL) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");

}

int main() {

	int arr[9] = { 2, 4, 6, 8, 1, 3, 5, 7, 9 };
	int arr_duplicated[18] = { 8, 1, 3, 2, 4, 6, 8, 1, 3, 5, 7, 9, 2, 4, 6, 5, 7, 9 };
	int arr_rmv[4] = { 2, 9, 8, 100 };


	// Add to list 1
	init();
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
		add(arr[i]);
	}
	printf("After add(normal) : ");
	traverse();


	// Add to list 2
	init();
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
		ascending_order_add(arr[i]);
	}
	printf("After add(ascending) : ");
	traverse();


	// Add to list 3
	init();
	for (int i = 0; i < sizeof(arr_duplicated) / sizeof(arr_duplicated[0]); ++i) {
		add_unique(arr_duplicated[i]);
	}
	printf("After add(unique) : ");
	traverse();


	// Remove specific values in list
	for (int i = 0; i < sizeof(arr_rmv) / sizeof(arr_rmv[0]); ++i) {
		remove(arr_rmv[i]);
	}
	printf("After remove : ");
	traverse();

	return 0;

}

실행결과

After add(normal) : 9 7 5 3 1 8 6 4 2
After add(ascending) : 1 2 3 4 5 6 7 8 9
After add(unique) : 9 7 5 6 4 2 3 1 8
After remove : 7 5 6 4 3 1


참고자료

[Python] pdb를 이용해 파이썬 코드 디버깅하기

> pdb를 이용해 python 코드를 디버깅하는 방법을 알아보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)- Python## pdb### pdb란?- ```pdb``` : 파이썬 디버깅 도구로 파인썬 인터프리터...… Continue reading