자료 구조, Linked List

자료 구조, Linked List

---

📌 Array 와 Linked List

Array	Linked List
데이터 검색(index 접근)	데이터 삽입 / 삭제(pointer접근)
정적메모리	동적메모리(Heap 영역)

배열과 링크드 리스트

---

✏️ 자기 참조 구조체

// 자기 참조 구조체

// 포인터(주소)로 연결하는 데이터. 데이터 적재문제 해결?

struct node

{

    // data1, data2는 구조체에 담을 수 있는 데이터 예시

    // 각각의 노드에 서로다른 유형의 여러 개 데이터를 저장할 수 있음

    int data1;

    char data2;

    struct node * link; // 포인터부

};

data부와 포인터부로 나누어져 있는 노드 구조체를 만든다.
일종의 붕어빵틀!
 
붕어빵틀을 이용해 여러 노드들(붕어빵)을 만들 수 있다.
data부는 한가지 데이터만 넣어도 되지만, 여러 유형의 데이터를 저장할 수 있다는 걸 보여주기 위해 integer타입과 charater타입 두가지로 이루어진 data부를 만들어 봤다.
 

---

✏️ 노드 생성 함수

// 새 노드 생성 함수

struct node *createNode(int data1, char data2)

{

    struct node *newNode = (struct node *)malloc(sizeof(struct node));

    newNode->data1 = data1;

    newNode->data2 = data2;

    newNode->link = NULL;

    return newNode;

};

앞서 만든 붕어빵틀로 newNode라는 붕어빵을 만들어 동적메모리(malloc)에 할당했다.
node 사이즈는 integer(4byte) + character(1byte)+pointer(4byte) = 9byte를 차지하는 동적메모리 생성!
 
화살표는 각 구조체의 속성들이다.
붕어빵 newNode의 data1에는 함수 파라미터로 들어온 int data1를 할당
붕어빵 newNode의 data2에는 함수 파라미터로 들어온 int data2를 할당해준다.
그리고 붕어빵 newNode의 포인터부에는 Null값을 할당해준다.
이 함수는 붕어빵 newNode를 반환한다.

---

✏️ head 설정

// pushfront, 새 노드를 Linked List 가장 앞에 삽입

// L.head가 변경되어야 함.

struct node *insterAtHead(struct node *head, int data1, char data2)

{

    struct node *newNode = createNode(data1, data2);

    // 새로 생성된 노드(newNode)가 head가 됨

    newNode->link = head;

    return newNode; // head포인터를 반환하면, 리스트 전체 구조가 반환됨.

};

Linked List는 head를 기준으로 데이터를 타고타고 접근한다.
그래서 Linked List 전체를 출력할때도 head값을 파라미터로 주고 받아야 한다.
 
그렇다면, 어떻게 head값을 찾을 수 있을까?
Null로 설정해준 포인터부(newNode->link)를 head값으로 지정해주면 된다.
head값에는 노드의 포인터(주소)값이 들어가는 것이다.
 

---

✏️ tail 설정

// 맨 끝 노드를 삭제하는 함수

struct node* popBack(struct node *head)

{

    // head가 NULL인 경우 처리

    if (head == NULL)

        return NULL;

    // 삭제할 노드와 이전 노드를 찾음

    struct node *delNode = head;

    struct node *prevNode = NULL;

    while (delNode->link != NULL)

    {

        prevNode = delNode;

        delNode = delNode->link;

    }

   

    // 이전 노드의 링크를 NULL로 설정

    if (prevNode != NULL)

        prevNode->link = NULL;

    else // 삭제할 노드가 head일 경우

        head = NULL;

    // 삭제할 노드 해제

    free(delNode);

    // 변경된 head 포인터 반환

    return head;

}

Linked List의 맨 끝을 tail이라고 한다.
linked List의 맨 끝 노드, tail의 포인터부를 NULL로 설정해준다.
 
head가 NULL인 경우 한 노드로 이루어진 Linked List인 것이다.
만약, head가 NULL이 아니라면, 여러 노드로 이루어진 것이므로 head부터 시작해 노드의 포인트가 NULL값이 아닐때까지 탐색을 한다.
포인터부가 NULL값이 나온다면 Linked List을 끝까지 탐색한 것이므로 tail에 도달했을 것이다.
이때 마지막 이전 노드의 포인트부에 NULL값을 할당해줘 tail노드를 바꿔주고 삭제할 노드의 메모리 할당을 해제해준다.
이렇게 되면 마지막 노드, tail이 바뀌고 기존의 tail 메모리는 메모리 영역에서 삭제할 수 있다.

---

✏️ 특정 key값 뒤로 새로운 노드 삽입

// insert, key 뒤에 새로운 노드를 삽입하는 함수

struct node *insertAfterKey(struct node *head, int key, int data1, char data2)

{

    // 새로운 노드 생성

    struct node *newNode = createNode(data1, data2);

    // key를 갖는 노드 찾음

    struct node *current = head;

    while (current != NULL)

    {

        if(current->data1 == key)

            break;

        current = current->link;

    }

   

    // key를 갖는 노드가 없는 경우, 노드를 삽입하지 않음

    if(current == NULL)

    {

        printf("Key not found in the list.\n");

        return head;

    }

    // key 노드 뒤에 newNode 삽입

    newNode->link = current->link; // 새로운 노드의 연결 -> 현재 노드와 연결된 노드

    current->link = newNode; // 현재노드의 연결 -> 새로운 노드

    return head;

};

특정 key값을 갖는 노드를 찾기위해서 head부터 탐색을 시작한다.
탐색하면서 노드의 data1의 값이 특정 key값과 이리하면 탐색을 멈춘다.
만약 특정 key값을 갖는 노드가 없을 경우에는 바로 head값을 반환하고 함수가 끝나도록 예외처리해주었다.
 
그리고 기존 연결을 바꿔준다.
어떻게? 포인터 접근을 바꿔서!

노드 연결 상태 변화

current->link값은 key값을 data1으로 가지는 노드의 다음 연결된 노드를 가르킨다.
link(포인터부)는 현재 노드의 포인터부가 가리키는 노드의 주소값임으로 이해하면 코드 이해가 쉽다.

---

📄 linkedlist.c

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

// 자기 참조 구조체 
// 포인터(주소)로 연결하는 데이터. 데이터 적재문제 해결?
struct node
{
    // data1, data2는 구조체에 담을 수 있는 데이터 예시
    // 각각의 노드에 서로다른 유형의 여러 개 데이터를 저장할 수 있음
    int data1;
    char data2;
    struct node * link; // 포인터부
};

// 새 노드 생성 함수
struct node *createNode(int data1, char data2)
{
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    newNode->data1 = data1;
    newNode->data2 = data2;
    newNode->link = NULL;
    return newNode;
};

// pushfront, 새 노드를 Linked List 가장 앞에 삽입
// L.head가 변경되어야 함.
struct node *insterAtHead(struct node *head, int data1, char data2)
{
    struct node *newNode = createNode(data1, data2);
    // 새로 생성된 노드(newNode)가 head가 됨
    newNode->link = head;
    return newNode; // head포인터를 반환하면, 리스트 전체 구조가 반환됨.
};

// insert, key 뒤에 새로운 노드를 삽입하는 함수
struct node *insertAfterKey(struct node *head, int key, int data1, char data2)
{
    // 새로운 노드 생성
    struct node *newNode = createNode(data1, data2);

    // key를 갖는 노드 찾음
    struct node *current = head;
    while (current != NULL)
    {
        if(current->data1 == key)
            break;
        current = current->link;
    }
    
    // key를 갖는 노드가 없는 경우, 노드를 삽입하지 않음
    if(current == NULL)
    {
        printf("Key not found in the list.\n");
        return head;
    }

    // key 노드 뒤에 newNode 삽입
    newNode->link = current->link; // 새로운 노드의 연결 -> 현재 노드와 연결된 노드
    current->link = newNode; // 현재노드의 연결 -> 새로운 노드

    return head;
};


// pushBack, 새 노드를 Linked List 맨 뒤에 삽입
struct node *pushBack(struct node *head, int data1, char data2)
{
    struct node *newNode = createNode(data1, data2);

    // 리스트가 비어 있다면, 맨끝 = 맨앞
    if(head == NULL)
    {
        return newNode;
    }
    else
    {
        // 맨 처음 노드부터 맨 끝 노드까지 탐색
        struct node *lastNode = head;
        while (lastNode->link != NULL)
        {
            lastNode = lastNode->link;
        }
        lastNode->link = newNode;
        return head; // head포인터를 반환하면, 리스트 전체 구조가 반환됨.
    }
};

// 맨 앞 노드를 삭제하는 함수
struct node* popFront(struct node *head)
{
    // head가 NULL인 경우
    if (head == NULL)
        return NULL;
    
    // 삭제할 노드와 다음 노드를 설정
    struct node *delNode = head;
    struct node *nextNode = head->link;

    // head를 다음 노드로 변경
    head = nextNode;

    // 삭제할 노들 해제
    free(delNode);

    // 변경할 head 포인터 반환
    return head;
}

// 맨 끝 노드를 삭제하는 함수
struct node* popBack(struct node *head)
{
    // head가 NULL인 경우 처리
    if (head == NULL)
        return NULL;

    // 삭제할 노드와 이전 노드를 찾음
    struct node *delNode = head;
    struct node *prevNode = NULL;
    while (delNode->link != NULL)
    {
        prevNode = delNode;
        delNode = delNode->link;
    }
    
    // 이전 노드의 링크를 NULL로 설정
    if (prevNode != NULL)
        prevNode->link = NULL;
    else // 삭제할 노드가 head일 경우
        head = NULL;

    // 삭제할 노드 해제
    free(delNode);

    // 변경된 head 포인터 반환
    return head;
}

// delete, key값을 갖는 노드를 삭제하는 함수
struct node* deleteNode(struct node *head, int key)
{
    struct node *current = head;
    struct node *pre = NULL;

    // head 노드가 key값을 갖는 경우
    if (current != NULL && current->data1 == key)
    {
        head = current->link;
        free(current);
        return head;
    }

    // 중간 노드나 마지막 노드가 key값을 갖는 경우
    while (current != NULL && current->data1 != key)
    {
        pre = current;
        current = current->link;
    }
    
    // key값을 갖는 노드를 찾는 경우
    if(current != NULL)
    {
        pre->link = current->link;
        free(current);
    }

    return head;
}

// key값을 갖는노드를 찾는 함수
struct node* search(struct node *head, int key)
{
    // head부터 시작해 key값을 갖는 노드 찾음
    struct node *current = head;
    while (current != NULL)
    {
        if (current->data1 == key)
            return current;
        current = current->link; // key값이 아니라면, 다음 노드로 넘어감.
    }
    
    // 다 탐색했는데도 key값을 가지는 노드가 없을 경우 NULL 반환
    return NULL;
}

// 리스트를 출력하는 함수
void printList(struct node *head)
{
    while (head != NULL)
    {
        printf("%d %c -> ", head->data1, head->data2);
        head = head->link;
    }
    printf("NULL\n");
}

int main()
{
    struct node *head = NULL;

    // 리스트에 새 노드 삽입
    head = insterAtHead(head, 1, 'A');
    head = insterAtHead(head, 2, 'B');
    head = insterAtHead(head, 3, 'C');

    // 리스트 맨 끝에 새 노드 추가
    head = pushBack(head, 4, 'D');
    head = pushBack(head, 5, 'E');

    // 리스트 출력
    printList(head);

    // 리스트 맨 앞 노드 삭제
    head = popFront(head);

    // 리스트 출력
    printList(head);

    // 리스트 맨 끝 노드 삭제
    head = popBack(head);
    
    // 리스트 출력
    printList(head);

    // key값이 1인 노드 찾기
    struct node *foundNode = search(head, 1);
    
    if(foundNode != NULL)
    {
        printf("data1 : %d, data2 : %c\n", foundNode->data1, foundNode->data2);
    }
    else
    {
        printf("Node not found!\n");
    }

    // key값이 2이 노드드 뒤에 새로운 노드를 삽입
    head = insertAfterKey(head, 2, 6, 'F');
    
    // 리스트 출력
    printList(head);

    head = deleteNode(head, 1);

    // 리스트 출력
    printList(head);

    return 0;
}