[자료구조] C언어로 쉽게 풀어쓴 자료구조 : 6장 연결 리스트 Ⅰ

리스트 추상 데이터 타입

리스트는 항목들이 차례대로 저장되는 데이터 타입으로 즉 각 항목 간 순서의 개념이 존재한다.

리스트를 추상 데이터 타입으로 정의하면 다음과 같다.

 

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

 

배열을 이용한 리스트의 구현

배열을 이용하면 리스트를 쉽게 구현할 수 있지만 배열의 특성상 동적으로 크기를 변경하는 것이 어렵기 때문에 리스트의 크기가 고정된다는 것이 단점이다.

또한 중간에 새로운 데이터를 삽입하거나 중간 데이터를 삭제할 경우 기존 데이터들을 이동하여야 한다.

 

배열로 리스트를 구현하면 순차적인 메모리 공간기 할당되므로 이를 리스트의 순차적 표현이라고도 한다.

 

우선 기본적인 함수들을 구현한다.

 

#define SIZE 100

typedef int element; // 자료형을 element라는 이름으로 새로 정의

typedef struct {
	element array[SIZE];
	int n_elements; // 현재 리스트에 저장된 요소 수
}ArrayList;

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

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

// 리스트 검사 함수들
int is_full (ArrayList* L) {
	return L->n_elements == SIZE; // 요소 수가 size와 같으면 true이므로 1 반환
}

int is_empty(ArrayList* L) {
	return L->n_elements == 0; // 요소 수가 0이면 empty = true이므로 1 반환
}

// 임의의 위치의 요소 반환
element get_entry(ArrayList* L, int pos) {
	if (pos < 0 || pos >= L->n_elements) error("위치 오류");
	return L->array[pos];
}

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

 

다음으로 특정 위치에 요소를 추가 / 삭제하는 함수를 구현해보자. 앞서 설명했듯 리스트의 중간에 요소가 추가될 경우 기존 요소들의 이동이 필요하다.

그러나 리스트의 마지막 부분에 요소를 추가할 경우 다른 요소를 shift할 필요 없으므로 비교적 구현이 간단하다.

 

// 리스트의 마지막에 항목을 추가
void insert_last(ArrayList *L, element item) {
    if (L->n_elements > = SIZE) {
        error("리스트 오버플로우");
    }
    L->array[L->n_elements++] = item;
}

 

현재 리스트 안의 요소 개수를 저장하는 n_elements를 인덱스로 이용해 n_elements를 하나 증가시킨 자리에 item을 삽입한다.

 

이제 마지막이 아닌 맨 처음을 포함한 임의의 위치에 요소를 삽입하는 함수를 구현하자.

 

// 특정 위치에 항목을 추가 (맨 처음 포함)
void insert(ArrayList *L, int pos, element item) {
    if (!is_full(L)) && (pos >=0) && (pos <= L->n_elements) // insert할 수 있는 조건 만족시
    {
        for (int i = (L->n_elements-1); i>=pos; i++) {
            L->array[i+1] = L->array[i]; // 하나씩 옆으로 shift
        }
        L->array[pos] = item;
        L->n_elements++;
    }
}

 

pos 위치를 기준으로 오른쪽에 있는 요소들은 옆으로 하나씩 이동시킨 후 pos 위치에 요소를 삽입한다.

다음으로 pos 위치의 항목을 삭제하는 delete 함수를 구현해보자.

 

// delete한 pos 위치의 element를 반환하는 함수
element delete(ArrayList *L, int pos) {
    element item;
    
    if (pos < 0 || pos >= L->n_elements) error ("invalid pos");
    item = L->array[pos];
    for (int i = pos ; i<(L->n_elements-1); i++) {
        L->array[i] = L->array[i+1]; // 위의 insert 함수와 반대로.
    }
    L->n_elements--;
    return item;
}

// 반환 없이 delete만
void void_delete(ArrayList *L, int pos) {
    if (pos < 0 || pos >= L->n_elements) error ("invalid pos");
    for (int i = pos; i < (L->n_elements - 1); i++) {
        L->array[i] = L->array[i+1];
    }
    L->n_elements--;
}

 

배열의 요소들을 shift하는 과정은 insert와 같다. 책에는 delete를 하면서 그 위치의 요소를 반환해주는 함수를 구현하였는데 딱히 반환받을 필요가 없는 경우도 있을 것 같아 void형 함수도 함께 구현했다.

 

본문에 나와 있지 않은 clear(list), replace(list, pos, item), get_length(list)는 다음과 같이 구현해보았다.

* 틀릴 수 있음.. 오류 지적해주세요..

void clear_list(ArrayList *L) {
    if (is_empty(L))
        error("이미 비어있는 리스트");
    
    L->n_elements = 0;
}

void replace(ArrayList *L, int pos, element item) {
    L->array[pos] = item;
}

int get_length(ArrayList *L) {
    return L->n_elements;
}

 

시간복잡도

get_entry의 경우 인덱스를 사용해 항목에 바로 접근 가능하므로 O(1)

삽입, 삭제 연산의 경우 수행 시 다른 요소들을 이동해야 하므로 O(n) (단, 맨 끝에 삽입하는 경우는 O(1))

 

---

연결 리스트

동적으로 크기가 변할 수 있고 삭제/삽입 시 데이터 이동이 필요 없는 연결된 표현 (linked representation)에 대해 다룬다.

배열로 구현한 리스트가 연속된 메모리 주소 안에서 요소들이 연결되어 있는 구조라면 연결된 표현의 경우 메모리 상에 흩어진 데이터들을 포인터를 통해 서로 연결하는 구조이다.

동적 메모리를 통해 공간을 할당하기 때문에 크기가 고정되었던 배열 리스트에 비해 새 요소의 추가도 용이하다.

 

그러나 배열에 비해 구현이 어렵다는 단점이 있고 오류가 나기 쉬우며 포인터를 함께 저장하므로 메모리 공간을 많이 차지한다.

또한 i번째 index의 데이터를 찾아야 할 경우 첫 번째 데이터부터 접근해야 한다.

 

하나의 프로그램 안에 여러 개의 연결 리스트가 존재할 경우 첫 번째 데이터를 이용해 연결 리스트를 구분한다.

 

연결 리스트의 구조

연결 리스트는 메모리의 임의의 장소에 존재하는 노드의 집합이다.

다른 노드로 가기 위해서는 현재 노드가 가지고 있는 포인터를 이용하면 된다.

 

노드는 다음과 같이 데이터 필드와 링크 필드로 구성되어 있다.

데이터 필드에는 저장할 데이터가, 링크 필드에는 다른 노드를 가리키는 포인터가 저장된다.

앞서 설명했듯 연결리스트의 i번째 데이터(노드 안의)를 찾아야 할 경우 첫 번째 노드부터 순차적으로 찾아나가야 하는데 이를 위해 연결 리스트마다 첫 번째 노드를 가리키는 변수인 헤드 포인터가 필요하다.

마지막 노드의 링크 필드는 NULL로 설정한다. (더 이상 연결될 노드 없음)

---

단순 연결 리스트

단순 연결 리스트에서는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용해 모든 노드들이 연결된다.

 

노드의 정의

노드는 자기 자신을 참조하는 포인터를 포함하는 구조체인 자기 참조 구조체를 이용해 정의된다.

typedef int element;

typedef struct {
    element data;
    struct ListNode *Link; // 자기 자신을 참조하는 포인터
}ListNode;

포인터인 Link는 ListNode 자료형 포인터로 정의된다.

 

공백 리스트의 생성

첫 노드를 가리키는 포인터 head를 정의하면 연결리스트를 생성할 수 있다. 공백 리스트를 만들 경우 head를 NULL로 설정한다.

ListNode *head = NULL;

 

노드의 생성

새 노드를 생성할 때마다 동적 메모리 할당을 이용한다. head와 두 번째 노드를 생성한 후 서로 이어보자.

ListNode *head = NULL;

ListNode *head;
head = (ListNode *)malloc(sizeof(ListNode));
head->data = 10;
head->Link = NULL;

ListNode *node2;
node2 = (ListNode *)malloc(sizeof(ListNode));
node2->data = 20;
node2->Link = NULL;

//두 노드를 연결
head->Link = node2;

node2의 경우 현재 상황에서는 마지막 노드가 될 것이기에 link될 노드가 없어 노드의 Link 포인터에는 NULL이 할당된다.

head의 Link 포인터가 node2를 가리키게 하면 두 노드는 순서대로 연결된다.

---

단순 연결 리스트의 연산

헤드 포인터만 정의해서 이용한다.

 

insert_first()

리스트의 첫 부분에 새로운 노드를 추가한다.

ListNode* insert_first(ListNode *head, element value) {
    ListNode *n = (ListNode*)malloc(sizeof(ListNode));
    n->data = value;
    n->Link = head;
    head = n; // 맨 앞에 추가되었으므로 head 포인터는 추가된 노드
    return head;
}

 

insert()

리스트의 중간 부분에 새로운 노드를 추가한다.

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

위와 동작하는 방식은 비슷하다. 이전 노드와 추가한 노드를 연결해야 하므로 이전 노드를 인자로 받아오고 추가한 노드와 연결한다.

 

delete_first()

첫 번째 노드(head)를 삭제한다.

ListNode* delete_first(ListNode *head) {
    ListNode *removed;
    if (head == NULL) return NULL;
    removed = head;
    head = removed->Link;
    free(removed);
    return head;
}

우선 head 포인터의 값을 removed라는 새 포인터 변수에 복사한 후 removed 변수가 가리키는 Link (즉 다음 노드)를 head와 연결한다.

removed 변수는 사용이 끝났으므로 free를 통해 메모리를 반환해준다.

 

delete()

중간 노드를 삭제한다.

ListNode* delete(ListNode *head, ListNode *pre) {
    ListNode* removed;
    removed = pre->Link; // 이전 노드가 가리키는 노드 (삭제할 노드) 를 removed 변수에 복사
    pre->Link = removed->Link; // 원래 삭제할 노드가 가리키고 있던 노드를 pre가 가리키도록
    free(removed);
    return head;
}

위의 delete_first와 비슷하게 동작하지만 이전 노드를 인자로 받아와 삭제할 노드의 다음 노드를 가리키도록 해 준다.

 

print_list()

연결 리스트의 노드를 방문하는 방문 연산은 연결 리스트의 기본이 되는 연산이다. 이를 이용해 연결 리스트의 모든 노드를 방문해 값을 출력하는 함수를 정의하자.

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

노드의 링크 값이 NULL이 아니면 계속 링크를 따라 가며 노드를 방문하고 데이터를 출력한다.