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

2020/10/30 - [자료구조] - [자료구조] 큐 (Queue) C/C++ 구현 - 알고리즘

2020/10/30 - [자료구조] - [자료구조] 스택 (Stack) C/C++ 구현 - 알고리즘

---

연결리스트란

연결리스트는 기차와 같습니다. 연결리스트는 동적으로 크기를 조절하므로 배열을 사용하는것 보다 메모리를 효율적으로 사용할 수 있다는 것이 장점입니다. 

출처 https://www.pinterest.co.kr/pin/837247386957546959/

연결리스트는 다음 노드에 해당하는 현재 노드를 기준으로 왼쪽 노드, 오른쪽 노드의 연결로 구성됩니다. 편의상 왼쪽에 존재하는 노드가 더 앞선 순서를 갖는다고 가정하겠습니다.

단방향 연결리스트의 경우 다음 노드를 의미하는 next와 마지막 노드를 가리키는 last, 저장할 data 최소 세가지의 요소로 구성됩니다. (마지막 노드를 가리키는 요소를 가지고 있어야 데이터 삽입 시 시퀀스 탐색을 하지 않습니다)

---

연결리스트 기능

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

insert(head, data)

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

getData(head, index)

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

remove(head, index)

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

count(head, data)

리스트 head에서 시작하여 last까지 탐색하면서 data와 같은 값을 가지는 노드의 개수를 반환합니다. (연결 리스트 응용)

---

연결리스트 구현

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

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

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

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

node* insert(node* head, int data) {
	if (head == NULL) { // 첫 삽입인 경우
		head = init(head);
		head->data = data;
		head->last = head;
		return head;
	}
	node* cur_node = head->last;

	node* new_node = NULL;
	new_node = init(new_node);
	cur_node->next = new_node;
	new_node->data = data;
	head->last = new_node;
	return head;
}

int getData(node* head, int index) {
	node* cur_node = head;
	for (int i = 0; i < index && cur_node != NULL; i++) {
		cur_node = cur_node->next;
	}
	if (cur_node == NULL) {
		return -1; // 범위를 넘어감
	}
	return cur_node->data;
}
int count(node* head, int data) { // 연결 리스트에서 data의 값이 몇개 있는지 
	int _cnt = 0;
	node* cur_node = head;
	while (cur_node->next != NULL) { // 마지막 노드를 찾음
		if (cur_node->data == data) {
			_cnt += 1;
		}
		cur_node = cur_node->next;
	}
	return _cnt;
}

node* remove(node* head, int index) { // index 번째 위치한 노드 삭제
	node* cur_node = head;
	node* pre_node = NULL; // 삭제하려는 노드의 앞에 위치한 노드
	for(int i = 0 ; i <index && cur_node != NULL ; i ++){
		pre_node = cur_node;
		cur_node = cur_node->next;
	}
	if (cur_node == NULL) { // 인덱스가 연결리스트 사이즈보다 큰경우
		return head;
	}
	if (pre_node == NULL) {  // 루트 노드를 삭제하려고 하면
		head->next->last = head->last;
		head = head->next;
		return head;
	}
	if (cur_node->next == NULL) { //마지막 노드를 삭제하려고 하면
		head->last = pre_node; // 마지막 노드를 앞의 노드로 재 설정
	}
	pre_node->next = cur_node->next;
	return head;
}

 

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

void print(node* cur_node) {
	while (cur_node != NULL) {
		cout << cur_node->data << " ";
		cur_node = cur_node->next;
	}
	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);


	cout << "3의 개수 : " << count(list, 3) << "개\n";

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

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

	cout << "3의 개수 : " << count(list, 3) << "개\n";

	list = remove(list, 4); // 마지막 노드 삭제
	print(list);

	list = insert(list, 5);
	print(list);
}