[C언어] 연결 리스트

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h> 
#define INF 10000

int arr[INF];
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\n", arr[i]);
	};
}

int main(void) {
	addBack(5);
	addBack(8);
	addBack(7);
	addFirst(10);
	addFirst(12);
	show();
	system("pause");
	return 0;
}

1. 연결 리스트

1) 포인터를 이용해 단방향적으로 다음 노드를 가리킴
2) 일반적으로 연결 리스트의 시작 노드를 헤드라고 하며 별도로 관리
3) 다음 노드가 없는 끝 노드의 다음 위치 값으로도 NULL을 넣음

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

typedef struct { // 구조체 선언
	int data;
	struct Node *next;
} Node;

Node *head; // 연결리스트는 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; // next로 데이터 연결, head에서 node1으로 이어질 수 있도록
	node1->next = node2; //  node1에서 node2로 이어질 수 있도록
	node2->next = NULL; // 항상 끝노드는 next 값으로 null값을 가짐으로서 더이상 연결되어 있는게 없다는 것을 알려줌
	Node *cur = head->next; // cur라는 이름의 포인터변수를 이용해서 전체 원소의 값들을 한개씩 다 출력
	while (cur != NULL) {
		printf("%d\n", cur->data); // 하나씩 출력하고
		cur = cur->next; // 그 다음원소로 이동하는 방식
	}
	system("pause");
	return 0;
}

• 삽입과 삭제가 배열에 비해서 간단하다는 장점이 있음
• 배열과 다르게 특정 인덱스로 즉시 접근하지 못하며, 원소를 차례대로 검색해야함.
• 추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비됨

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

typedef struct { // 구조체 선언
	int data;
	struct Node *next;
} Node;

Node *head; // 연결리스트는 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\n", 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;
}

연결 리스트

• 연결 리스트는 데이터를 선형적으로 저장하고 처리하는 한 방법
• 기존에 배열을 이용했을 때보다 삽입과 삭제가 많은 경우에서 효율적
• 다만 특정한 인덱스를 바로 참조해야 할 때가 많다면 배열을 이용하는 것이 효율적

2. 양방향 연결 리스트

1) 양방향 연결 리스트는 머리(Head)와 꼬리(Tail)를 모두 가진다는 특징이 있음
2) 양방향 연결 리스트의 각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장하고 있음

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

typedef struct { // 구조체 선언
	int data;
	struct Node* prev;
	struct Node* next;
} Node;

Node* head, * 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로 설정 
	prev->next = node; // 앞에 있는 노드의 next가 현재 삽입할 노드가 되고
	node->prev = prev; // 노드의 prev가 앞쪽에 있는 노드가 되고
	cur->prev = node; // 뒤에 있는 노드의 prev가 노드가 되고
	node->next = cur; // 노드의 next가 뒤에 있는 노드가 됨
}

// 양방향 연결 리스트 삭제 함수
void removeFront() {
	Node* node = head->next;
	head->next = node->next;
	Node* next = node->next;
	next->prev = head;
	free(node);
}

// 양방향 연결 리스트 전체 출력 함수
void show() {
	Node* cur = head->next;
	while (cur != tail) {
		printf("%d\n", cur->data);
		cur = cur->next;
	}
}


int main(void) {
	// head, tail 모두 할당
	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(3);
	insert(9);
	insert(7);
	removeFront();
	show();
	system("pause");
	return 0;
}

양방향 연결 리스트

• 양방향 연결 리스트에서는 각 노드가 앞 노드와 뒤 노드의 정보를 저장하고 있음
• 양방향 연결 리스트를 이용하면 리스트의 앞에서부터 혹은 뒤에서부터 모두 접근할 수 있음