[C언어로 쉽게 풀어쓴 자료구조] 7장 연결리스트 - Ⅱ

C언어로 쉽게 풀어쓴 자료구조: 7장

---

7.1 원형 연결 리스트

• 마지막 노드가 첫 번째 노드를 가리키는 리스트이다.
• 하나의 노드에서 다른 모든 노드로의 접근이 가능하다.

 
원형 리스트의 처음에 삽입

ListNode* insert_first(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;	// (1)
		head->link = node;		// (2)
	}
	return head;	// 변경된 헤드 포인터를 반환한다. 
}

• 새로운 노드의 링크인 node->link가 첫 번째 노드를 가리키게 한다.
• 마지막 노드의 링크가 node를 가리키게 한다.

원형 리스트의 처음에 삽입

 
 

원형 리스트의 끝에 삽입

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;	// (1)
		head->link = node;		// (2)
		head = node;		// (3)
	}
	return head;	// 변경된 헤드 포인터를 반환한다. 
}

• 원형 연결 리스트는 시작과 끝이 불분명하다
• head의 위치만 새로운 노드로 바꾸면 새로운 노드가 마지막 노드가 된다.

원형 리스트의 끝에 삽입

 
 
 

---

7.3 이중 연결 리스트

• 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트이다.
• 양방향으로 검색이 가능해진다.

typedef int element;
typedef struct DListNode {	// 이중연결 노드 타입
	element data;
	struct DListNode* llink;
	struct DListNode* rlink;
} DListNode;

이중 연결 리스트 노드 구조

 

삽입연산

// 새로운 데이터를 노드 before의 오른쪽에 삽입한다.
void dinsert(DListNode *before, element data)
{
	DListNode *newnode = (DListNode *)malloc(sizeof(DListNode));
	strcpy(newnode->data, data);
	newnode->llink = before;        // 1
	newnode->rlink = before->rlink; // 2
	before->rlink->llink = newnode; // 3
	before->rlink = newnode;        // 4
}

이중 연결리스트에서 삽입연산

 

삭제연산

// 노드 removed를 삭제한다.
void ddelete(DListNode* head, DListNode* removed)
{
	if (removed == head) return;
	removed->llink->rlink = removed->rlink; // 1
	removed->rlink->llink = removed->llink; // 2
	free(removed);
}

 

이중 연결리스트에서 삭제연산

---

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

• 단순 연결 리스트에서 맨 앞에 데이터를 삽입하는 것과 동일
• 연결된 스택에서 헤드 포인터 

#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;
}
// 공백 상태 검출 함수
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_stack(&s);
	pop(&s); print_stack(&s);
	pop(&s); print_stack(&s);
	return 0;
}

 

---

7.6 연결 리스트로 구현한 큐

• 기본적인 구조는 단순 연결리스트에 2개의 포인터를 추가한 것과 같음
• front 포인터는 삭제와 관련(큐에 가장 먼저 들어온 요소)
• rear 포인터는 삽입과 관련(큐에 가장 마지막에 들어온 요소)

typedef int element;	// 요소의 타입
typedef struct QueueNode {	// 큐의 노드의 타입 
	element data;
	struct QueueNode *link;
} QueueNode;

typedef struct {		// 큐 ADT 구현
	QueueNode *front, *rear;
} LinkedQueueType;

 

연결리스트로 구현한 큐

 
전체 코드

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

typedef int element;	// 요소의 타입
typedef struct QueueNode {	// 큐의 노드의 타입 
	element data;
	struct QueueNode *link;
} QueueNode;

typedef struct {		// 큐 ADT 구현
	QueueNode *front, *rear;
} LinkedQueueType;

// 큐 초기화 함수
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; 		// 링크 필드를 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; // front를 다음노드를 가리키도록 한다.
		if (q->front == 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;
}