CHAP 7 리스트II

(1)

CHAP 7 리스트II

2021. 5. 17

순천향대학교 컴퓨터공학과

1

(2)

원형 연결 리스트



마지막 노드의 링크가 첫 번째 노드를 가리키 는 리스트



한 노드에서 다른 모든 노드로의 접근이 가능

(4)

원형 연결 리스트



보통 헤드포인터가 마지막 노드를 가리키게 끔 구성하면 리스트의 처음이나 마지막에 노 드를 삽입하는 연산이 단순 연결 리스트에 비하여 용이

(5)

원형 연결 리스트의 처음에 삽입

(6)

삽입 알고리즘(1): 처음에 삽입

 첫번째 노드로 삽입하고 헤드 포인터 반환

6

ListNode* insert_first(ListNode* head, element data) // head: 헤드 포인터, data: 삽입될 항목

//리스트가 NULL인 경우 고려

head

NULL NULL

… node

(7)

삽입 알고리즘(2): 끝에 삽입

7

ListNode* insert_last(ListNode* head, element data) // head: 헤드 포인터

// data: 삽입될 데이터

//리스트가 NULL인 경우 고려

head

NULL NULL

…

node

(8)

원형 연결 리스트 출력



리스트에 포함된 모든 항목 출력

8

void print_list(ListNode *head) // head: 헤드 포인터

head

NULL NULL

…

(9)

테스트

int main(void) {

ListNode *head = NULL;

head = insert_last(head, 20);

head = insert_first(head, 10);

print_list(head);

return 0;

}

(10)

원형 연결 리스트 응용



태스크 스케쥴링

(11)

원형 연결 리스트 응용 (2)



원형 큐 구현

(12)

이중 연결 리스트



단순 연결 리스트의 문제점: 선행 노드를 찾 기가 힘들다

(13)

이중 연결 리스트



이중 연결 리스트: 하나의 노드가 선행 노드 와 후속 노드에 대한 두 개의 링크를 가지는 리스트



단점은 공간을 많이 차지하고 코드가 복잡

(14)

이중연결리스트



P가 임의 노드를 가리키면 다음 관계 성립

14

p = p.llink.rlink = p.rlink.llink

p

(15)

노드의 구조



노드 구조: (llink, data, rlink)

 llink, rlink는 각각 노드의 선행 노드와 후속 노드를 가리키는 링크임

typedef int element;

typedef struct DlistNode { element data;

struct DlistNode *llink;

struct DlistNode *rlink;

} DlistNode;

llink data rlink

(16)

헤드노드



헤드노드(head node): 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으 로 만들어진 노드

 헤드 포인터와 달리 데이터 포함하지 않음

 이중연결이면서 원형연결리스트 구성

 마지막 노드 삽입, 삭제시 효율적

(17)

헤드노드



공백상태에서는 헤드 노드만 존재

헤드노드 head

(18)

삽입 연산

// 새로운 데이터를 노드 before의 오른쪽에 삽입한다.

void dinsert(DListNode *before, element data) {

DListNode *newnode = (DListNode *)malloc(sizeof(DListNode));

}

(19)

삭제 연산

// 노드 removed를 삭제한다.

void ddelete(DListNode* head, DListNode* removed) {

if (removed == head) return;

free(removed);

}

(20)

테스트

int main(void) {

DListNode*head = (DListNode *)malloc(sizeof(DListNode));

init(head); // llink, rlink가 자신을 가리키게 초기화 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++) {// 헤드 노드의 ?노드 삭제 ddelete(head, head->rlink);

}

free(head);

return 0;

}

헤드노드

(21)

연결 리스트로 구현한 스택

(22)

연결리스트 스택 표현

typedef int element;

typedef struct StackNode { element data;

struct StackNode *link;

} StackNode;

typedef struct {

StackNode *top;

} LinkedStackType;

(23)

삽입 연산

void push(LinkedStackType *s, element item) {

StackNode *temp = (StackNode *)malloc(sizeof(StackNode));

temp->data = item;

}

(24)

삭제 연산

element pop(LinkedStackType *s) {

if (is_empty(s)) {

fprintf(stderr, "스택이 비어있음\n");

exit(1);

} else { // 데이터 반환, 노드는 회수

} }

(25)

Test:

int main(void) {

LinkedStackType s;

init(&s); // 스택 초기화 push(&s, 1);

push(&s, 2);

push(&s, 3);

pop(&s);

return 0;

}

(26)

연결 리스트로 구현한 큐



연결된 큐(linked queued)

 연결리스트로 구현된 큐

(27)

연결된 큐의 표현

typedef int element; // 요소의 타입

typedef struct QueueNode { // 큐의 노드의 타입 element data;

struct QueueNode *link;

} QueueNode;

typedef struct { // 큐 타입 구현

QueueNode *front, *rear;

} LinkedQueueType;

(28)

연결된 큐: 삽입 연산

(29)

삽입 연산 알고리즘

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 { }

}

(30)

연결된 큐: 삭제 연산

(31)

삭제 연산 알고리즘

element dequeue(LinkedQueueType *q) { if (is_empty(q)) {

fprintf(stderr, "스택이 비어있음\n");

exit(1);

} else { // 삭제 후에 큐가 공백이 된 경우 고려

} }

(32)

Test:

int main(void) {

LinkedQueueType q;

init(&q); // 큐 초기화 enqueue(&q, 1);

enqueue(&q, 2);

enqueue(&q, 3);

dequeuer(&q);

return 0;

}

CHAP 7 리스트II