Data Structure Chapter 3 연결 자료구조.md

Data Structure Chapter 3

연결 자료구조

• 노드: [데이터][링크] - 링크는 다음 데이터의 주소
• C에서는 포인터를 이용하여 구현한다고 보면 된다.

리스트 처음에 삽입

1. 삽입할 노드(X)에 대한 메모리 할당받아 포인터 new에 주소 저장
2. X의 데이터 필드에 데이터 저장
3. X의 링크 필드에 리스트의 첫 번째 노드 주소 저장
4. 리스트의 첫 번째 노드 주소를 담고 있는 포인터 변수에 X의 주소 저장

리스트 중간에 삽입 - 리스트가 NULL인 경우와 아닌 경우로 나뉜다.

Null인 경우

1. 삽입할 노드(X)에 대한 메모리 할당받아 포인터 new에 주소 저장
2. X의 데이터 필드에 데이터 저장
3. NULL 리스트의 포인터에 새 노드X의 주소 할당
4. X의 링크 필드에 NULL 저장하여 마지막 노드임을 표시

Null이 아닌 경우

1. 삽입할 노드(X)에 대한 메모리 할당받아 포인터 new에 주소 저장
2. X의 데이터 필드에 데이터 저장
3. X의 링크 필드에 리스트의 노드 중 X노드의 다음에 위치할 노드의 주소를 저장
4. 리스트에서 PRE-X노드(X노드를 가리킬 노드)의 링크 필드에 X의 주소를 저장

리스트 마지막에 삽입 - 이 경우도 리스트가 NULL인 경우와 아닌 경우로 나뉜다

Null인 경우는 중간에 삽입하는 경우와 같다.

Null이 아닐 경우

1. 삽입할 노드(X)에 대한 메모리 할당받아 포인터 new에 주소 저장
2. X의 데이터 필드에 데이터 저장
3. 리스트의 마지막 노드(링크필드가 NULL)를 WHILE문으로 찾는다.
4. 마지막 노드의 링크필드에 X의 주소를 저장한다.

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


typedef struct _node {
    char data[8];
    struct _node* link;
} Node;


typedef struct {
    Node* head;
} LinkedList_h;


LinkedList_h* createLinkedList_h(void) {
    LinkedList_h* L;
    L = (LinkedList_h*)malloc(sizeof(LinkedList_h));
    return L;
}


void freeLinkedList_h(LinkedList_h* L) {
    Node* p;
    while (L -> head != NULL) {
        p = L -> head;
        L -> head = L -> head -> link;
        free(p);
        p = NULL;
    }
}


void printList(LinkedList_h* L) {
    Node* p;
    printf("L = (");
    p = L -> head;
    while (p != NULL) {
        printf("%s", p -> data);
        p = p -> link;
        if (p != NULL) {
            printf(", ");
        }
    }
    printf(") \n");
}


// 첫 번째 노드로 삽입
void insertFirstNode(LinkedList_h* L, char* x) {
    Node* newNode;
    newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode -> data, x);
    newNode -> link = L -> head;
    L -> head = newNode;
}

// 중간에 노드를 삽입하는 연산
void insertMiddleNode(LinkedList_h* L, Node* pre, char* x) {
    Node* newNode;
    newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode -> data, x);
    if (L == NULL) {
        newNode -> link = NULL;
        L -> head = newNode;
    }
    else if (pre == NULL) {
        L -> head = newNode;
    }
    else {
        newNode -> link = pre -> link;
        pre -> link = newNode;
    }
}


// 마지막에 노드를 삽입하는 연산
void insertLastNode(LinkedList_h* L, char* x) {
    Node *newNode, *temp;
    newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode -> data, x);
    newNode -> link = NULL;
    if (L -> head == NULL) {
        L -> head = newNode;
        return;
    }

    temp = L -> head;
    while (temp -> link != NULL) {
        temp -> link;
    }
    temp -> link = newNode;
}

int main () {
    LinkedList_h *L;
    L = createLinkedList_h();
    printf("(1) Make NULL List! \n");
    printList(L);

    printf("(2) Insert [Web] Node! \n");
    insertFirstNode(L, "Web");
    printList(L);

    printf("(3) Insert [Fri] Node at last! \n");
    insertLastNode(L, "Fri");
    printList(L);

    printf("(4) Insert [Mon] Node at first! \n");
    insertFirstNode(L, "Mon");
    printList(L);

    printf("(5) Free Lists! \n");
    freeLinkedList_h(L);
    printList(L);

    return 0;
}

$ gcc 4-1.c -o 4-1.out && ./4-1.out
(1) Make NULL List! 
L = () 
(2) Insert [Web] Node! 
L = (Web) 
(3) Insert [Fri] Node at last! 
L = (Web, Fri) 
(4) Insert [Mon] Node at first! 
L = (Mon, Web, Fri) 
(5) Free Lists! 
L = ()