[자료구조] 그림으로 쉽게 보는 연결 리스트 (Linked List) 개념과 구현

Linked List

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

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

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

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

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

head와 tail은 데이터 필드는 있지만 쓰지 않을 겁니다. 구현의 용이함을 위해선데요. 만약 head와 tail의 데이터 필드를 쓰게 되면  추가, 삭제시 3가지를 고려해야합니다.

1) 추가, 삭제할 노드가 맨 앞 노드인가

2) 추가, 삭제할 노드가 맨 뒤 노드인가

3) 추가, 삭제할 노드가 중간 노드인가

하지만 head와 tail의 data를 쓰지 않는다면 3)번 조건만 고려하면 되기 때문입니다.

이처럼 아무 데이터가 없는 노드를 더미노드라고 합니다.

이딴걸 왜 쓰지?

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

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

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

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의 다음)에 새로운 노드를 추가하는 연산입니다.

2. addLast(list, data)

addFirst와 반대로 가장 뒤에 노드를 추가합니다.

3. removeNode(list, data)

링크드리스트가 갖고 있는 노드 중에 data값을 갖고 있는 노드를 삭제합니다. 

4. searchNode(list,data)

링크드 리스트에서 data의 값과 일치하는 노드를 검색합니다.

5. printList()

링크드리스트를 전부 탐색합니다. 리스트의 데이터를 전부 보여줍니다.

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

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;
}

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