[ C언어 ] 자료구조_LinkedList

이번에는 자료구조 중 연결리스트를 c언어로 구현해 보겠습니다.

연결리스트는 여러 방식이 있습니다. 하나씩 그림으로 알아보겠습니다.

 

1. 단일 연결리스트

이 방식은 가장 단순하면서 구현하기 쉽습니다.

원리는 HEAD 노드가 다음 노드의 주소를 가리키고 다음 노드가 그다음 노드의 주소를 가리키는 구조입니다.

---

 

2. 원형 연결리스트

이 구조는 단일 연결리스트의 단점을 보완한 방식입니다.

단일 연결리스트는 마지막 노드에서 끝나지만 원형 연결시스트는 마지막 노드가 그다음 노드로 HEAD를 가리키고 있기 때문에 조금 더 유연한 순회를 할 수 있게 됩니다.

---

3. 이중 연결리스트 

이 구조도 단일 연결리스트의 단점을 보완한 구조입니다.

단일 연결리스트와 원형 연결리스트는 다음 노드만 가리키고 있기 때문에 이전 노드로 돌아가기 위해서는 처음부터 다시 순회를 해야 하지만 이중 연결리스트 는 이전 노드의 주소까지 가리키고 있기 때문에 훨씬 더 유연하고 빠른 순회가 가능해졌습니다.

---

4. 이중 원형 연결리스트

이 방식은 위 3가지 방식의 장점을 결합한 방식입니다.

이중 연결리스트 도 효율적이지만 결국 양쪽의 노드를 서로 왕복하기 위해서는 O(n)의 시간 복잡도가 걸리게 됩니다.

하지만 원형 연결리스트 방식을 추가하면 하나의 노드만 이동하게 되면 바로 양쪽의 노드로 바로 이동이 가능하기 때문에 효율이 더 좋아지게 됩니다.

 

하지만 효율이 좋아지는 만큼 코드가 복잡해지게 됩니다.

 

---

5. 다양한 방식의 연결리스트

연결리스트는 위 4가지 방법만 존재하는 건 아닙니다. 

이런 식으로 HEAD를 따로 빼서 Node를 가리키는 방식으로 구현할 수도 있습니다.

이 방식의 장점은 시작 Node 를 변경할 수 있기 때문에 자주 접근하는 Node 를 시작 Node로 지정할 수도 있고 추후에 변경도 가능하다는 장점이 있습니다.

 

---

 

저는 위 방식들과 또 다른 방식으로 연결리스트를 구현 해 보았습니다.

이중 연결리스트 를 기반으로 양쪽의 노드의 주소를 저장해서 양쪽에서 이동할 수 있도록 구성하였습니다.

그리고 리스트의 노드개수를 저장하도록 하여 사이즈를 바로 가져올 수 있도록 만들었습니다.

 

LinkedList.h

typedef int element;

typedef struct Node {
	struct Node* next;
	struct Node* back;
	element data;
}Node;

typedef struct LinkedList {
	struct Node* front;
	struct Node* rear;
	int size;
}LinkedList;

void init(LinkedList* list);

int add(LinkedList* list, element data);

int add_front(LinkedList* list, element data);

int add_index(LinkedList* list, int index, element data);

int remove(LinkedList* list);

int remove_front(LinkedList* list);

int remove_index(LinkedList* list, int index);

int set(LinkedList* list, int index, element data);

element get(LinkedList* list, int index);

int size(LinkedList* list);

 

LinkedList.c

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

Node* addNode()
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL) return NULL;
	newNode->next = NULL;
	newNode->back = NULL;

	return newNode;
}


//============================================

void init(LinkedList* list)
{
	list->front = NULL;
	list->rear = NULL;
	list->size = 0;
}

int add(LinkedList* list, element data)
{
	Node* newNode = addNode();
	if (newNode == NULL) return -1;

	newNode->data = data;

	if (list->size == 0) {
		list->rear = newNode;
		list->front = newNode;
		list->size = 1;
		return 0;
	}

	list->rear->next = newNode;
	newNode->back = list->rear;
	list->rear = newNode;

	list->size++;

	return 0;
}

int add_front(LinkedList* list, element data)
{
	Node* newNode = addNode();
	if (newNode == NULL) return -1;

	newNode->data = data;

	if (list->size == 0) {
		list->rear = newNode;
		list->front = newNode;
		list->size = 1;
		return 0;
	}

	list->front->back = newNode;
	newNode->next = list->front;
	list->front = newNode;

	list->size++;

	return 0;
}

int add_index(LinkedList* list, int index, element data)
{
	if (index > list->size || index < 0) return 1;

	Node* newNode = addNode();
	if (newNode == NULL) return -1;

	newNode->data = data;

	if (index == 0) 
	{
		return add_front(list, data);
	}
	else if (index == list->size)
	{
		return add(list, data);
	}
	else
	{
		Node* insert_address = NULL;

		if (index < list->size / 2)
		{
			insert_address = list->front;
			for (int i = 0; i < index - 1; i++)
			{
				insert_address = insert_address->next;
			}
		}
		else
		{
			insert_address = list->rear;
			for (int i = 0; i < list->size - index; i++)
			{
				insert_address = insert_address->back;
			}
		}

		newNode->next = insert_address->next;
		insert_address->next->back = newNode;
		insert_address->next = newNode;
		newNode->back = insert_address;

		list->size++;
	}

	return 0;

}

int remove(LinkedList* list)
{
	if (list->size == 0) return 1;

	Node* delete_address = list->rear;
	list->rear = delete_address->back;

	free(delete_address);
	
	list->size--;

	return 0;
}

int remove_front(LinkedList* list)
{
	if (list->size == 0) return 1;

	Node* delete_address = list->front;
	list->front = delete_address->next;

	free(delete_address);

	list->size--;

	return 0;
}

int remove_index(LinkedList* list, int index)
{
	if (list->size == 0) return 1;
	if (index > list->size || index < 0) return 1;
	if (index == 0) {
		return remove_front(list);
	}
	else if (index == list->size)
	{
		return remove(list);
	}
	else
	{
		Node* delete_address = NULL;

		if (index < list->size / 2)
		{
			delete_address = list->front;
			for (int i = 0; i < index; i++)
			{
				delete_address = delete_address->next;
			}

		}
		else
		{
			delete_address = list->rear;
			for (int i = 0; i < list->size - index; i++)
			{
				delete_address = delete_address->back;
			}
		}

		delete_address->back->next = delete_address->next;
		delete_address->next->back = delete_address->back;

		free(delete_address);

		list->size--;

		return 0;
	}
}

int set(LinkedList* list, int index, element data)
{
	if (index > list->size) return 1;
	Node* node_address = NULL;

	if (index < list->size / 2)
	{
		node_address = list->front;
		for (int i = 0; i < index; i++)
		{
			node_address = node_address->next;
		}
	}
	else
	{
		node_address = list->rear;
		for (int i = 0; i < list->size - index; i++)
		{
			node_address = node_address->back;
		}
	}
	node_address->data = data;

	return 0;
}

element get(LinkedList* list, int index)
{
	if (list->size == 0)
	{
		printf("요소가 없습니다,\n");
		exit(1);
	}
	if (index > list->size || index < 0)
	{
		printf("인덱스 범위 에러,\n");
		exit(1);
	}

	Node* node_address = NULL;

	if (index < list->size / 2)
	{
		node_address = list->front;
		for (int i = 0; i < index; i++)
		{
			node_address = node_address->next;
		}
	}
	else
	{
		node_address = list->rear;
		for (int i = 0; i < list->size - index - 1; i++)
		{
			node_address = node_address->back;
		}
	}
	return node_address->data;
}

int size(LinkedList* list)
{
	return list->size;
}

 

main.c

#include <stdio.h>
#include "LinkedList.h"

void listPrint(LinkedList* list) {
	for (int i = 0; i < size(list); i++) {
		printf("%.2d ", get(list, i));
	}
	printf("\n");
}

int main() {

	LinkedList list;

	init(&list);

	for (int i = 0; i < 10; i++) {
		add(&list, i);
	}

	listPrint(&list);				//전체 출력

	add_index(&list, 2, 11);

	listPrint(&list);				//전체 출력

	set(&list, 0, -1);

	listPrint(&list);				//전체 출력

	remove(&list);

	listPrint(&list);				//전체 출력

	remove_index(&list, 7);

	listPrint(&list);				//전체 출력

	return 0;
}

 

실행결과

 

위 방식은 사실 Java에서 기본으로 제공하는 LinkedList 방식과 유사하게 동작하는 코드입니다.

 

마지막으로 선형 리스트는 위 연결리스트 와 배열을 사용한 방식이 있지만 대부분은 배열을 이용한 ArrayList 방식을 더 많이 사용하게 됩니다. Java 나 Kotlin 도 ArrayList를 주로 사용하고 있습니다.

이유는 배열을 사용하면 인덱스에 바로 접근할 수 있기 때문에 O(1)의 시간복잡도로 빠르며 연결라스트는 다음 노드의 주소를 가리키기 위한 메모리 영역이 필요하기 때문에 컴퓨터 자원을 더 많이 소모하게 된다는 단점이 있기 때문입니다.

 

물론 상황에 따라 적절한 방식을 사용하는 것이 좋지만 일반적으로는 배열을 사용한 리스트를 더 추천드립니다.