C언어 연결리스트

우리가 보통 리스트라고 하면 어떠한 정보가 나열된 것을 생각합니다.

마찬가지로 연결리스트도 정보가 나열되어 있습니다. 추가로 각각 연결이 되어 있는 상태입니다.

배열과 비슷하다고 생각하시면 됩니다.

* 데이터와 다음리스트를 가리키는 포인터가 저장된 것을 노드라 합니다.

* 특별히 맨 앞의 노드는 Head라고 부릅니다

* 마지막의 노드는 Null을 가리킵니다.

리스트의 삽입 과정은 다음과 같습니다.

새로운 노드가 기존의 노드를 가리키고 Head가 새로운노드를 가리키도록 하면 됩니다.

리스트의 삭제는 다음과 같습니다.

삭제할 노드의 이전의 노드가 삭제할 노드의 다음노드를 가리킨뒤 기존 노드를 삭제하면 됩니다.

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

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


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

void SingleremoveFront(SingleNode* root) {
	SingleNode* front = root->next;
	root->next = front->next;
	free(front);
}

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

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

연결리스트에는 양방향 연결리스트가 있습니다. 일반 연결리스트는 한방향만 가리키게 되는데, 양방향 연결리스트는 현재 노드의 앞부분과 뒷부분의 정보를 모두 가지고 있습니다.

양방향 연결리스트의 제일 앞부분은 Head라고 하며 제일 뒷부분은 Tail이라고 합니다.

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

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

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct {
	int data;
	struct DoubleNode* prev;
	struct DoubleNode* next;
} DoubleNode;


//t 오름차순 1 2 3 4 ...
//f 내림차순 
void insert(DoubleNode* head, DoubleNode* tail, int data, bool sort) {
	DoubleNode* node = (DoubleNode*)malloc(sizeof(DoubleNode));
	node->data = data;
	DoubleNode* cur;
	cur = head->next;
	if (sort) {
		while (cur->data < data && cur != tail) {
			cur = cur->next;
		}
	}
	else {
		while (cur->data > data && cur != tail) {
			cur = cur->next;
		}
	}
	DoubleNode* prev = cur->prev;
	prev->next = node;
	node->prev = prev;
	cur->prev = node;
	node->next = cur;
}

void DoubleremoveFront(DoubleNode* head) {
	DoubleNode* node = head->next;
	head->next = node->next;
	DoubleNode* next = node->next;
	next->prev = head;
	free(node);
}

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