(C) 자료구조 - 연결 자료구조와 단순 연결 리스트의 구조와 구현

※ 학습 일지를 쓰기 전, 순차 자료구조와 선형 리스트까지는 학습을 했었기 때문에 연결 자료구조부터 학습 일지를 써보려고 한다.

---

1. 연결 자료구조의 개념

- 순차 자료구조 구현 방식 및 한계

논리적인 순서와 물리적인 순서가 같기 때문에 원소 위치를 찾아 액세스하기 쉽지만, 삽입이나 삭제 연산을 한 다음 연속적인 물리적 위치를 유지하기 위해 원소를 옮기는 추가 작업을 해야 하며 그만큼 시간이 든다.

 

또한, 배열을 이용하여 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 안고 있다.

 

- 순차 자료구조의 연산 시간과 저장 공간에 대한 문제를 개선한 자료 표현 방법

1. 연결 자료구조(Linked Data Structure)

-> 원소의 논리적인 순서와 물리적인 순서가 일치하지 않아도 된다.

-> 각 원소에 저장되어 있는 다음 원소의 주소(링크)에 의해 순서가 연결되는 구현 방식이라 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.

<원소, 주소> 단위로 구성되며, 이를 노드라고 한다.

• 데이터 필드(Data Field) : 원소값을 저장
• 링크 필드(Link Field) : 다음 노드의 주소를 저장 / 포인터 변수를 사용하여 주소값을 저장하며, 포인터 또는 링크 또는 참조라고도 한다.

-> 각 노드의 필드에 저장한 값은 포인터의 점 연산자(.)를 사용해 액세스한다.

 

연결리스트는 노드를 연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트로 나눌 수 있다.

 

<리스트 노드의 구조체>

typedef struct Node {
    char data[4];
    struct Node* link;  // 다음 노드를 가리키는 포인터
};

---

2. 단순 연결 리스트

2-1. 단순 연결 리스트의 개념

노드의 링크 필드가 하나이며, 링크 필드는 다음 노드와 연결되는 구조이다.

연결 리스트, 선형 연결 리스트, 단순 연결 선형 리스트라고도 한다.

 

2-2. 단순 연결 리스트에서 삽입 연산

1. 삽입할 노드를 준비한다.

2. 새 노드의 데이터 필드에 값을 저장한다.

3. 새 노드의 링크값을 저장한다.

4. 리스트의 앞 노드에 새 노드를 연결한다.

 

2-3. 단순 연결리스트에서 삭제 연산

1. 삭제할 노드의 앞 노드를 찾는다.

2. 앞 노드에서 삭제할 노드의 링크 필드값을 저장한다.

3. 삭제한 노드의 앞 노드와 삭제한 노드의 다음 노드를 연결한다.

-> 삭제된 노드의 링크 필드가 계속 연결되어 있지만,  앞의 노드가 연결되어 있지 않기 때문에 논리적을 제외된 노드가 된다.

 

2-4. 단순 연결 리스트의 알고리즘 프로그램

// 단순 연결 리스트의 노드 구조를 구조체로 정의
typedef struct ListNode {
    char data[4];
    struct ListNode* link;
} listNode;
 
// 리스트 시작을 나타내는 head 노드를 구조체로 정의
typedef struct {
    listNode* head;
} linkedList_h;

 

1. 첫 번째 노드에 삽입하는 알고리즘

// 첫 번째 노드로 삽입하는 연산
void insertFirstNode(linkedList_h* L, char* x) {
    listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode));  // 삽입할 새 노드 할당
    strcpy(newNode->data, x);                              // 새 노드의 데이터 필드에 x 저장
    newNode->link = L->head;
    L->head = newNode;

 

2. 중간 노드에 삽입하는 알고리즘

// 노드를 pre 뒤에 삽입하는 연산
void insertMiddleNode(linkedList_h* L, listNode* pre, char* x) {
    listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode));
    strcpy(newNode->data, x);
    if (L->head == NULL) {                            // 공백 리스트인 경우
        newNode->link = NULL;                // 새 노드를 첫 번째이자 마지막 노드로 연결
        L->head = newNode;
    }
    else if (pre == NULL) {                            // 삽입 위치를 지정하는 포인터 pre가 NULL인 경우
        newNode->link = L->head;                // 새 노드를 첫 번째 노드로 삽입
        L->head = newNode;
    }
    else {
        newNode->link = pre->link;                // 포인터 pre의 노드 뒤에서 새 노드 연결
        pre->link = newNode;
    }
}

 

3. 마지막 노드에 삽입하는 알고리즘

// 마지막 노드로 삽입하는 연산
void insertLastNode(linkedList_h* L, char* x) {
    listNode* newNode;
    listNode* temp;
    newNode = (listNode*)malloc(sizeof(listNode));
    strcpy(newNode->data, x);
    newNode->link = NULL;
    if (L->head == NULL) {            // 현재 리스트가 공백인 경우
        L->head = newNode;        // 새 노드를 리스트이 시작 노드로 연결
        return;
    }
    // 현재 리스트가 공백이 아닌 경우
    temp = L->head;
    while (temp->link != NULL) temp = temp->link;  // 현재 리스트의 마지막 노드를 찾음
    temp->link = newNode;  // 새 노드를 마지막 노드(temp)의 다음 노드로 연결
}

 

- 단순 연결 프로그램 1

#include <stdio.h>
#include "LinkedList.h"
 
int main(void) {
    linkedList_h* L;
    L = createLinkedList_h();
    printf("(1) 공백 리스트 생성하기! \n");
    printList(L);
 
    printf("\n(2) 리스트에 [수] 노드 삽입하기! \n");
    insertFirstNode(L, "수");
    printList(L);
 
    printf("\n(3) 리스트에 마지막에 [금] 노드 삽입하기! \n");
    insertLastNode(L, "금");
    printList(L);
 
    printf("\n(4) 리스트 첫 번째에 [월] 노드 삽입하기! \n");
    insertFirstNode(L, "월");
    printList(L);
 
    printf("\n(5) 리스트 공간을 해제하여 공백 리스트로 만들기! \n");
    freeLinkedList_h(L);
    printList(L);
 
    getchar(); return 0;
}

 

4. 노드를 삭제하는 알고리즘

// 리스트에서 노드 p를 삭제하는 연산
void deleteNode(linkedList_h* L, listNode* p) {
    listNode* pre;                    // 삭제할 노드의 선행자 노드를 나타낼 포인터
    if (L->head == NULL) return;  // 공백리스트라면 삭제 연산 중단
    if (L->head->link == NULL) {  // 리스트에 노드가 한 개만 있는 경우
        free(L->head);                // 첫 번째 노드를 메모리에서 해제하고
        L->head = NULL;            // 리스트 시작 포인터를 NULL로 설정
        return;
    }
    else if (p == NULL) return;    // 삭제할 노드가 없다면 삭제 연산 중단
    else {                                // 삭제할 노드 p의 선행자 노드를 포인터 pre를 이용해 찾음
        pre = L->head;
        while (pre->link != p) {
            pre = pre->link;
        }
        pre->link = p->link;        // 삭제할 노드 p의 선행자 노드와 다음 노드를 연결
        free(p);
    }
}

 

5. 노드를 탐색하는 알고리즘

// 리스트에서 x 노드를 탐색하는 연산
listNode* searchNode(linkedList_h* L, char* x) {
    listNode* temp;
    temp = L->head;
    while (temp != NULL) {
        if (strcmp(temp->data, x) == 0) return temp;
        else temp = temp->link;
    }
    return temp;
}

 

6. 노드 순서를 역순으로 바꾸는 알고리즘

// 리스트의 노드 순서를 역순으로 바꾸는 연산
void reverse(linkedList_h* L) {
    listNode* p;
    listNode* q;
    listNode* r;
 
    p = L->head;                // 포인터 p를 첫 번째 노드에 설정
    q = NULL;
    r = NULL;
 
    // 리스트의 첫 번째 노드부터 링크를 따라 다음 노드로 이동하면서
    // 노드 간의 연결을 바꿈
    while (p != NULL) {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    L->head = q;
}

 

- 단순 연결 리스트 프로그램2

#include <stdio.h>
#include <stdlib.h>
#include "LinkedList.h"
 
int main(void) {
    linkedList_h* L;
    listNode* p;
    L = createLinkedList_h();        // 공백 리스트 생성
 
    printf("(1) 리스트에 [월],[수],[일] 노드 삽입하기! \n");
    insertLastNode(L, "월"); insertLastNode(L, "수"); insertLastNode(L, "일");
    printList(L);
 
    printf("\n(2) 리스트에서 [수] 노드 탐색하기! \n");
    p = searchNode(L, "수");
    if (p == NULL) printf("찾는 데이터가 없습니다.\n");
    else printf("[%s]를 찾았습니다.\n", p->data);
 
    printf("\n(3) 리스트의 [수] 뒤에 [금] 노드 삽입하기! \n");
    insertMiddleNode(L, p, "금");
    printList(L);
 
    printf("\n(4) 리스트에서 [일] 노드 삭제하기! \n");
    p = searchNode(L, "일");        // 삭제할 노드 위치 p를 찾음
    deleteNode(L, p);            // 포인터 p 노드 삭제
    printList(L);
 
    printf("\n(5) 리스트 순서를 역순으로 바꾸기! \n");
    reverse(L);
    printList(L);
 
    freeLinkedList_h(L);        // 리스트의 메모리 해제
    getchar();
 
    return 0;
}