연결리스트(LinkedList)

우리는 배열을 사용하여 데이터를 저장할 수 있고 꺼내 쓸 수도 있습니다.

하지만 처음부터 배열의 크기를 너무 크게 사용할 경우 메모리 공간이 효율적으로 사용되기 어렵습니다.

예를들어 우리에게 필요한건 5개만 저장 할 수 있는 공간인데 1000개를 저장할 수 있는 배열을 선언할 필요는 없습니다.

하지만 자료구조를 구현할 때 정확하게 몇개의 저장공간이 필요한지 알 수 있다면 좋겠지만 그렇지 않은 경우가 더 많습니다.

배열 기반 연결리스트 구현

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

int arr[1000];
int count = 0;

void addBack(int data) {
	arr[count] = data;
	count++;
}

void addFirst(int data) {
	for (int i = count; i >= 1; i--) {
		arr[i] = arr[i - 1];
	}
	arr[0] = data;
	count++;
}

void show() {
	for (int i = 0; i < count; i++) {
		printf("%d ", arr[i]);
	}
}

void removeAt(int index) {
for (int i = index; i < count - 1; i++) {
arr[i] = arr[i + 1];
}
count--;
}

int main(void) {
	addFirst(4);
	addFirst(5);
	addFirst(1);
	addBack(7);
	addBack(6);
	addBack(8);
	show();
	system("pause");
	return 0;
}

배열 기반 연결리스트 특징

1. 배열로 만들었으므로 특정 위치에 바로 접근가능 합니다.

2. 데이터가 들어갈 공간을 미리 메모리에 할당해야 합니다.

3. 특정하게 원하는 위치로의 삽입이나 삭제가 비효율적입니다.


구조체와 포인터를 이용한 연결리스트 구현

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

typedef struct Node{
	int data;
	struct Node *next;
} Node;

Node *head;

void addFront(Node *root, int data) {
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = root->next;
	root->next = node;
}

void removeFront(Node *root) {
	Node *front = root->next;
	root->next = front->next;
	free(front);
}

void freeAll(Node *root) {
	Node *cur = head->next;
	while (cur != NULL) {
		Node *next = cur->next;
		free(cur);
		cur = next;
	}
}

void showAll(Node *root) {
	Node *cur = head->next;
	while (cur != NULL) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

int main(void) {
	head = (Node*)malloc(sizeof(Node));
	head->next = NULL;
	addFront(head, 2);
	addFront(head, 1);
	addFront(head, 7);
	addFront(head, 9);
	addFront(head, 8);
	removeFront(head);
	showAll(head);
	freeAll(head);
	system("pause");
	return 0;
}

연결리스트 특징

1. 삽입과 삭제가 배열에 비해 간단하다.

2. 배열과 다르게 특정 인덱스로 즉시 접근하지 못하고, 원소를 순차적으로 접근하여야 한다.

3. 추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비된다.


양방향 연결리스트 구현(오름차순으로 데이터 저장)

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

typedef struct Node{
	int data;
	struct Node *next;
	struct Node *prev;
}Node;

Node *head;
Node *tail;

void insert(int data) {
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	Node *cur;
	cur = head->next;
	
	while (cur->data < data && cur != tail) {
		cur = cur->next;
	}

	Node *prev = cur->prev;
	prev->next = node;
	node->prev = prev;
	cur->prev = node; 
	node->next = cur;
}

void show() {
	Node *cur = head->next;
	while (cur != tail) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

void removeFront() {
	Node *node = head->next;
	head->next = node->next;
	node->next->prev = head;
	free(node);
}




int main(void) {
	head = (Node*)malloc(sizeof(Node));
	tail = (Node*)malloc(sizeof(Node));

	head->next = tail;
	head->prev = head;
	tail->next = tail;
	tail->prev = head;
	insert(2);
	insert(1);
	insert(5);
	insert(7);
	insert(4);
	removeFront();
	show();
	

	system("pause");
	return 0;
}

양방향 연결리스트 특징

1. 양방향 연결 리스트에서는 각 노드가 앞 노드와 뒤 노드의 정보를 저장하고 있습니다.

2. 양방향 연결 리스트를 이용하면 리스트의 앞 뒤에서부터 모두 접근할 수 있습니다.

다만 포인터를 두개 사용하니까 기존 단일 연결리스트보다 메모리 공간이 조금 더 많이 사용 됩니다.


출처: 나동빈님 강의