[📗c언어 쉽게 풀어쓴 자료구조7] 연결리스트2

👑 원형 연결리스트

: 마지막 노드의 링크가 첫 번째 노드 주소 가리킴

• head가 마지막 노드 가리키는 포인터!!!
• 처음에 삽입, 마지막에 삽입 2가지

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

typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

//출력 함수
void print_list(ListNode* head) {
	ListNode* p;
	if (head == NULL) return;
	p = head->link;
	do {
		printf("%d->", p->data);
		p = p->link;
	} while (p!=head);
	printf("%d->", p->data);
}

//처음 삽입 함수
ListNode* insert_first(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) { //공백상태이면, head가 가리키는 것이 그 노드가 되게
		head = node;
		node->link = head;
	}
	else {
		node->link = head->link;
		head->link = node;
	}
	return head;
}

//마지막 삽입 함수
ListNode* insert_last(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head = node;
		node -> link = head;
	}
	else {
		node->link = head->link;
		head->link = node;
		head = node;
	}
	return head;
}

int main(void)
{
	ListNode* head = NULL;
	
	head = insert_last(head, 20);
	head = insert_last(head, 30);
	head = insert_last(head, 40);
	head = insert_first(head, 10);
	print_list(head);

	return 0;
}

👑 이중 연결리스트

• 선행노드와 후속노드 존재(llink, rlink)
• 사용 전에 반드시 초기화 해야 함
• 헤드 노드 존재 (head 포인터와는 다름. 아무 값 없는 노드)
• llink: 바로 선행 노드 가리킴, rlink: 바로 후속 노드 가리킴
• 중간 삽입 시, 코드 순서: ↖ -> ↗ -> ↙ -> ↘
• 삭제는 가장 최근 것부터 삭제됨!!

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

typedef int element;
typedef struct DListNode {
	element data;
	struct DListNode* llink;
	struct DListNode* rlink;
}DListNode;

//초기화 함수
void init(DListNode* phead) {
	phead->llink = phead;
	phead->rlink = phead;
}

//노드 출력 함수
void print_dlist(DListNode* phead) {
	DListNode* p;
	for (p = phead->rlink;p != phead;p = p->rlink) {
		printf("<-| | %d| |-> ", p->data);
	}
	printf("\n");
}

//before의 오른쪽에 삽입하는 함수
void dinsert(DListNode* before, element data) {
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	newnode->data = data;
	newnode->llink = before;
	newnode->rlink = before->rlink;
	before->rlink->llink = newnode;
	before->rlink = newnode;
}

//노드를 remove하는 함수 
void ddelete(DListNode* head, DListNode* removed) {
	if (removed == head) return;
	removed->llink->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}

int main(void)
{
	DListNode* head = (DListNode*)malloc(sizeof(DListNode));
	init(head);
	printf("추가 단계\n");
	for (int i = 0;i < 5;i++) {
		dinsert(head, i);
		print_dlist(head);
	}
	printf("삭제 단계\n");
	for (int i = 0;i < 5;i++) {
		print_dlist(head);
		ddelete(head, head->rlink);
	}
	free(head);

	return 0;
}

👑 연결리스트로 구현한 스택

• 단순 연결리스트에서 맨 앞에 요소 삽입하는 것과 같음
• head 포인터 대신 top 포인터
• 초기화: top==NULL (배열에서는 top==-1)
• 공백 상태 (top이 가리키는 것이 NULL, 포화는 안됨-동적할당)

#include <stdio.h>
#include <malloc.h>

typedef int element;
typedef struct StackNode {
	element data;
	struct StackNode* link;
}StackNode;

typedef struct {
	StackNode* top;
}LinkedStackType;

//초기화 함수
void init(LinkedStackType* s) {
	s->top == NULL;
}

//공백 상태 함수 (top이 가리키는 것이 NULL인지)
int is_empty(LinkedStackType* s) {  
	return (s->top == NULL);
}

//포화 상태 함수 (포화상태는 거의 없음. 메모리 동적 할당하기 때문에)
int is_full(LinkedStackType*s) {
	return 0;  //항상 포화상태 아님
}

//삽입 함수
void push(LinkedStackType* s, element item) {
	StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
	temp->data = item;
	temp->link = s->top;
	s->top = temp;
}

//출력 함수
void print_stack(LinkedStackType* s) {
	for (StackNode* p = s->top;p != NULL;p = p->link) {
		printf("%d->", p->data);
	}
	printf("NULL \n");
}

//삭제 함수
element pop(LinkedStackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		StackNode* temp = s->top;
		int data = temp->data;
		s->top = s->top->link;
		free(temp);
		return data;
	}
}

//피크 함수
element peek(LinkedStackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		return s->top->data;
	}
}

int main(void)
{
	LinkedStackType* s;
	init(&s);
	push(&s, 1); print_stack(&s);
	push(&s, 2); print_stack(&s);
	push(&s, 3); print_stack(&s);
	pop(&s); print_list(&s);
	pop(&s); print_list(&s);
	pop(&s); print_list(&s);

	return 0;
}

👑 연결리스트로 구현한 큐

• 삽입 (맨 뒤 rear), 삭제 (맨 앞 front)
• 초기화: front와 rear이 0 (선형 큐 배열에서는 -1)
• 공백 상태: front이 NULL (선형 큐 배열에서는 front==rear인 경우)

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

typedef int element;
typedef struct QueueNode {
	element data;
	struct QueueNode* link;
}QueueNode;

typedef struct {
	QueueNode* front, *rear;
}LinkedQueueType;

//초기화 함수 (front와 rear이 NULL)
void init(LinkedQueueType* q) {
	q->front = q->rear = 0;
}

//공백 상태 함수
int is_empty(LinkedQueueType* q) {
	return (q->front = NULL);
}

//포화 상태 함수
int is_full(LinkedQueueType* q) {
	return 0;
}

//삽입 함수
void enqueue(LinkedQueueType* q, element data) {
	QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
	temp->data = data;
	temp->link = NULL;
	if (is_empty(q)) {
		q->front = temp;
		q->rear = temp;
	}
	else {
		q->rear->link = temp;
		q->rear = temp;
	}
}

//삭제 함수
element dequeue(LinkedQueueType* q) {
	QueueNode* temp = q->front;
	element data;
	if (is_empty(q)) {
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		data = temp->data;
		q->front = q->front->link;
		if (q->front == NULL) { //마지막 남은 노드 삭제 했을 경우(front와 rear모두 NULL)
			q->rear = NULL;
		}
		free(temp);
		return data;
	}
}

//출력 함수
void print_queue(LinkedQueueType* q) {
	QueueNode* p;
	for (p = q->front;p != NULL;p = p->link) {
		printf("%d->", p->data);
	}
	printf("NULL \n");
}

int main(void)
{
	LinkedQueueType queue;
	init(&queue);

	enqueue(&queue, 1); print_queue(&queue);
	enqueue(&queue, 2); print_queue(&queue);
	enqueue(&queue, 3); print_queue(&queue);
	dequeue(&queue); print_queue(&queue);
	dequeue(&queue); print_queue(&queue);
	dequeue(&queue); print_queue(&queue);
	return 0;
}

⭕ TIL (Today I Learned)

& 이중 연결리스트에서 llink와 rlink는 노드를 가리키는 것임! 특정 링크가 아니라!!!
이중 연결리스트에서 삽입 순서 잘 기억하기!!! (1-2-3-4)
연결리스트에서 삽입 할 때에는 보통 선연결 후 이동 (포인터의 이동)!!

연결리스트는 어쨌튼 방향은 다 '->' 쪽이라고 상상하면서 코드 분석하기!! 스택과 큐에서는 배열과의 차이점을 생각하면서!