리스트(List)란?

리스트(list), 선형 리스트(Linear list)란?

▶ 순서를 가진 항목들의 모임

 

▶ 집합: 항목간의 순서의 개념이 없음

 

리스트의 예

▶ 요일: (일요일, 월요일, ..., 토요일)

▶ 한글 자음의 모임: (ㄱ, ㄴ, ..., ㅎ)

▶ 카드: (Ace, 2, 3, ..., King)

▶ 핸드폰의 문자 메시지 리스트

리스트

 

리스트의 연산은 무엇이 있을까?

▶ 새로운 항목을 리스트의 끝, 처음, 중간에 추가한다.

▶ 기존의 항목을 리스트의 임의의 위치에서 삭제한다.

▶ 모든 항목을 삭제한다.

▶ 기존의 항목을 대치한다.

▶ 리스트가 특정한 항목을 가지고 있는지를 살핀다.

▶ 리스트의 특정 위치 항목을 반환한다.

▶ 리스트 안의 항목 개수를 센다.

▶ 리스트가 비었는지, 꽉 찼는지를 체크한다.

▶ 리스트 안의 모든 항목을 표시한다.

등 등..

 

그럼 위의 내용을 바탕으로 리스트의 ADT를 생성한다면?

리스트의 ADT

 

리스트 ADT의 사용 예시를 그림과 코드로 살펴보자.

리스트 ADT 예: 그림

리스트 ADT 예: 코드

 

리스트를 구현하는 방법

▶ 배열을 이용하는 방법

구현은 간단하지만, 삽입, 삭제 시에 오버헤드가 발생하고, 항목의 개수가 제한된다.

 

▶ 연결리스트를 이용하는 방법

구현은 복잡하지만, 삽입, 삭제가 효율적이며, 크기가 제한되지 않는다.

배열과 연결리스트를 이용한 리스트 구현

 

우선, 배열로 리스트를 구현해보자.

 

방법은 1차원 배열에 항목들을 순서대로 저장한다.

 

삽입 연산: 삽입 위치 다음의 항목들을 이동하여야 함.

1차원 배열 삽입 연산

 

삭제 연산: 삭제 위치 다음의 항목들을 이동하여야 함.

1차원 배열 삭제 연산

 

ArrayListType의 구현

▶ 항목들의 타입은 element로 정의

▶ list라는 1차원 배열에 항목들을 차례대로 저장

▶ length에 항목의 개수 저장

 

▶ is_empty 연산과 is_full 연산의 구현

 

ArrayListType의 삽입 연산

▶ add 함수는 먼저 배열이 포화상태인지를 검사하고 삽입 위치가 적합한 범위에 있는지를 검사한다.

▶ 삽입 위치 다음에 있는 자료들을 한 칸씩 뒤로 이동한다..

ArrayListType의 삽입 연산

 

ArrayListType의 삭제 연산

▶ 삭제 위치를 검사한다. (is_empty 기능을 포함)

▶ 삭제 위치부터 마지막 자료를 한 칸씩 앞으로 옮긴다.

ArrayListType의 삭제 연산

 

그 다음, 연결 리스트의 방법이다.

 

아까, 리스트를 표현하는 방법에는 2가지가 있다고 했다.

 

순차 표현: 배열을 이용한 리스트 표현

연결된 표현: 연결 리스트를 사용한 리스트 표현, 하나의 노드가 데이터와 링크로 구성되어 있고, 링크가 노드들을 연결한다.

 

 

연결된 표현

▶ 리스트의 항목들을 노드(node)라고 하는 곳에 분산하여 저장

▶ 다음 항목을 가리키는 주소도 같이 저장

▶ 노드 (node) : <항목, 주소> 쌍

▶ 노드는 데이터 필드와 링크 필드로 구성

데이터 필드: 리스트의 원소, 즉 데이터 값을 저장하는 곳

링크 필드: 다른 노드의 주소값을 저장하는 장소 (포인터)

▶ 메모리 안에서 노드의 물리적 순서가 리스트의 논리적 순서와 일치할 필요 없음

 

연결된 표현의 장단점

 

장점

▶ 삽입, 삭제가 보다 용이하다.

▶ 연속된 메모리 공간이 필요 없다.

▶ 크기 제한이 없다.

 

단점

▶ 구현이 어렵다.

▶ 오류가 발생하기 쉽다.

 

연결 리스트의 구조

 

▶ 노드 = 데이터 필드 + 링크 필드

노드

 

▶ 헤드 포인터(head pointer): 리스트의 첫 번째 노드를 가리키는 변수

헤드 포인터

 

▶ 노드의 생성: 필요할 때마다 동적 메모리 생성 이용하여 노드를 생성

노드의 생성

 

연결 리스트의 종류

연결 리스트의 종류

 

▶ 단순 연결 리스트

하나의 링크 필드를 이용하여 연결한다.

마지막 노드의 링크 값은 NULL

단순 연결 리스트

 

단순 연결 리스트의 삽입 연산 (1)

 

단순 연결 리스트의 삭제 연산 (1)

 

단순 연결 리스트의 구현

▶ 데이터 필드: 구조체로 정의

▶ 링크 필드: 포인터 사용

 

▶ 노드의 생성: 동적 메모리 생성 라이브러리 malloc 함수 이용

▶ 데이터 필드와 링크 필드 설정

 

▶ 두 번째 노드 생성과 첫 번째 노드와의 연결

 

▶ 헤드 포인터(head pointer)

연결 리스트의 맨 처음 노드를 가리키는 포인터

 

단순 연결 리스트의 삽입 연산 (2)

▶ 삽입 함수의 프로토타입

헤드포인터가 함수 안에서 변경되므로 헤드포인터의 포인터 필요

 

▶ 삽입의 3가지 경우

1) head가 NULL인 경우: 공백 리스트에 삽입

2) p가 NULL인 경우: 리스트의 맨 처음에 삽입

3) 일반적인 경우: 리스트의 중간에 삽입

 

▶ head가 NULL인 경우

head가 NULL이라면 현재 삽입하려는 노드가 첫 번째 노드가 된다. 따라서 head의 값만 변경하면 된다.

head가 NULL인 경우

 

▶ p가 NULL인 경우

p가 NULL이라면 새로운 노드를 리스트의 맨 앞에 삽입한다.

p가 NULL인 경우

 

▶ head와 p가 NULL이 아닌 경우
가장 일반적인 경우이다.

new_node의 link에 p->link값을 복사한 다음, p->link가 new_node를 가리키도록 한다.

head와 p가 NULL이 아닌 경우

 

방문 연산 코드(display)

▶ 방문 연산: 리스트 상의 노드를 순차적으로 방문

▶ 반복(iteration)과 순환(recursion) 기법을 모두 사용 가능

 

▶ 반복 버전(iteration)

 

▶ 순환 버전(recursion)

 

단순 연결 리스트의 삭제 연산(2)

▶ 삭제 함수의 프로토타입

 

▶ 삭제의 2가지 경우

1) p가 NULL인 경우: 맨 앞의 노드를 삭제

2) p가 NULL이 아닌 경우: 중간 노드를 삭제

 

▶ p가 NULL인 경우
연결 리스트의 첫 번째 노드를 삭제한다. 헤드 포인터 변경

 

▶ p가 NULL이 아닌 경우

removed 앞의 노드인 p의 링크가 removed 다음 노드를 가리키도록 변경

 

합병 연산 코드(concat)

▶ 합병 연산: 2개의 리스트를 합하는 연산

 

역순 연산 코드(reverse)

▶ 역순 연산: 리스트의 노드들을 역순으로 만드는 연산

 

탐색 연산 코드(search)

▶ 탐색 연산: 특정한 데이터 값을 갖는 노드를 찾는 연산

 

이를 바탕으로 simpleLinkedList를 전체 구현해본 결과는 다음과 같다.

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

typedef struct ListNode {
    int data;           // 데이터를 저장하는 변수
    struct ListNode *link;  // 다음 노드를 가리키는 포인터
} ListNode;

typedef int element;

// 노드 생성 코드
ListNode *create_node(element data, ListNode *link) {
    ListNode *new_node;
    new_node = (ListNode *)malloc(sizeof(ListNode));

    if(new_node == NULL)
        printf("메모리 할당 에러\n");

    new_node->data = data;
    new_node->link = link;

    return new_node;
}

// 리스트 삽입 연산
// phead: 리스트의 헤드 포인터의 포인터
// p: 선행 노드
// new_node: 삽입될 노드
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node) {
    if( *phead == 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;
    }
}

// 리스트 방문 연산
// iteration의 방법
void display(ListNode *head) {
    ListNode *p = head;
    while( p != NULL ) {
        printf("%d->", p->data);
        p = p->link;
    }
    printf("\n");
}

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

// 리스트 삭제 연산
// phead: 헤드 포인터에 대한 포인터
// p: 삭제될 노드의 선행 노드
// removed: 삭제될 노드
void remove_node(ListNode **phead, ListNode *p, ListNode *removed) {
    if( p != NULL ) {
        *phead = removed->link; // *phead = (*phead)->link;
    } else {
        p->link = removed->link;
    }
    free(removed);
}

// 리스트 합병 연산
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;
    }
}

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

// 리스트 탐색 연산
ListNode *search(ListNode *head, int x) {
    ListNode *p;    // ListNode *p = head;
    p = head;
    while( p != NULL ) {
        if( p->data == x )
            return p; // 탐색 성공
        p = p->link;
    }
    return p;   // 탐색 실패일 경우 NULL 반환
}

// main 연결 리스트 실행문
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 = reverse(list1);
    display(list1);

    p = search(list1, 20);
    if(p != NULL)
        printf("검색 결과: %d \n", p->data);

    return 0;
}

 

게시글이 너무 길어져서 원형 연결 리스트와 이중 연결 리스트, 연결 리스트의 응용은 다음 게시글에서 쓰도록 하겠다.

 

 

다음에 계속...