02. 연결리스트

연결리스트의 필요성

• 배열 사용 시 데이터를 순차적으로 저장 가능한 장점 존재
• 메모리 공간이 불필요하게 낭비될 수 있음

배열 기반의 리스트

배열 리스트의 삽입

배열 리스트의 삭제

특정한 위치의 원소를 삭제하고자 한다면 위의 그림에서 처럼 삭제 후 당길 수 있음

배열 리스트의 구현

#include <stdio.h>
#define INF 10000

int arr[INF]; // 거의 무한에 가깝다고 가정
int count = 0;

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

void addFront(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]);
	}
}

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

배열 기반 리스트의 특징

• 배열로 만들었기에 특정한 위치의 원소에 즉시 접근 가능하다는 장점
• 데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점
• 원하는 위치로의 삽입이나 삭제가 비효율적

연결 리스트

• 연결리스트는 구조체와 포인터를 함께 사용해 구현
• 연결리스트는 리스트의 중간 지점에 노드를 추가하거나 삭제 가능
• 필요할 때마다 메모리 공간 할당(동적 할당)

단방향 연결 리스트

단방향 연결 리스트의 구조

단방향 연결 리스트의 Node들은 값과 다음 Node의 주소값을 가짐

단방향 연결 리스트 구조체

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

int arr[INF]; // 거의 무한에 가깝다고 가정
int count = 0;

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

Node* head;

int main(void) {
	head = (Node*)malloc(sizeof(Node));
	Node* node1 = (Node*)malloc(sizeof(Node));
	node1->data = 1;
	Node* node2 = (Node*)malloc(sizeof(Node));
	node2->data = 2;
	head->next = node1;
	node1->next = node2;
	node2->next = NULL;
	Node* cur = head->next; 
	// cur에 저장된 위치를 통해 연결된 리스트들의 값들에 접근
	while (cur != NULL) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	system("pause");
	return 0;
}

단방향 연결리스트 삽입과정

단방향 연결리스트 삭제과정

단방향 연결 리스트 구현

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

typedef struct {
	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;
}

주의사항

• 삽입 및 삭제에서 예외 사항 처리 필요
• 삭제할 원소가 없는데 삭제하는 경우, Head 노드를 잘못 넣은 경우 등을 체크

정리

• 삽입과 삭제가 배열에 비해 간단
• 특정 인덱스로 즉시 접근하지 못해 차례대로 검색
• 추가적인 포인터 변수가 사용되어 메모리 공간 낭비