06 연결리스트1 (C언어로 쉽게 풀어쓴 자료구조)

6.1 리스트 추상 데이터 타입

리스트의 소개

L=(item0, item1, ... , item(n-1))

리스트는 순서와 위치를 가진다는 점에서 집합과는 다른 개념이다

항목, 삭제, 탐색을 해보자

그냥 일상적으로 작성하는 투두리스트 같은 거다!

 

리스트 ADT

-객체: n개의 element형으로 구성된 순서 있는 모임
-연산:
    insert(list, pos, item) ::= pos 위치에 item을 추가한다
    insert_last(list, item) ::= 맨 끝에 item을 추가한다
    insert_first(list, item) ::= 맨 처음에 item을 추가한다
    delete(list, pos) ::= pos 위치의 요소를 제거한다
    clear(list) ::= 리스트의 모든 요소를 제거한다
    get_entry(list, pos) ::= pos 위치의 요소를 반환한다
    get_length(list, pos) ::= 리스트의 길이를 구한다
    is_empty(list) ::= 리스트가 비어있는지 검사한다
    is_full(list) ::= 리스트가 꽉 찼는지 검사한다
    print_list(list) ::= 리스트의 모든 요소를 표시한다

그동안 반환함수는 peek였는데 여기선 get_entry를 쓴다

리스트 구현

• 배열로 구현하기: 간단한데 크기가 고정된다는 단점~
• 연결리스트로 구현하기: 포인터를 이용한다. 크기변화에 유연하다. 근데 i번째 항목을 꺼내자! 할 때는 배열보다 시간이 많이 걸린다

 

6.2 배열로 구현된 리스트

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

#define MAX_LIST_SIZE 100

typedef int element;
typedef struct {
    element array[MAX_LIST_SIZE];
    int size; //현재 리스트에 저장된 항목들의 개수
} ArrayListType;

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

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

//is_empty(비어있으면 1/아니면 0)
int is_empty(ArrayListType *L)
{
    return L->size == 0;
}

//is_full
int is_full(ArrayListType *L)
{
    return L->size == MAX_LIST_SIZE;
}

//get_entry
element get_entry(ArrayListType *L, int pos)
{
    if (pos<0 || pos>=L->size)
        error("위치 오류");
    return L->array[pos];
}

//print_list
void print_list(ArrayListType *L)
{
    int i;
    for(i=0; i<L->size; i++)
        printf("%d->", L->array[i]);
    printf("\n");
}

//insert_last
void insert_last(ArrayListType *L, element item)
{
    if(L->size >= MAX_LIST_SIZE){ //삽입할 빈 공간이 없으면 오류
        error("리스트 오버플로우");
    }
    L->array[L->size++] = item;
}

//insert
void insert(ArrayListType *L, int pos, element item)
{
    if(!is_full(L) && (pos >= 0) && (pos <= L->size)){
        for(int i=(L->size-1); i>=pos; i--)
            L->array[i+1] = L->array[i];
        L->array[pos]=item;
        L->size++;
    } 
}

//delete
element delete(ArrayListType *L, int pos)
{
    element item;

    if(pos<0 || pos>=L->size)
        error("위치 오류");
    item = L->array[pos];
    for(int i=pos; i<(L->size -1); i++)
        L->array[i] = L->array[i+1];
    L->size--;
    return item;
}

//테스트프로그램
int main(void)
{
    //ArrayListType을 정적으로 생성하고 ArrayListType을 가리키는
    //포인터를 함수의 매개변수로 전달한다
    ArrayListType list;

    init(&list);
    insert(&list, 0, 10); print_list(&list);
    insert(&list, 0, 20); print_list(&list);
    insert(&list, 0, 30); print_list(&list);
    insert_last(&list, 40); print_list(&list);
    delete(&list, 0); print_list(&list);
    return 0;
}

배열리스트코드를 작성해보았다. 포인터를 사용하려니 상당히 아리까리하군^^;;;

 

실행시간 분석

get_entry: O(1) 인덱스 사용해서 바로 접근하니까

삽입/삭제연산: 기존애들을 이동하는 걸 포함하니까 최악의 경우 O(n)

리스트의 맨 끝에서 진행된다면 O(1)

 

6.3 연결 리스트

연결리스트의 구조

배열리스트란 상자(노드)를 줄(링크)로 연결한 것!

상자는 데이터필드, 링크필드로 나뉜다.

데이터 필드: 우리가 저장하고 싶은 데이터가 들어간다
링크 필드: 다른 노드를 가리키는 포인터가 저장된다(마지막 노드는 NULL)

 

 

하나의 프로그램에는 동시에 여러 개의 연결리스트가 들어갈 수 있는데 이 구분은 연결리스트의 첫번째데이터로 한다.

그래서 첫번째 노드를 가리키고 있는 변수가 필수로 필요하다! 걔를 헤드포인터라고 부른다.

 

연결리스트는 배열에 비해서

1)삽입/삭제가 보다 용이(유연하다)

2)연속된 메모리 공간이 필요X

3)크기 제한 X

라는 장점이 있다

 

연결리스트의 종류

6장에서는 단순연결리스트만 다룰 것이고, 7장에서는 원형 연결리스트와 이중 연결 리스트를 다룰 것이다!

 

6.4 단순 연결 리스트

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

//노드의 정의
typedef int element;

typedef struct ListNode { //노드타입을 구조체로 정의한다
    element data;
    struct ListNode *link;
} ListNode;

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

//삽입연산
//insert_first
ListNode* insert_first(ListNode *head, element value)
{
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));
    p->data = value;
    p->link = head; //헤드 포인터 값을 복사
    head=p;         //헤드 포인터 변경
    return head;    //변경된 헤드포인터 반환
}

//insert
ListNode* insert(ListNode *head, ListNode *pre, element value)
{
     ListNode *p = (ListNode *)malloc(sizeof(ListNode));
     p->data = value;
     p->link = pre->link;
     pre->link = p;
     return head;
}

//삭제연산
//delete_first
ListNode* delete_first(ListNode *head)
{
    ListNode *removed;
    if(head==NULL) return NULL;
    //head 포인터의 값을 removed에 복사한다
    removed = head;
    head=removed->link;
    free(removed);
    return head;
}

//delete
ListNode* delete(ListNode *head, ListNode *pre)
{
    //제거할 애를 찾는다
    ListNode *removed;
    removed=pre->link;
    pre->link = removed->link;
    free(removed);
    return head;
}

//print_list
void print_list(ListNode *head)
{
    for(ListNode *p=head; p!=NULL; p=p->link)
        printf("%d->",p->data);
    printf("NULL\n");
}

//테스트 함수
int main(void)
{
    ListNode *head = NULL;

    for (int i=0; i<5; i++){
        head=insert_first(head, i);
        print_list(head);
    }
    for (int i=0; i<5; i++){
        head=delete_first(head);
        print_list(head);
    }
    return 0;
}

 

6.5 단순 연결 리스트의 연산 구현

삽입 연산 insert_first()

 

삽입연산 insert() _ 중간삽입

 

삭제 연산 delete_first()

 

삭제 연산 delete()

6.6 단순 연결 리스트의 응용 : 다항식

 

헤더노드의 개념

우리는 지금까지 제일 앞 head만 저장하는 헤드포인터만 써왔다. 근데 여기서는

size: 연결리스트 안 항목들의 개수
헤드: 첫 번째 노드
테일: 마지막 노드

이렇게 세 가지 요소를 포함한 헤더노드를 사용할 것이다.

헤더노드를 사용하면 맨 끝에 노드를 추가할 때 편리하다. 기존 것은 포인터를 사용해 끝까지 가야 추가할 수 있었으니까!

근데 주의할 점은 헤더노드를 사용하기 위해서는  항상 연결리스트를 생성한 다음 초기화해주어야 한다.

여기서는 create()함수를 이용해서 헤더노드를 동적으로 생성 및 초기화하겠다