'자료구조'에 해당되는 글 2건

Linked List

링크드리스트란 짧게 이야기해서 노드를 연결시킨 자료구조입니다. 노드는 무엇일까요?

링크드리스트에서 데이터를 갖고 있는 데이터의 묶음입니다. 그림으로 보는 것이 편할 것 같네요.

데이터들을 갖고 있는 하나의 요소가 보이시나요? 이것이 노드입니다. 노드 속에 다음 노드를 가리키고 있습니다.

화살표 모양으로 보아하니, 포인터군요!

특히, 제일 앞에 있는 노드는 헤드(head), 제일 끝 노드는 테일(tail)이라고 부릅니다.

이딴걸 왜 쓰지?

링크드리스트의 가장 큰 장점은 리스트의 길이가 가변적이라는 겁니다. 배열의 단점을 링크드리스트가 커버 할 수 있습니다.

배열은 크기가 가변적이지 않죠. 우선 크기를 정해준 다음에 모자라면 메모리를 더 할당하고, 배열의 데이터를 복사해야 되죠. 오래걸리고 비효율적이라는 것을 알 수 있겠죠?

배열을 사용해서 다시 사이즈를 늘리는 코드를 이런식으로 짤 수 있겠죠.

data *newList = (data*)malloc(sizeof(data)*(2*size));
for (int i = 0; i < size; size++)
	list[i] = newList[i];
free(list);

위 코드에서 보는 것과 같이 메모리를 할당한 후 for루프로 기존의 있던 값을 복사합니다.

하지만 링크드리스트는 어떨까요?

링크드리스트는 다음 노드만 추가하면 되기 때문에 리스트의 사이즈를 조정하는데, 그리 큰 비용을 들이지 않습니다.

아 좋은거네! 이것만 쓰면 되겠구만

이라고 생각할 수도 있겠지만, 링크드리스트는 어떤 노드를 search하거나 데이터를 변경할때 바로 찾아낼 수가 없습니다.

링크드리스트를 전부 탐색해야할 수도 있습니다.

그러니까 데이터가 자주 추가되거나 가변적으로 자주 변하게 될 프로그램이라면 링크드리스트를 쓰는 것이 좋겠고, 주로 데이터의 변경이나 탐색을 위한 것이라면 배열을 쓰는 것이 좋습니다. case-by-case죠.

구현

포인터나 구조체를 제대로 배우지 않은 사람이라면 약간 어려울 수 있습니다.

우리는 다음과 같은 연산을 정의할 겁니다.

각각의 연산을 어떻게 구현하면 될 지 그림으로 설명하도록 하지요.

1. addFirst(list, data)

가장 첫번째에 노드를 추가합니다. 가장 첫번째라고 해서 head 앞에 추가해서는 안됩니다. head의 다음 노드에 추가해야합니다.

head의 다음 노드를 새로운 노드로 가리키게 만들고, 그 새로운 노드는 이전에 head가 가리키고 있던 노드를 가리키면 됩니다.

코드는 아래와 같습니다.

void addFirst(List *list,int data) {
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = list->head->next;
	list->head->next = newNode;
	list->size++;
}

2. addLast(list, data)

가장 마지막(tail 앞)에 노드를 추가하는 연산입니다. 일단 tail앞까지 가야하지만, 그 전의 노드를 기억해야합니다. 그러니까 살짝 까다로울 수 있지요.

아래는 노드 삭제연산을 구현한 코드입니다.

void addLast(List* list, int data) {
	Node *last = list->head;
	
	while (last->next != list->tail) 
		last = last->next;
	
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = list->tail;
	last->next = newNode;
	list->size++;
}

3. removeNode(list, data)

리스트의 노드를 하나씩 돌면서 data가 일치하면 그 노드를 삭제하는 겁니다.

주의할 점은 그 노드 다음 노드를 이전의 노드가 가리키는 작업이 우선적으로 이루어져야한다는 겁니다.

void removeNode(List *list, int data) {
	Node *node = list->head;
	while (node->next != list->tail) {
		if (node->next->data == data) {
			Node *delNode = node->next;
			node->next = delNode->next;
			free(delNode);
			list->size--;
			return;
		}
		node = node->next;
	}
	printf("데이터를 찾지 못했습니다.\n");
}

4. searchNode(list, data)

삭제 연산보다 쉽습니다. list를 돌면서 data와 값이 일치하면 그 노드를 반환하면 되니까요.

void removeNode(List *list, int data) {
	Node *node = list->head;
	while (node->next != list->tail) {
		if (node->next->data == data) {
			Node *delNode = node->next;
			node->next = delNode->next;
			free(delNode);
			list->size--;
			return;
		}
		node = node->next;
	}
	printf("데이터를 찾지 못했습니다.\n");
}

5. printList(list)

이 함수 역시 정말 쉽습니다. search 연산과 별 다를 것이 없죠. 그냥 list돌면서 하나하나 출력해주기만 하면 됩니다.

전체 코드

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


typedef struct node {
	int data;
	struct node *next;
} Node;
typedef struct list {
	Node *head;
	Node *tail;
	int size;
} List;

void createlist(List *list) {
	
	list->head = (Node*)malloc(sizeof(Node));
	list->tail = (Node*)malloc(sizeof(Node));
	list->head->next = list->tail;
	list->tail->next = list->tail;
	list->size = 0;
}
void addFirst(List *list,int data) {
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = list->head->next;
	list->head->next = newNode;
	list->size++;
}
void addLast(List* list, int data) {
	Node *last = list->head;
	
	while (last->next != list->tail) 
		last = last->next;
	
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = list->tail;
	last->next = newNode;
	list->size++;
}

Node* searchNode(List *list, int data) {
	Node *node = list->head->next;
	while (node != list->tail) {
		if (node->data == data)
			return node;
		node = node->next;
	}
	printf("데이터를 찾지 못했습니다.\n");

	return NULL;
}

void removeNode(List *list, int data) {
	Node *node = list->head;
	while (node->next != list->tail) {
		if (node->next->data == data) {
			Node *delNode = node->next;
			node->next = delNode->next;
			free(delNode);
			list->size--;
			return;
		}
		node = node->next;
	}
	printf("데이터를 찾지 못했습니다.\n");
}



void printList(List *list) {
	Node *node = list->head->next;
	int i = 1;
	while (node != list->tail) {
		printf("%d 번째 노드 데이터 :%d\n", i++, node->data);
		node = node->next;
	}
}
void distroyList(List *list) {
	Node *node = list->head;
	while (node != list->tail) {
		Node *delNode = node;
		node = delNode->next;
		free(delNode);
	}
	free(list->head);
	free(list->tail);
}

int main() {

	int i;
	List list;
	createlist(&list);
	
	for (i = 1; i <= 5; i++)
		addLast(&list, i);
	for (i = 11; i <= 15; i++)
		addFirst(&list, i);
	removeNode(&list, 11);
	removeNode(&list, 15);
	removeNode(&list, 5);
	removeNode(&list, 4);
	removeNode(&list, 50);

	Node *node = searchNode(&list, 14);
	printf("search :%d\n", node->data);

	node=searchNode(&list,12);
	printf("search :%d\n", node->data);

	node = searchNode(&list, 3);
	printf("search :%d\n", node->data);

	printList(&list);
	return 0;
}

제가 구현한 코드가 삑사리가 있을지도 모릅니다. 그럴땐 여러분들이 고쳐보세요! 그러면서 실력이 느는거 아니겠습니까?! 하하