[Data Structure] 단순 연결리스트

#단순 연결리스트

이번시간은 연결리스트에 대해서 알아보겠습니다. 먼저 리스트란, 자료구조의 한 종류로써 순차적으로 data를 저장하고 순차적으로 data를 처리하는데 유리합니다. 연결리스트에도 종류는 다양합니다. (단순,원형,이중) 하지만, 저는 연결리스트를 단순 연결리스트로 생각하고 설명하겠습니다. 

               <c언어로 만드는 자료구주와 적용알고리즘 해설서 출처>

리스트에는 배열리스트, 연결리스트가 있는데, 배열리스트는 얼마나 리스트가 생기고 줄어드는지 미리 파악할 수 없기에 단순히 미리 크기 값을 할당합니다. 따라서 메모리 누수가 발생할 가능성이 있습니다.  너무 큰 크기로 배열을 잡았다가, 실제 다 사용하지 않는다면 메모리가 낭비되기 때문이죠. 하지만 연결리스트는 필요시에만 메모리를 동적으로 할당하기 때문에 메모리 누수가 발생되지 않고 유연합니다. 

또한, 배열리스트는 물리적으로 data가 순차적으로 되어있는 반면 연결리스트는 data가 물리적으로 순차적이지 않을 수 있습니다. 즉 각각 data의 값들이 저장되는 메모리 조각들이 포인트로 인해 논리적으로 순차적이게 보일 뿐 사실상 물리적으로는 순차적이지 않는 특징이 있습니다. 

또 연결리스트는 단순 data가 아닌 노드라는 것으로 저장합니다. 노드 안에는 data와 link를 할 수 있는 포인터로 구성되어 있습니다. 또한, 자주 변경되는 상황에서는 배열리스트보단 연결리스트가 비용적인 측면에서 효율적입니다. 

끝으로 탐색에서 연결리스트는 노드의 개수가 n개 일 경우 시간 복잡도가 O(n)인데 비해 배열리스트는 O(1)을 가집니다.  

요약을 하자면, 연결리스트가 배열리스트와 비교했을 때 가지는 장단점은 다음과 같습니다.

장점

- 추가 원소 이동 연산 불필요

- 최대 원소 개수 지정 불필요

단점

- 구현의 어려움(포인터 연산, 동적 메모리 할당, 메모리 관리 등)

-  탐색 연산의 비용이 높음

이제 실제로 구현해보겠습니다. 저는 오랜만에 공부도 할겸 C언어로 구현해보겠습니다. 한 가지 알아둘 점은, 배열리스트는 배열을 이용해 구현하고, 리스트는 구조체와 포인터를 이용해 구현한다는 점입니다. 따라서 구조체와 포인터에 대한 이해는 필수입니다. ㅎㅎ 

저는 단순하게 처음에 노드를 추가/삭제하는 함수, 원하는 위치에 노드를 삽입하는 함수, 노드 전부를 출력하는 함수, 메모리 반납을 하는 함수, 원하는 data값이 어디에 위치하는지 탐색하는 함수 정도로 구현해봤습니다.

// CProject.cpp: 콘솔 응용 프로그램의 진입점을 정의합니다.
//

#include <stdio.h>
#include <stdlib.h> //malloc을 위함

struct NODE 
{
	struct NODE *next;
	int data;
};

void init(struct NODE* head) {
	head->data = NULL;
	head->next = NULL;
}

void addFrist(struct NODE* target, int data) {
	struct NODE* newNode = (NODE*)malloc(sizeof(NODE));
	newNode->next = target->next;
	newNode->data = data;

	target->next = newNode;
}

void removeFrist(struct NODE* target) {

	struct NODE *removeNode = target->next;
	target->next = removeNode->next;

	free(removeNode);
}

void insertNode(struct NODE* head, int object, int data) {
	struct NODE* curr = head;
	struct NODE* newNode = (NODE*)malloc(sizeof(NODE));
	
	for (int i = 0; i < object-1; i++) {
		struct NODE *next = curr->next;
		curr = next;
	}
	//printf("%d\n", curr->data);
	newNode->next = curr->next;
	newNode->data = data;
	curr->next = newNode;

}

void searchNode(struct NODE* head, int data) {
	struct NODE* curr = head->next;
	int n = 1;
	while (curr != NULL) {
		struct NODE *next = curr->next;
		if (data == (int)(curr->data)) {
			printf("%d 번째에 있습니다.\n",n);
		}
		n++;
		curr = next;

	}

}

void printNode(struct NODE* head) {
	struct NODE *curr = head->next;
	while (curr != NULL) {
		printf("%d ->", curr->data);
		curr = curr->next;
	}
	printf("\n");
}

void freeNode(struct NODE* head) {
	struct NODE *curr = head->next;
	curr = head->next;
	while (curr != NULL) {
		struct NODE *next = curr->next;
		free(curr);
		curr = next;
	}

	free(head);
}

struct NODE *head;

int main()
{
	struct NODE *head = (NODE*)malloc(sizeof(NODE));
	init(head);

	addFrist(head, 10);
	addFrist(head, 20);
	addFrist(head, 30);
	addFrist(head, 40);

	removeFrist(head);

	printNode(head);
	insertNode(head,1,50);
	
	printNode(head);

	searchNode(head,50);
	
	freeNode(head);
	

    return 0;
}

결과 콘솔창