원형 연결 리스트 : 마지막 노드가 첫 번째 노드를 가리키는 리스트
단순 연결 리스트에서는 마지막 노드가 NULL이었지만 원형에서는 마지막 노드의 링크가 첫 번째 노드 주소를 가르키면 된다.
장점 : 하나의 노드에서 다른 모든 노드로의 접근이 가능하다. 즉 노드의 삽입과 삭제가 단순 연결 리스트보다는 용이해진다.
특히 노드를 리스트의 끝에 추가하려면 첫 번째 노드부터 마지막 노드로 이동해야한다는 귀찮음이 있다. 그러나 head포인터가 마지막 노드를 가르키도록 구성한다면 그런 귀찮음을 없앴수 있다.
따라서 head는 마지막 노드를 가르키고 있고 head->link가 첫 번째 노드를 가르키고 있는 것이다.
원형 연결 리스트 처음에 삽입하는 함수
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의 첫번째 노드를 가르킨다.
head->link = node; // head의 링크가 새로운 노드르 가르키면 새로운 노드가 head의 첫 번째 노드가 된다.
}
return head; // 변경된 head 반환
}원형 연결 리스트 끝에 삽입하는 함수
원형 연결 리스트는 원형으로 연결되어 있으므로 어디가 처음이고 끝인지 불분명하다. 따라서 head의 위치만 새로운 노드로 바꾸어주면 새로운 노드가 미지막 노드가 된다.
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의 첫번째 노드를 가르킨다.
head->link = node; // head의 링크가 새로운 노드르 가르키면 새로운 노드가 head의 첫 번째 노드가 된다.
head = node //head가 마지막 노드를 가르킴
}
return head; // 변경된 head 반환
}테스트 프로그램
#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 = 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;
// list = 10->20->30->40
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;
}원형 연결 리스트 응용 - 멀티 플레이 게임
프로그램 설명
모두의 마블을 생각해보자 KIM, PARK, CHOI는 100번의 턴을 가지고 있다.
연결 리스트에는 각 사용자의 이름(노드 data)을 연결 시킨다.
각 플레이어는 두 개의 주사위를 던지는데 만약 두 주사위의 숫자가 같으면 (double!) 한번 더 주사위를 던질 수 있다. 첫 주사위가 다르거나, 반복 후 다르면 다음 순번으로 넘어간다(다음 노드로 이동). 만약 double!을 해서 한번 더 던진 주사위가 다시 한번 double!이 나온다면 i의 횟수가 증가하면서 또 주사위를 던지게 된다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef char element[100]; // 노드 data 타입 정의
typedef struct ListNode { // 노드 타입
element data; //data값 받는 변수
struct ListNode* link; // 다음 노드 주소값 받는 변수
} ListNode;
typedef struct CListType {
ListNode* head; //head 생성
} CListType;
// 리스트의 항목 출력
void print_list(CListType* L)
{
ListNode* p;
if (L->head == NULL) return;
p = L->head->link;
do {
printf("%s->", p->data); //data값 출력
p = p->link; // 다음 노드로 이동
} while (p != L->head); // p가 head의 주소랑 다를 때까지 반복
printf("%s->", p->data); // 마지막 노드 출력
}
void insert_first(CListType* L, element data)
{
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
strcpy(node->data, data);
if (L->head == NULL) {
L->head = node;
node->link = L->head;
}
else {
node->link = L->head->link;
L->head->link = node;
}
}
// 원형 연결 리스트 테스트 프로그램
int main(void)
{
int dice1, dice2; // 주사위 2개 선언
srand(time(NULL)); // 각각 다른 랜덤숫자 나오게 하기위해 선언
CListType list = { NULL }; // head값 NULL로 초기화
insert_first(&list, "KIM"); //KIM노드 생성후 연결
insert_first(&list, "PARK"); //Park노드 생성후 연결
insert_first(&list, "CHOI"); //Choi노드 생성후 연결
ListNode* p = list.head;
for (int i = 0; i < 100; i++) { //10번 반복
dice1 = rand() % 6 + 1; //주사위 2개 랜덤생성
dice2 = rand() % 6 + 1; // 숫자는 1부터 6까지
printf("현재 차례=%s 주사위: %d %d\n", p->data, dice1, dice2);
if (dice1 == dice2) { //첫 2개 주사위 숫자가 같으면 한번 더 반복
dice1 = rand() % 6 + 1;
dice2 = rand() % 6 + 1;
printf("현재 차례=%s 주사위: %d %d\n", p->data, dice1, dice2);
if (dice1 != dice2) p = p->link; //반복후 다르면 다음 노드로 이동
}
else p = p->link; //첫 주사위가 다르면 다음 노드로 이동
}
return 0;
}이중 연결 리스트
하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트
특징
- 링크가 양방향이므로 양방향으로 검색이 가능해진다.
- 헤드 포인터는 리스트의 첫 번째 노드를 가리키는 포인터이고 헤드 노드는 단순히 삽입, 삭제를 용이하기 위한 데이터를 가지고 있지 않는 노드이다.
노드의 구조
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)); // 노드 동적생성
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;// 위 사진의 상x
removed->rlink->llink = removed->llink;// 위 사진의 하x
free(removed);
}전체 프로그램
#include <stdio.h>
#include <stdlib.h>
#include <string.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의 오른쪽에 삽입한다. // insert_first
void dinsert(DListNode *before, element data)
{
DListNode *newnode = (DListNode *)malloc(sizeof(DListNode));
//strcpy(newnode->data, data);
newnode->data = data;
newnode->llink = before;
newnode->rlink = before->rlink;
before->rlink->llink = newnode;
before->rlink = newnode;
}
// 노드 removed를 삭제한다.
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삭제 단계\n");
for (int i = 0; i < 5; i++) {
print_dlist(head);
ddelete(head, head->rlink); //헤드의 오른쪽 원소부터 삭제
}
free(head);
return 0;
}책에서는 노드를 헤드의 오른쪽에 삽입하였다. (insert_first) 나는 노드를 헤드의 왼쪽에 삽입하는 함수를 만들어 보았다. (insert_last)
// 새로운 데이터를 노드 before의 왼쪽에 삽입한다. //insert_last
void dinsert_last(DListNode* before, element data) {
DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
newnode->data = data;
newnode->llink = before->llink; // (1)
newnode->rlink = before; // (2)
before->llink->rlink = newnode; // (4)
before->llink = newnode; // (3)
}이중 연결 리스트의 응용 - MP3 재생 프로그램
MP3 재생기를 보면 현재 곡에서 이전 곡으로 가기도 하고 다음 곡으로 가기도 한다. 리스트에는 노래 제목을 노드에 넣고 사용자는 > , < , q 명령어를 입력하면 현재 노래에서 다음, 이전, 중지를 할 수 있다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char element[100];
typedef struct DListNode { // 이중연결 노드 타입
element data;
struct DListNode* llink;
struct DListNode* rlink;
} DListNode;
DListNode* current; // 현재 어느 노드에 있는지
// 이중 연결 리스트를 초기화
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) {
if (p == current)
printf("<-| #%s# |-> ", p->data);
else
printf("<-| %s |-> ", p->data);
}
printf("\n");
}
// 노드 newnode를 노드 before의 오른쪽에 삽입한다.
void dinsert(DListNode *before, element data)
{
DListNode *newnode = (DListNode *)malloc(sizeof(DListNode));
strcpy(newnode->data, data);
newnode->llink = before;
newnode->rlink = before->rlink;
before->rlink->llink = newnode;
before->rlink = newnode;
}
// 노드 removed를 삭제한다.
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)
{
char ch;
DListNode* head = (DListNode *)malloc(sizeof(DListNode));
init(head);
dinsert(head, "Mamamia");
dinsert(head, "Dancing Queen");
dinsert(head, "Fernando");
current = head->rlink;
print_dlist(head);
do {
printf("\n명령어를 입력하시오(<, >, q): ");
ch = getchar();
if (ch == '<') {
current = current->llink;
if (current == head)
current = current->llink;
}
else if (ch == '>') {
current = current->rlink;
if (current == head)
current = current->rlink;
}
print_dlist(head);
getchar();
} while (ch != 'q');
free(head); // 동적 메모리 해제 코드를 여기에
free(current);
}연결 리스트로 구현한 스택
- 크기가 제한되지 않는다는것!
- 동적 메모리 할당, 해제를 해야 하므로 삽입, 삭제에 시간은 좀 걸린다.
즉 단순 연결 리스트 + insert_first() -> delete_first()
스택 노드
typedef int element;
typedef struct StackNode {
element data;
struct StackNode *link;
} StackNode;
typedef struct {
StackNode *top;
} LinkedStackType; // 일관성을 위해 구조체로 top포인터를 정의전체 프로그램
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);
for (int i = 0; i < 3; i++) {
push(&s, i); print_stack(&s);
}
for (int i = 0; i < 3; i++) {
pop(&s); print_stack(&s);
}
return 0;
}
연결 리스트로 구현한 큐
- front 포인터는 삭제, rear 포인터는 삽입
- 큐에 요소가 없는 경우 : front,rear = NULL
단순 연결 리스트 + insert_last() -> delete_first()
큐 노드
typedef int element;
typedef struct QueueNode {
element data;
struct QueueNode *link;
} QueueNode;
typedef struct {
QueueNode *front, *rear;
} LinkedQueueType;전체 프로그램
#include <stdio.h>
#include <stdlib.h>
typedef int element; // 요소의 타입
typedef struct QueueNode { // 큐의 노드의 타입
element data;
struct QueueNode *link;
} QueueNode;
typedef struct { // 큐 front, rear 구현
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;
}
방구석개발자