1. 리스트

1. 리스트의 추상 자료형

- 리스트의 개념

리스트

: 목록 형태로 이뤄진 데이터 형식

 

노드 (Node, 마디)

: 리스트의 목록을 이루는 개별 요소

• 첫 번째 노드를 헤드 (Head, 머리) 라고 부르고 마지막 노드를 테일 (Tail, 꼬리) 이라고 부른다
• 리스트의 길이는 헤드부터 테일까지 이르는 노드 개수와 같다

 

ADT는 자료구조가 갖춰야 할 일련의 연산

리스트도 갖춰야 할 연산이 있는데

• Append : 리스트에 노드를 추가하는 연산
• Insert : 노드 사이에 노드를 삽입하는 연산
• Remove : 노드를 제거하는 연산
• GetAt : 특정 위치에 있는 노드를 반환하는 연산

---

- 리스트의 구현

리스트는 배열과 연결 리스트를 이용하여 구현할 수 있음

 

 

• 배열로 구현된 리스트
  • 장점
    • 구현이 간단
    • 속도가 빠름
  • 단점
    • 리스트의 크기가 고정됨

 

 

• 연결리스트로 구현된 리스트
  • 장점
    • 크기가 제한 x
    • 중간에서 쉽게 삽입하거나 삭제할 수 있는 유연한 리스트를 구현
  • 단점
    • 구현이 복잡
    • 임의 항목을 추출할려고 할 때 배열보다 시간이 오래 걸림

 

---

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