[책 정리] Chapter 04. 리스트

4.1 리스트 추상 자료형

리스트 소개

리스트(list) 또는 선형 리스트(linear list)의 항목들은 순서 또는 위치를 가짐
$L = (item_0, item_1, item_2, ..., item_{n-1})$

리스트 연산

• 새로운 항목을 리스트의 임의의 위치에 추가
• 기존의 항목을 리스트의 임의의 위치에서 삭제
• 모든 항목을 삭제
• 기존의 항목을 대치
• 리스트가 특정한 항목을 가지고 있는지 확인
• 리스트의 특정 위치의 항목을 반환
• 리스트 안의 항목의 개수 계산
• 리스트가 비어있는지 여부 확인
• 리스트 안의 모든 항목 표시

리스트 ADT

<ADT 4.1.1> 리스트

객체: n개의 element형으로 구성된 순서 있는 컬렉션
연산:
	add_last(list, item) ::= 맨 끝에 요소 추가
    add_first(list, itme) ::= 맨 앞에 요소 추가
   	add(list, pos, item) ::= pos 위치에 요소 추가
    delete(list, pos) ::= pos 위치의 요소 제거
   	clear(list) ::= 리스트의 모든 요소 제거
    replace(list, pos, item) ::= pos 위치의 요소를 item으로 변경
    is_in_list(list, item) ::= item이 리스트 내에 있는지 확인
    get_entry(list, pos) ::= pos 위치의 요소를 반환                                                                 get_length(list) ::= 리스트의 길이 계산
    is_empty(list) ::= 리스트가 비었는지 확인
    is_full(list) ::= 리스트가 꽉 찼는지 확인
    display(list) ::= 리스트의 모든 요소 표시

<예제 4.1.1> 리스트 ADT의 사용 예 #1

add_last(list1, a)
add_last(list1, b)
add(list1, 2, c)
-> 리스트 (a, b, c)
add(list1, 1, d) // 항목의 위치는 0부터 시작한다고 가정
-> 리스트 (a, d, b, c)
delete(list1, 2)
replace(list1, 1, e)
-> 리스트 (a, e, c)

<예제 4.1.2> 리스트 ADT의 사용 예 #2

// 리스트 ADT가 존재한다고 가정
// 슈퍼에서 구입할 것을 리스트로 만들어 순서대로 정리하는 프로그램

main(){
	int i, n;
    ListType list2; // list2 생성, 구현 방법에 따라 약간씩 다름
    add_last(&list2, "마요네즈"); // 리스트의 포인터를 전달
    add_last(&list2, "빵");
    add_last(&list2, "치즈");
    add_last(&list2, "우유");
    n = get_length(&list2);
    printf("쇼핑해야할 항목의 수는 %d입니다.\n",n);
    for(i=0;i<n;i++){
    	printf("%d 항목은 %s입니다.",i,get_entry(&list2,i));
    }
}

[출력 결과]
쇼핑해야할 항목의 수는 4입니다.
0 항목은 마요니즈입니다.
1 항목은 빵입니다.
2 항목은 치즈입니다.
3 항목은 우유입니다.

Quiz

1. 리스트 ADT가 이미 구현되었다고 가정, 다음과 같은 작업을 수행하는 코드 작성

• 리스트를 생성
• 리스트의 끝에 10 추가
• 리스트의 끝에 20 추가
• 리스트의 첫 번째 요소 삭제
• 리스트의 요소를 모두 출력

ListType list3;
add_last(&list3, 10);
add_last(&list3, 20);
delete(&list3,0);
// display(&list3);
int n = get_length(&list3);
for(int i=0;i<n;i++){
	printf("%d\n", get_entry(&list3,i));
}

4.2 배열로 구현된 리스트

배열은 메모리 안에서 순차적으로 공간이 할당된다고 해서 순차적 표현(sequential representation)이라고 함

<프로그램 4.2.1> 배열 리스트 ADT에서의 is_empty()와 is_full() 함수

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

#define MAX_LIST_SIZE 100 // 배열 최대 크기

typedef int element; // 배열이 저장되는 항목
typedef struct{
	element list[MAX_LIST_SIZE]; // 배열 정의
    int length; // 현재 배열에 저장된 자료들의 개수
}ArrayListType;

// 모든 함수에 구조체 포인터가 전달됨 -> 전역 변수를 사용하지 않아도 된다는 장점이 있음

// 오류 처리 함수
void error(const char* message){
    fprintf(stderr, "%s\n", message); // 오류 메세지 출력
    exit(1); // 프로그램 종료
}

// 리스트 초기화
void init(ArrayListType *L){
	L->length = 0;
}

// 리스트가 비어 있으면 1, 아니면 0 반환
int is_empty(ArrayListType *L){
	return L->length == 0;
}

// 리스트가 가득차있으면 1, 아니면 0 반환
int is_full(ArrayListType *L){
	return L->length == MAX_LIST_SIZE;
}

// 리스트 출력
void display(ArrayListType *L){
	for(int i=0;i<L->length;i++){
    	printf("%d\n",L->list[i]);
    }
}

<프로그램 4.2.2> 배열을 이용한 리스트 ADT에서의 삽입 함수

// position: 삽입하고자 하는 위치
// item: 삽입하고자 하는 자료
void add(ArrayListType* L, int position, element item)
{
    // length 보다 큰 위치에는 삽입할 수 없음
        if(!is_full(L) && (position >=0) && (position <= L->length)){
        // 삽입 위치 다음에 있는 자료들을 한 칸씩 뒤로 이동
        // 맨 뒤쪽 자료부터 한 칸씩 뒤로 이동해야 함
        for (int i = L->length - 1; i >= position; i--) {
            L->list[i + 1] = L->list[i];
        }
        L->list[position] = item;
        L->length++;
    }
}

<프로그램 4.2.3> 배열을 이용한 리스트 ADT에서의 삭제 함수

// position: 삭제하고자 하는 위치
// 반환 값: 삭제되는 자료
element delete(ArrayListType *L, int position){
	if(position <0 || position >= L->length){
    	error("위치 오류");
    }
    element item = L->list[position];
    
    // 삭제한 위치부터 맨 끝까지 자료를 한 칸씩 앞으로 이동
    // 앞에서 뒤로 이동해야 함
    for(int i=position;i<(L->length-1);i++){
    	L->list[i] = L->list[i+1];
    }
    L->length--;
    
    return item;
}

<프로그램 4.2.4> 배열을 이용한 리스트 ADT 테스트 프로그램

int main(){
    ArrayListType list1;
    ArrayListType* plist;

    // ArrayListType의 구조체를 정적으로 생성하고 이 구조체를 가리키는
    // 포인터를 함수의 매개변수로 전달
    init(&list1);
    add(&list1, 0, 10);
    add(&list1, 0, 20);
    add(&list1, 0, 30);
    display(&list1);

    // ArrayListType의 구조체를 동적으로 생성하고 이 구조체를 가리키는
    // 포이터를 함수의 매개변수로 전달
    plist = (ArrayListType*)malloc(sizeof(ArrayListType));
    init(plist);
    add(plist, 0, 10);
    add(plist, 0, 20);
    add(plist, 0, 30);
    display(plist);
    free(plist);

    return 0;
}

(배열을 이용한 리스트)
장점: 구현이 간단
단점: 크기가 고정

Quiz

1. 본문에 나와있지 않은 다음과 같은 리스트 ADT 연산을 구현해보자.

• clear(list)
• replace(list, pos, item)
• get_entry(list, pos)
• get_length(list);

void clear(ArrayListType*L){
    for (int i = 0; i < L->length;i++){
        L->list[i] = 0;
    }
    L->length = 0;
}

void replace(ArrayListType*L,int position, element item){
    L->list[position] = item;
}

element get_entry(ArrayListType*L,int position){
    return L->list[position];
}

int get_length(ArrayListType*L){
    return L->length;
}

4.3 연결리스트

4.3.1 연결리스트의 소개

연결 리스트란?

연결리스트는 동적으로 크기가 변할 수 있고, 삭제나 삽입시에 데이터 이동이 필요없는 연결된 표현(linked representation)(데이터와 링크로 구성, 링크가 데이터들을 연결하는 역할을 함)임.

연결 리스트(linked list): 물리적으로 흩어져 있는 자료들을 서류 연결하여 하나로 묶는 방법
장점: 삽입, 삭제시 데이터 이동이 필요없음, 데이터 저장 공간을 동적으로 생성할 수 있음
단점: 연산의 구현이나 사용방법이 배열에 비해 복잡하여 오류 발생 가능성이 높음, 링크 필드를 위한 추가 공간 필요

연결리스트의 구조

노드(node) = 데이터 필드(data field, 저장하고 싶은 데이터) + 링크 필드(link field, 다른 노드를 가리키는 포인터)
-연결 리스트는 노드의 집합
-노드는 어떤 위치에나 있을 수 있으며, 다른 노드로 가기 위해서는 현재 노드가 가지고 있는 포인터를 이용하면 됨
-연결 리스트에서 첫 번째 노드를 알아야 전체 노드를 접근할 수 있음. 따라서, 첫 번째 노드를 가리키고 있는 변수가 필요한데, 이를 헤드 포인터(head pointer)라고 함
-연결 리스트에서 마지막 노드의 일크는 NULL로 설정, 이는 더 이상 연결된 노드가 없다는 것을 의미함

1. 단순 연결 리스트(singly linked list): 하나의 방향으로만 연결되어 있음. 맨 마지막 노드의 링크 필드는 NULL 값을 가짐
2. 원형 연결 리스트(circular linked list): 단순 연결 리스트와 같으나 맨 마지막 노드 링크 필드가 첫 번째 노드를 가리킴
3. 이중 연결 리스트(doubly linked list): 각 노드마다 링크 필드가 2개씩 존재하며 앞, 뒤 노드를 가리키고 있음.

Quiz

1. 단순 연결 리스트에서 첫 번쨰 노드를 가리키고 있는 포인터를 헤드 포인터라고 한다.
2. 노드는 데이터 필드와 링크 필드로 이루어져 있다.
3. 배열에 비하여 연결 리스트는 어떤 장점을 가지는가? -> 삽입, 삭제시 데이터 이동이 필요없고, 데이터 저장 공간을 동적으로 생성할 수 있음

4.3.2 단순 연결 리스트

단순 연결 리스트 소개

단순 연결 리스트는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결되어 있음. 마지막 노드의 링크 필드 값은 NULL이 됨

<알고리즘 4.3.2.1> 단순 연결 리스트에서의 삽입 알고리즘

insert_node(L,before,new)

if L = NULL
	then L <- new
    else new.link <- before.link
    	 before.link <- new
         
 1. 만약 연결 리스트 L이 공백 상태라면
 2. 새로운 노드를 첫 번째 노드로 함
 3. 그렇지 않으면 new 노드의 링크가 after를 가리키게 하고(after 노드의 주소가 before 노드의 링크에 저장되어 있음)
 4. befor의 링크가 new를 가리키게 함.

<알고리즘 4.3.2.2> 단순 연결 리스트에서의 삭제 알고리즘

remove_node(L,before, removed)

if L != NULL
	then befor.link <- removed.link
    	 destory(removed)
         
1. 만약 연결 리스트 L이 공백 상태가 아니라면
2. before 노드의 링크가 after를 가리키게 하고(after 노드의 주소가 removed 노드의 링크에 저장되어 있음)
3. removed 노드를 삭제함

단순 연결 리스트의 구현

// 단순 연결 리스트 구조체 생성
typedef int element;
typedef struct ListNode{
	element data;
    struct ListNode* link;
}ListNode;

// 연결 리스트에서는 필요 시에 노드를 동적으로 생성
ListNode *p1;
p1 = (ListNode *)malloc(struct(ListNode));

p1->data = 10;
p1->link = NULL;

// 두 개의 노드를 연결
ListNode *p2;
p2 = (ListNode *)malloc(struct(ListNode));

p2->data = 20;
p2->link = NULL;
p1->link = p2;

// 메모리 해제
free(p1);
free(p2);

삽입 연산

<프로그램 4.3.2.1> 단순 연결 리스트 삽입 함수

1. head가 NULL인 경우: head가 NULL이라면 현재 삽입하려는 노드가 첫번째 노드가 됨. 따라서, head의 값만 변경하면 됨
   
2. p가 NULL인 경우: 선행 노드 p가 NULL 값일 때는 리스트의 맨 앞에 삽입. 먼저, new_node의 link가 head와 같은 값을 갖도록하고 다음에 head가 new_node를 가리키도록 함
   
3. head와 p가 NULL이 아닌 경우: 가장 일반적인 경우, new_node의 link에 p->link 값을 복사한 다음, p->link가 new_node를 가리키도록 함
   

// phead: 리스트의 헤드 포인터 head에 대한 포인터
// p: 삽입될 위치의 선행 노드를 가리키는 포인터, 이 노드 다음에 삽입 됨
// new_node: 새로운 노드를 가리키는 포인터, 삽입될 노드

void insert_node(ListNode** phead, ListNode* p, ListNode* new_node)
{
    if (*phead == NULL) { // 공백 리스트인 경우
        new_node->link = NULL;
        *phead = new_node;
    } else if (p == NULL) { // p가 NULL이면 첫 번째 노드로 삽입
        new_node->link = *phead;
        *phead = new_node;
    } else { // p 다음에 삽입
        new_node->link = p->link;
        p->link = new_node;
    }
}

삭제 연산

(1) p가 NULL인 경우: 연결 리스트의 첫 번째 노드를 삭제, 헤드 포인터를 변경하고 removed 노드가 차지하고 있는 공간을 시스템에 반환

(2) p가 NULL이 아닌 경우: 먼저 removed 앞의 노드인 p의 링크가 removed 다음 노드를 가리키도록 변경, 추가 작업으로 removed 노드가 차지하고 있는 공간을 시스템에 반환

<프로그램 4.3.2.2> 단순 연결 리스트 삭제 함수

// phead: 헤드 포인터 head의 포인터
// p: 삭제될 노드의 선행 노드를 가리키는 포인터
// removed: 삭제될 노드를 가리키는 포인터

void remove_node(ListNode **phead, ListNode *p, ListNode *removed){
	if(p == NULL){
    	*phead = (*phead)->link;
    }else{
    	p->link = removed->link;
    }
    free(removed);
}

방문 연산

<프로그램 4.3.2.3> 반복적인 리스트 방문 알고리즘

void display(ListNode *head){ // 매개변수: 첫 번째 노드를 가리키는 포인터
	ListNode *p = head;
    while(p!=NULL){ // 노드의 링크 값이 NULL이 아니면 
    	printf("%d->",p->data);
        p = p->link; // 계속 링크를 따라가면서 노드를 방문
    }
    printf("\n");
}

<프로그램 4.3.2.4> 순환적인 리스트 탐색 알고리즘

void display_recur(ListNode *head){
	ListNode *p = head;
    if(p!=NULL){
    	printf("%d->",p->data);
        display_recur(p->link);
    }
}

탐색 연산

1. 포인터 p가 첫 번째 노드를 가리키도록 함
2. 순서대로 링크를 따라가면서 노드의 데이터와 비교
3. 링크 값이 NULL이면 연결 리스트 끝에 도달한 것이므로 탐색 중단
4. 반환 값은 탐색 값을 가지고 있는 노드를 가리키는 포인터

<프로그램 4.3.2.5> 노드 값 탐색 알고리즘

ListNode *search(ListNode *head, element item){
	ListNode *p = head;
    while(p!=NULL){
    	if(p->data == item) return p; // 탐색 성공
    	p = p->link;
    }
    return p; // 탐색 실패 NULL 반환
}

두 개의 리스트 L1과 L2를 하나로 만드는 연산

첫 번째 리스트의 맨 끝으로 간 다음, 마지막 노드의 링크가 두 번째 리스트의 맨 처음 노드를 가리키도록 변경하면 됨, head1, head2가 NULL인 경우를 반드시 처리해야 함

<프로그램 4.3.2.6> 연결 리스트 연결 알고리즘

ListNode *concat(ListNode *head1, ListNode *head2){
	ListNode*p;
    if(head1 == NULL) return head2;
    else if(head2 == NULL) return head1;
    else{
    	p = head1;
        while(p->link != NULL){
        	p = p->link;
        }
        
        p->link = head2;
        return head1;
    }
}

리스트를 역순으로 만드는 연산

3개의 포인터를 이용해서 연결 리스트를 순회하면서 링크의 방향을 역순으로 바꾸면 됨, 링크의 방향을 역순으로 바꾸기 전에 미리 뒤의 노드를 알아놓아야 함

<프로그램 4.3.2.7> 연결 리스트 역순 알고리즘

ListNode *reverse(ListNode *head){
	// 순회 포인터로 p,q,r을 사용
    ListNode *p,*q,*r;
    p = head; // p는 아직 처리되지 않은 노드
    q = NULL; // q는 역순으로 만들 노드
    
    while(p!=NULL){
    	r = q; // r은 역순으로 된 노드 r은 q, q는 p를 차례를 따라간다.
        q = p;
        p = p->link;
        q->link = r; // q 링크의 방향을 바꾼다.
    }
    return q; // q는 역순으로 된 리스트의 헤드 포인터
}

전체 테스트 프로그램

<프로그램 4.3.2.8> 전체 테스트 프로그램

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

// (추가)오류 처리 함수
void error(const char*message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

// (추가)노드를 동적으로 생성하는 프로그램
ListNode * create_node(element data, ListNode *link){
	ListNode *new_node;
    new_node = (ListNode*)malloc(sizeof(ListNode));
    if(new_node == NULL) error("memory allocate error");
    new_node->data = data;
    new_node->link = link;
    return new_node;
}

// 테스트 프로그램
int main(){
    ListNode *list1 = NULL, *list2 = NULL;
    ListNode* p;

    //list1 = 30->20->10
    insert_node(&list1, NULL, create_node(10, NULL));
    insert_node(&list1, NULL, create_node(20, NULL));
    insert_node(&list1, NULL, create_node(30, NULL));
    display(list1);

    // list1 = 20->10
    remove_node(&list1, NULL, list1);
    display(list1);

    // list2 = 80->70->60
    insert_node(&list2, NULL, create_node(60, NULL));
    insert_node(&list2, NULL, create_node(70, NULL));
    insert_node(&list2, NULL, create_node(80, NULL));
    display(list2);

    // list1 = list1 + list2
    list1 = concat(list1, list2);
    display(list1);

    // list1을 역순으로
    list1 = reverse(list1);
    display(list1);

    // list1에서 20 탐색
    p = search(list1, 20);
    printf("Search Success: %d\n", p->data);

    return 0;
}

Quiz

1. 단순 연결 리스트에서 하나의 노드를 삭제하려면 어떤 노드를 가리키는 포인터 변수가 필요한가? -> 첫 번째 노드를 가리키는 포인터의 포인터 변수, 삭제하려고 하는 노드의 선행 노드의 포인터 변수, 삭제하려는 노드의 포인터 변수
2. 단순 연결 리스트에 존재하는 노드의 수를 계산하는 get_length()를 작성하여라

int get_length(ListNode *head){
    int cnt = 0;
    ListNode* p = head;
    while(p!=NULL){
        p = p->link;
        cnt++;
    }
    return cnt;
}

4.3.3 원형 연결 리스트

원형 연결 리스트 소개

원형 연결 리스트: 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트
-> 마지막 노드는 헤드 포인터인 head가 가리키고 있고, 첫 번째 노드는 head->link가 가리키고 있음
장점: 한 노드에서 다른 모든 노드로의 접근이 가능하기 때문에 삭제나 삽입이 단순 연결 리스트보다는 용이해짐

삽입 함수

1. 새로운 노드의 링크인 node->link가 첫 번째 노드를 가리키게 함
2. 마지막 노드의 링크가 node를 가리키면 됨

<프로그램 4.3.3.1> 원형 연결 리스트 처음에 삽입하는 함수

// phead: 리스트의 헤드 포인터의 포인터
// node: 삽입될 노드
void insert_first(ListNode **phead, ListNode *node){
	if(*phead == NULL){
    	*phead = node;
        node->link = node;
    }else{
      node->link = (*phead)->link;
      (*phead)->link = node;
    }
}

<프로그램 4.3.3.2> 원형 연결 리스트 삽입 알고리즘

// phead: 리스트의 헤드 포인터의 포인터
// node: 삽입될 노드
void insert_last(ListNode **phead, ListNode *node){
	if(*phead == NULL){
    	*phead = node;
        node->link = node;
    }else{
      node->link = (*phead)->link;
      (*phead)->link = node;
      *phead = node; // head의 위치만 새로운 노드로 바꿔주면 새로운 노드가 마지막 노드가 됨
    }
}

테스트 프로그램

<프로그램 4.3.3.3> 원형 연결 리스트 테스트 프로그램

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

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

void error(const char* message){
	fprintf(stderr, "%s\n", message);
    exit(1);
}

// 노드를 동적으로 생성하는 프로그램
ListNode* create_node(element data, ListNode* link)
{
    ListNode* new_node;
    new_node = (ListNode*)malloc(sizeof(ListNode));
    if (new_node == NULL)
        error("memory allocate error");
    new_node->data = data;
    new_node->link = link;
    return new_node;
}

// 리스트의 항목 출력
void display(ListNode* head)
{
    ListNode* p;
    if (head == NULL)
        return;

    p = head;
    do {
        p = p->link;
        printf("%d->", p->data);
    } while (p != head); // 마지막 노드의 링크가 9이 아니기 때문에 리스트의 끝에 도달했는지를 검사하려면 헤드 포인터와 비교해야 함 
    printf("\n");

}

int main(){
    ListNode* list1 = NULL;
    // list1 = 20->10->30
    insert_first(&list1, create_node(10, NULL));
    insert_first(&list1, create_node(20, NULL));
    insert_last(&list1, create_node(30, NULL));
    display(list1);
    
    return 0;
}

Quiz

1. 단순 연결 리스트에 비하여 원형 연결 리스트의 장점? -> 한 노드에서 다른 모든 노드로의 접근이 가능하다는 것. 하나의 노드에서 링크를 계속 따라가면 결국 모든 노드를 거쳐서 자기 자신으로 되돌아올 수 있으므로 어떤 노도로드 갈 수 있음. 따라서, 노드의 삽입과 삭제가 단순 연결 리스트보다는 용이해짐
2. 원형 연결 리스트에 존재하는 노드의 수를 계산하는 함수 get_length()를 작성하라.

int get_length(ListNode* head)
{
    int cnt = 0;
    ListNode* p = head;
    do {
        p = p->link;
        cnt++;
    } while (p != head);
    return cnt;
}

4.3.4 이중 연결 리스트

이중 연결 리스트: 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트
장점: 양방향으로 검색이 가능
단점: 공간을 많이 차지하고, 코드가 복잡해짐
-헤드 노드(head node)라는 특별한 노드를 축하는 경우가 많음 (헤드 포인터와 구별해야 함)
-헤드 포인터: 리스트의 첫 번째 노드를 가리키는 포인터
-헤드 노드: 데이터를 가지고 있지 않은 특별한 노드

이중 연결 리스트 노드 = 왼쪽 링크 필드 + 데이터 필드 + 오른쪽 링크 필드
-> 이중 연결 리스트에서 임의의 노드를 가리키는 포인터를 p라 하면, p == p->llink->rlink == p->rlink->llink 관계가 항상 성립됨

// 이중 연결 리스트 구조체 생성
typedef int element;
typedef struct DlistNode{
	element data;
    struct DlistNode *llink;
    struct DlistNode *rlink;
}DlistNode;

삽입 연산

<프로그램 4.3.4.1> 이중 연결 리스트에서의 삽입 함수

// 노드 new_node를 노드 before의 오른쪽에 삽입
void dinsert_node(DlistNode *before, DlistNode *new_node){
	new_node->llink = before;
    new_node->rlink = before->rlink;
    before->rlink->llink = new_node;
    before->rlink = new_node;
}

삭제 연산

<프로그램 4.3.4.2> 이중 연결 리스트에서의 삭제 함수

// 노드 removed를 삭제
void dremove_node(DlistNode *phead_node, DlistNode *removed){
	if(removed == phead_node) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

완전한 프로그램

<프로그램 4.3.4.3> 이중 연결 리스트에서의 삭제 함수

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

// 이중 연결 리스트 초기화
void init(DlistNode *phead){
    phead->llink = phead;
    phead->rlink = phead;
}

// 이중 연결 리스트의 노드들 출력
void display(DlistNode *phead){
    DlistNode* p;
    for (p = phead->rlink; p != phead;p=p->rlink){
        printf("<---  | %x | %d | %x | --->\n", p->llink, p->data, p->rlink);
    }
    printf("\n");
}

int main(){
    DlistNode head_node;
    DlistNode* p[10];
    init(&head_node);
    for (int i = 0; i < 5;i++){
        p[i] = (DlistNode*)malloc(sizeof(DlistNode));
        p[i]->data = i;
        // 헤드 노드의 오른쪽에 삽입
        dinsert_node(&head_node, p[i]);
    }
    dremove_node(&head_node, p[4]);
    display(&head_node);
    return 0;
}

Quiz

1. 이중 연결 리스트에서 헤드 노드를 사용하는 이유? -> 헤드 노드가 존재하게 되면 삽입, 삭제 알고리즘이 간편해지기 때문
2. 헤드 노드만 있는 공백 상태의 이중 연결 리스트에 노드를 삽입하기 위하여 dinsert_node()를 호출하였다면 포인터들은 어떻게 변경되는가? 그림으로 설명
   

4.3.5 연결 리스트 응용: 다항식

• 단순 연결 리스트에서 다항식의 각 항이 노드로 표현됨

typedef struct ListNode{
	int coef; // 계수
    int expon; // 지수
    struct ListNode *link; // 다음 항을 가리키는 링크
}ListNode;

ex) 2개의 다항식을 더하는 뎃셈 연산 c(x) = a(x) + b(x)를 구현
1. p.expon == q.expon: 두 계수를 더해서 0이 아니면 새로운 항을 만들어 다항식 c에 추가, 그리고 p와 q는 모두 다음 항으로 이동
2. p.expon < q.expon: q가 가리키는 항을 새로운 항으로 복사하여 다항식 c에 추가, 그리고 q만 다음 항으로 이동
3. p.expon > q.expon: p가 가리키는 항을 새로운 항으로 복사하여 다항식 c에 추가, 그리고 p만 다음 항으로 이동

효율적인 계산을 위해서 연결 리스트의 첫 번째 노드와 마지막 노드를 가리키는 포인터를 동시에 사용 -> 이를 헤더 노드를 통해 관리(따라서, 헤드 노드는 이중 연결 리스트)

<프로그램 4.3.5.1> 이중 연결 리스트의 다항식 프로그램

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

// 연결 리스트의 노드의 구조
typedef struct ListNode {
    int coef;
    int expon;
    struct ListNode* link;
} ListNode;

// 연결 리스트 헤더
typedef struct ListHeader {
    int length;
    ListNode* head;
    ListNode* tail;
} ListHeader;

// 초기화 함수
void init(ListHeader* plist)
{
    plist->length = 0;
    plist->head = plist->tail = NULL;
}

// 오류 처리 함수
void error(const char* message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

// plist: 연결 리스트의 헤더를 가리키는 포인터
// coef: 계수
// expon: 지수
void insert_node_last(ListHeader *plist, int coef, int expon){
    ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
    if(tmp == NULL)
        error("memory allocate error");
    tmp->coef = coef;
    tmp->expon = expon;
    tmp->link = NULL;

    if(plist->tail == NULL){
        plist->head = plist->tail = tmp;
    }else{
        plist->tail->link = tmp;
        plist->tail = tmp;
    }
    plist->length++;
}

//list3 = list1 + list2
void poly_add(ListHeader *plist1,ListHeader *plist2, ListHeader*plist3){
    ListNode* p = plist1->head;
    ListNode* q = plist2->head;
    int sum;
    while(p!=NULL && q!=NULL){
        if(p->expon == q->expon){ // p의 차수 == q의 차수 
            sum = p->coef + q->coef;
            if(sum !=0 ){
                insert_node_last(plist3, sum, p->expon);
            }
            p = p->link;
            q = q->link;
        }else if(p->expon < q->expon){ // p의 차수 < q의 차수
            insert_node_last(plist3, q->coef, q->expon);
            q = q->link;
        } else { // p의 차수 > q의 차수
            insert_node_last(plist3, p->coef, p->expon);
            p = p->link;
        }
    }

    // p와 q중의 하나가 먼저 끝나게 되면 남아 있는 항들을 모두 결과 다항식으로 복사
    if(p!=NULL){
        for (; p != NULL; p = p->link) {
            insert_node_last(plist3, p->coef, p->expon);
        }
    }
    if(q!=NULL){
        for (; q != NULL;q=q->link){
            insert_node_last(plist3, q->coef, q->expon);
        }
    }
}

// 다항식 출력 함수
void poly_display(ListHeader *plist){
    ListNode* tmp = plist->head;
    for (; tmp != NULL; tmp=tmp->link){
        printf("coef: %d, expon: %d\n", tmp->coef, tmp->expon);
    }
    printf("\n");
}

// 이중 연결 리스트의 응용 프로그램
int main(){
    ListHeader list1, list2, list3;

    // 연결 리스트 초기화
    init(&list1);
    init(&list2);
    init(&list3);

    // 다항식1을 생성(list1)
    insert_node_last(&list1, 3, 12);
    insert_node_last(&list1, 2, 8);
    insert_node_last(&list1, 1, 0);

    // 다항식2를 생성(list2)
    insert_node_last(&list2, 8, 12);
    insert_node_last(&list2, -3, 10);
    insert_node_last(&list2, 10, 6);

    // 다항식3 = 다항식1 + 다항식2
    poly_add(&list1, &list2, &list3);
    poly_display(&list3);

    return 0;
}

4.4 연결 리스트로 구현된 리스트

리스트 ADT의 구현

• 단순 연결 리스트 삽입 함수 insert_node()와 삭제 함수 delete_node()는 함수의 매개변수로 노드를 가리키는 포인터를 받음
• 리스트 ADT의 정의에서는 함수의 매개변수가 포인터가 아니라 리스트에서의 항목의 위치가 됨
  => 연결 리스트로 리스트를 구현하는 경우, 리스트의 ADT의 연산들은 연결 리스트에서 제공하는 연산들을 이용하여 구현됨
  여기서는 위치를 매개변수로 받아서 삽입, 삭제하는 함수를 작성함

리스트를 위한 구조체

typedef struct{
	ListNode *head; // 첫 번째노드를 가리키는 헤드 포인터
    int length; // 연결 리스트 내에 존재하는 노드의 개수
}LinkedListType;

// 리스트 생성
LinkedListType list1;

is_empty 연산의 구현

<프로그램 4.4.1> 연결 리스트를 사용한 리스트 ADT의 is_empty 구현

int is_empty(LinkedListType *list){
	if(list->head == NULL) return 1;
    else return 0;
}

get_length 연산의 구현

<프로그램 4.4.2> 연결 리스트를 사용한 리스트 ADT의 get_length 함수 구현

// 리스트의 항목의 개수를 반환
int get_length(LinkedListType *list){
	return list->length;
}

add 연산의 구현

add 연산: 새로운 자료를 선형 리스트에 추가하는 함수
1. 동적 메모리 할당을 이용하여 노드를 생성
2. 노드의 데이터 필드에 자료를 복사
3. 기존의 노드들 중에서 지정된 노드를 찾아서 지정된 노드의 뒤에 연결해주면 됨
-> get_node_at함수 정의: 매개변수 pos로 위치를 받아서 그 위치에 해당하는 노드의 주소를 반환, 음수라면 NULL을 반환

<프로그램 4.4.3> 연결 리스트를 사용한 리스트 ADT의 삽입 함수 구현

// 리스트 안에서 pos 위치의 노드를 반환
ListNode *get_node_at(LinkedListType*list, int pos){
	ListNode *tmp = list->head;
    if(pos < 0) return NULL;
    for(int i=0;i<pos;i++){
    	tmp = tmp->link;
    }
    return tmp;
}

// 주어진 위치에 데이터를 삽입
void add(LinkedListType *list, int pos, element data){
	ListNode*tmp;
    if((pos>=0) && (pos<=list->length)){
    	ListNode *node = (ListNode*)malloc(sizeof(ListNode));
        if(node == NULL) error("memory allocate error");
        node->data = data;
        tmp = get_node_at(list, pos-1); // 추가할 위치의 선행 노드의 주소 찾음
        insert_node(&(list->head),tmp,node);
        list->length++;
    }
}

// 리스트의 끝에 데이터를 삽입
void add_last(LinkedListType *list, element data){
	add(list, get_length(list),data);
}

// 리스트의 처음에 데이터를 삽입
void add_first(LinkedListType *list, element data){
	add(list, 0, data);
}

delete 연산의 구현

delete 연산: 공백이 아닌 리스트에서 pos 위치의 자료를 삭제함
1. get_node_at 함수를 사용하여 (pos-1) 위치에 해당하는 노드의 주소를 얻음 -> 노드 삭제 시 그 노드의 선행 노드의 주소가 필요하기 때문
2. remove_node 함수를 호출

<프로그램 4.4.4> 연결 리스트를 사용한 리스트 ADT의 삭제 함수 구현

// 주어진 위치의 데이터를 삭제
void delete(LinkedListType *list, int pos){
	if( !is_empty(list) && (pos>=0) && (pos < list->length)){
		ListNode*p = get_node_at(list, pos-1);
        ListNode*removed = get_node_at(list,pos);
        remove_node(&(list->head),p,removed);
        list->length--;
    }
}

get_entry 연산의 구현

get_entry 연산: 위치 pos에 해당하는 데이터를 반환하는 연산
1. pos가 length보다 작은지 확인
2. 작으면, get_node_at 함수를 이용하여 위치에 해당하는 노드의 주소를 얻음
3. 노드가 가지고 있는 데이터 값을 반환

<프로그램 4.4.5> 연결 리스트를 사용한 리스트 ADT의 get_entry 구현

// 주어진 위치에 해당하는 데이터를 반환
element get_entry(LinkedListType *list, int pos){
	if(pos >= get_length(list)){
    	error("location error");
    }
    ListNode*p = get_node_at(list, pos);
    return p->data;
}

clear 연산 구현

clear 연산: 모든 노드를 지우는 함수
1. 리스트의 길이 만큼 delete 함수를 호출하면 됨

<프로그램 4.4.6> 연결 리스트를 사용한 리스트 ADT의 clear 구현

// 모든 노드를 삭제
void clear(LinkedListType *list){
	for(int i=0;i<get_length(list);i++){
    	delete(list, i);
    }
}

display 연산 구현

display 연산: 리스트가 가지고 있는 데이터를 화면에 출력하는 함수
1. list의 헤드 포인터가 가리키는 노드에서부터 NULL을 만날 때까지 노드의 데이터 값을 출력하면됨

<프로그램 4.4.7> 연결 리스트를 사용한 리스트 ADT의 display 구현

// 버퍼 내용을 출력
void display(LinkedListType *list){
	ListNode *node = list->head;
    printf("(");
    for(int i=0;i < get_length(list);i++){
    	printf("%d ",node->data);
        node = node->link;
    }
    printf(")\n");
}

is_in_list 연산의 구현

is_in_list 연산: 연결 리스트에서 데이터 필드가 item 인 노드를 탐색하는 연산
-> 연결 리스트 상의 모든 노드를 검색하여 데이터 필드가 item인 노드를 찾음
1. 헤드 포인터에서부터 시작하여 NULL을 만날 때까지 while 루프를 수행
2. 이때, 헤드 포인터를 직접 사용하면 안되고 반드시 복사하여 사용해야 함 -> 헤드 포인터를 변경하면 연결 리스트사 상실됨

<프로그램 4.4.8> 리스트 탐색 알고리즘

// 데이터 값이 item인 노드를 찾음
int is_in_list(LinkedListType *list, element item){
	ListNode *node = list->head; // 헤드 포인터 복사
    while(node !=NULL){
    	if(node->data == item){ // 노드의 데이터가 item이면
        	break;
        }
        node = node->link;
    }
    
    if(node == NULL) return false;
    else return true;
    
}

전체 프로그램

<프로그램 4.4.9> 연결 리스트로 구현된 리스트 ADT 테스트 프로그램

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

void error(const char *message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

// 리스트를 초기화
void init(LinkedListType *list){
    if(list== NULL)
        return;
    list->length = 0;
    list->head = NULL;
}

int main(){
    LinkedListType list;
    
    init(&list);
    add(&list, 0, 20);
    add_last(&list, 30);
    add_first(&list, 10);
    add_last(&list, 40);

    // list = (10,20,30,40)
    display(&list);

    // list = (10,20,30)
    del(&list, 3);
    display(&list);

    // list = (20,30)
    del(&list, 0);
    display(&list);

    printf("%s\n", is_in_list(&list, 20) == true ? "success" : "fail");
    printf("%d\n", get_entry(&list, 0));
    
    return 0;
}

연결 리스트로 구현된 리스트 사용 시 주의할 점

• 리스트의 항목들을 순차적으로 방문하면서 어떤 작업을 해야되는 경우에는 리스트 ADT가 제공하는 연산보다 연결 리스트가 제공하는 포인터를 이용한 연산이 훨씬 효율적 -> 따라서, 이런 경우 리스트 ADT보다는 연결 리스트를 이용하는 것이 나음
• 객체 지향 언어들은 Iterator(반복자)라는 개념으로 순차적으로 객체를 효율적으로 방문하면서 작업할 수 있는 각종 연산을 제공하고 있음

// 리스트 ADT 사용 -> 가능하지만 비효율적
// 리스트의 항목을 순차적으로 방문하면서 1씩 증가
void visit(LinkedListType *list){
	for(int i=0;i<get_length(list);i++){
    	data = get_entry(list,i);
        replace(list, pos, data+1);
    }
}

// 포인터 사용 -> 효울적인 구현
// 리스트의 항목을 순차적으로 방문하면서 1씩 증가
void visit(LinkedListType *list){
	ListNode *node = list->head;
    while(node != NULL){
    	node->data++;
        node = node->link;
    }
}

4.5 선형 리스트의 응용: 텍스트 에디터

라인 에디터(line editor): 라인 단위로 입력이나 삭제를 할 수 있음

<프로그램 4.5.1> 리스트 ADT를 사용한 라인 에디터

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

#define MAX_CHAR_PER_LINE 1000
#define MAX_NAME 256

void warning(const char*);
void error(const char*);

#define FALSE 0
#define TRUE 1

typedef struct 
{
    char a[MAX_CHAR_PER_LINE];
} element;

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

typedef struct{
    ListNode* head;
    int length;
} LinkedListType;

void insert_node(ListNode **phead, ListNode *p,ListNode *new_node){
    if((*phead) == NULL){
        new_node->link = NULL;
        (*phead) = new_node;
    }else if(p==NULL){
        new_node->link = (*phead);
        (*phead) = new_node;
    }else{
        new_node->link = p->link;
        p->link = new_node;
    }
}

void remove_node(ListNode **phead, ListNode *p, ListNode *removed){
    if(p== NULL){
        (*phead) = (*phead)->link; // 첫번째 노드 삭제
    }else{
        p->link = removed->link;
    }
    free(removed);
}

void init(LinkedListType* list)
{
    if (list == NULL)
        return;
    list->length = 0;
    list->head = NULL;
}

ListNode* get_node_at(LinkedListType* list, int pos)
{
    ListNode* tmp = list->head;
    if (pos < 0)
        return NULL;
    for (int i = 0; i < pos; i++) {
        tmp = tmp->link;
    }
    return tmp;
}

int get_length(LinkedListType* list)
{
    return list->length;
}

void add(LinkedListType* list, int pos, element data)
{
    ListNode* tmp;
    if ((pos >= 0) && (pos <= list->length)) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        if (node == NULL)
            error("memory allocate error");
        node->data = data;
        tmp = get_node_at(list, pos - 1); // 추가할 위치의 선행 노드의 주소 찾음
        insert_node(&(list->head), tmp, node);
        list->length++;
    }
}

void add_last(LinkedListType* list, element data)
{
    add(list, get_length(list), data);
}

void add_first(LinkedListType* list, element data)
{
    add(list, 0, data);
}

int is_empty(LinkedListType* list)
{
    if (list->head == NULL)
        return 1;
    else
        return 0;
}

void del(LinkedListType* list, int pos)
{
    if (!is_empty(list) && (pos >= 0) && (pos < list->length)) {
        ListNode* p = get_node_at(list, pos - 1);
        ListNode* removed = get_node_at(list, pos);
        remove_node(&(list->head), p, removed);
        list->length--;
    }
}

element get_entry(LinkedListType* list, int pos)
{
    if (pos >= get_length(list)) {
        error("location error");
    }
    ListNode* p = get_node_at(list, pos);
    return p->data;
}

void clear(LinkedListType* list)
{
    for (int i = 0; i < get_length(list); i++) {
        del(list, i);
    }
}

void display(LinkedListType* buffer)
{
    ListNode* node = buffer->head;
    printf("******************\n");
    for (int i = 0; i < buffer->length; i++) {
        printf("%s", node->data.a);
        node = node->link;
    }
    printf("******************\n");

}

void warning(const char *message){
    fprintf(stderr, "%s\n", message);
}

void error(const char* message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void help(){
    printf("******************\n");
    printf("i: input\n");
    printf("d: delete\n");
    printf("r: read\n");
    printf("w: write\n");
    printf("q: quit\n");
    printf("******************\n");
}

// 디스크 파일로부터 데이터를 읽음
void read_file(LinkedListType *buffer){
    char fname[MAX_NAME];
    FILE* fd;
    element p;

    if(!is_empty(buffer)){
        clear(buffer);
    }
    init(buffer);

    printf("File name: ");
    scanf("%s", fname);
    if((fd = fopen(fname,"r")) == NULL){
        warning("Not open");
        return;
    }

    while(fgets(p.a,MAX_CHAR_PER_LINE,fd)){
        add_last(buffer, p);
    }
    fclose(fd);
    display(buffer);
}

// 버퍼에 있는 데이터를 디스크 파일에 쓴다.
void write_file(LinkedListType *buffer){
    FILE* fd;
    char fname[MAX_NAME];
    element p;

    printf("File name: ");
    scanf("%s", fname);
    if ((fd = fopen(fname, "w")) == NULL) {
        printf("Not open\n");
        return;
    }

    for (int i = 0; i < get_length(buffer);i++){
        p = get_entry(buffer, i);
        fputs(p.a, fd);
    }
    fclose(fd);
    display(buffer);
}

// 하나의 라인을 지움
void delete_line(LinkedListType *buffer){
    int position;
    if(is_empty(buffer)){
        printf("No delete line\n");
    }else{
        printf("Write line number: ");
        scanf("%d", &position);
        del(buffer, position);
    }
    display(buffer);
}

// 하나의 라인 삽입
void insert_line(LinkedListType *buffer){
    int position;
    char line[MAX_CHAR_PER_LINE];
    element p;

    printf("Write line number: ");
    scanf("%d", &position);

    printf("Write line: ");
    fflush(stdin);
    fgets(line, MAX_CHAR_PER_LINE, stdin);

    strcpy(p.a, line);
    add(buffer, position, p);
    display(buffer);
}

void do_command(LinkedListType *buffer, char command){
    switch (command)
    {
    case 'i':
        insert_line(buffer);
        break;
    case 'd':
        delete_line(buffer);
        break;
    case 'r':
        read_file(buffer);
        break;
    case 'w':
        write_file(buffer);
        break;
    case 'q':
        break;
    }
}

// 라인 에디터 메인 프로그램
int main(){
    char command;
    LinkedListType buffer;

    init(&buffer);
    do{
        help();
        command = getchar();
        do_command(&buffer,command);
        fflush(stdin);
    } while (command != 'q');
}

<참고자료>
천인국 · 공용해 · 하상호 지음,『C언어로 쉽게 풀어쓴 자료구조』, 생능출판(2016)