[C] Linked List, 링크드 리스트

wrld_worthy·2023년 11월 3일

C

목록 보기

6/6

링크드 리스트

정의

링크드 리스트는 일반적인 배열처럼 연속적인 메모리 공간에 할당되지 않고, 각각의 노드가 데이터와 다음 노드를 가리키는 참조를 포함하여 체인처럼 연결된 데이터 구조이다. 배열과 달리, 링크드 리스트에서는 노드들이 메모리 상의 임의 위치에 존재할 수 있다.

구조

링크드 리스트의 기본 단위는 노드(Node)로, 각 노드는 두 부분으로 구성된다.

데이터(Data): 실제 저장하고자 하는 값
참조(Reference) 또는 링크(Link): 리스트의 다음 돈느 이전 노드의 주소를 가리킨다.

typedef struct Node {
    int data;         // 데이터 필드
    struct Node* next; // 다음 노드를 가리키는 포인터
} Node;

각 노드는 위 코드와 비슷한 구조를 갖는다.

링크드 리스트의 종류

단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드만을 가리키는 가장 간단한 형태이다.
데이터가 단방향으로 이동한다.
이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드 모두 가리킨다.
데이터가 앞 뒤로 이동이 자유롭지만, 추가적인 메모리를 필요로 한다.
원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리켜 순환하는 구조를 갖는다.

링크드 리스트의 연산과 시간 복잡도

삽입 연산

새로운 노드 생성
새 노드의 next포인터를 이전 노드가 가리키던 노드로 설정
이전 노드의 next포인터를 새 노드로 변경
삽입 연산의 시간 복잡도는 삽입 위치에 따라 다르다.

리스트의 시작에 삽입: O(1)
리스트의 중간이나 끝에 삽입 할 때: O(N) 최악의 경우 리스트 전체를 순회해야한다.
단, 삽입할 위치와 포인터 데이터를 가지고 있다면 O(1)이 될 수 있다.

삭제 연산

삭제할 노드의 이전 노드를 찾는다.
이전 노드의 next 포인터를 삭제할 노드의 다음 노드로 변경
삭제할 노드의 메모리를 해제

삭제 시간의 시간 복잡도는 삽입 시간과 유사하게 위치에 따라 다르다.

수정 연산

수정할 노드를 찾는다.
수정한다.

시간 복잡도는 최악의 경우 전체를 순회하기 때문에 O(N)이다.

구현 (삽입, 삭제, 수정)

1. 노드 생성

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

노드 생성에서는 malloc함수를 호출하여 Node 구조체 하나의 크기만큼 메모리를 동적으로 할당하고,
할당된 메모리 블록의 시작 주소를 반환한다. 반환된 주소는 Node* 타입으로 캐스팅 되어 newNode 포인터 변수에 저장된다. 이 포인터는 새로운 노드를 가리키게 된다.

malloc함수로 동적할당 + 메모리 반환받음 -> 메로리를 Node*타입으로 캐스팅 -> newNode에 할당하고 newNode는 새로운 노드를 가리키게 함.

2. 노드 삽입

// 머리에 삽입
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// 꼬리에 삽입
void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

// 주어진 노드 뒤에 삽입
void insertAfter(Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("prevNode is NULL\n");
        return;
    }
    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

insertAtHead
이 함수는 Head의 주소를 받아서 Head가 가리키리고 있는 주소를 newNode의 Next노드로 설정하도록하여 Head에 삽입한다.

inserAtTail
이 함수는 Head에서 부터 Next의 값이 Null이 될 때 까지 반복하여 끝 노드에 도착하면 끝노드의 Next를 newNode를 가리키게 하여 삽입한다.

insertAfter
이 함수는 이 전 노드를 Next를 newNode를 가리키게 하고 newNode의 Next를 전 노드의 Next를 가리키게 하여 중간에 삽입한다.

3. 노드 삭제

// 주어진 키를 가진 노드를 삭제
void deleteNodeByKey(Node** head, int key) {
    Node *temp = *head, *prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

deleteNodeByKey
이 함수는 temp 구조체 포인터에 head가 가리키는 주소를,
전 노드를 Null로 하여 가리키지 않는다.
head부터 순회하는데 head가 존재하고 key의 데이터를 가지고 있따면 temp를 free로 메모리를 날린다.
temp가 Null이고 data가 key 일때 까지 즉, tail까지 순회를 진행하면서 data가 key인 노드를 발견하면 free로 삭제한다.

4. 노드 검색

Node* findNode(Node* head, int key) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

findNode
이 함수는 head부터 시작하여 끝노드까지 순횔르 하는데 data가 key인 노드를 만나면 그 노드를 반환하고 아니라면 해당 노드의 Next를 해당 노드로 바꿔서 순회한다. 찾지 못하면 NULL을 반환한다.

5. 노드 수정

void updateNodeData(Node* node, int oldData, int newData) {
    while (node != NULL) {
        if (node->data == oldData) {
            node->data = newData;
            return;
        }
        node = node->next;
    }
    printf("data %d not found.\n", oldData);
}

updateNodeData
head를 입력 받아 순회를 시작하는데 Node의 데이터가 oldData인 노드를 만나면 newData로 초기화하고 종료한다.

6. 리스트 출력

void printList(Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

printList
이 함수는 head부터 순회하여 각 노드의 데이터를 출력한다.

7. 리스트 메모리 해제

void freeList(Node** head) {
    Node* current = *head;
    Node* next;

    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }

    *head = NULL;
}

freeList
이 함수는 head부터 순회를 시작하여 모든 노드를 free로 메모리 해제를 하고 마지막에 head의 포인터를 NULL로 초기화하는 함수이다.

main함수

int main() {
    Node* head = NULL;

    // 예시 데이터 삽입
    insertAtHead(&head, 10);
    insertAtTail(&head, 20);
    insertAtTail(&head, 30);
    insertAfter(head->next, 25); // 20 뒤에 25 삽입

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

    // 노드 검색
    Node* found = findNode(head, 25);
    if (found != NULL) {
        printf("25 found.\n");
    } else {
        printf("not found.\n");
    }

    // 노드 수정
    updateNodeData(head, 20, 21);

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

    // 노드 삭제
    deleteNodeByKey(&head, 21);

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

    // 메모리 해제
    freeList(&head);

    return 0;
}

wrld_worthy