연결리스트 C 구현

1. 단일 연결 리스트의 C 구현

  ㅇ 구조체, 포인터, 함수, 동적 메모리 할당을 사용하여 구현

  ㅇ 노드의 구조체 정의
     - struct Node { struct Node *next; int data; }
        . struct Node *next : Node 구조체로 만든 다른 노드의 주소를 가리킴

  ㅇ 구조체 포인터에 동적 메모리 할당
     - struct 구조체이름 *구조체포인터이름 = malloc(sizeof(struct 구조체이름))

  ㅇ (추가편집중)


2. 노드 2개인 단일 연결 리스트 구현 例)

  ㅇ 구현 소스
      
#include <stdio.h>  // printf()
#include <string.h> // strcpy()
#include <stdlib.h> // malloc(), free()

typedef struct ListNode { // 연결 리스트의 노드 구조체
    struct ListNode *next; // 다음 노드 주소를 저장할 포인터
    char label[10]; // 라벨이름
    int data; // 데이터
} Node;

void displayAll(Node *head) { // 반복적으로 리스트 노드들을 방문하고, 각 노드 메모리 해제
    Node *curr = head->next; // 순회용 포인터에 첫째 노드의 주소 저장
    printf("(head) -> "); // 머리 노드 출력
    while(curr != NULL) { // 순회용 포인터가 NULL이 아니면 계속 노드를 방문
        if(curr->next != NULL) printf("(%s) %d -> ", curr->label, curr->data); // 현재 노드의 데이터 출력
        else printf("(%s) %d -> ", curr->label, curr->data); // 꼬리 노드의 출력
        curr = curr->next; // 순회용 포인터에 다음 노드의 주소 저장
    }
    printf("NULL \n");
}

Node *addAfter(Node *target, char *label, int data) { // 타깃 노드 뒤에 새 노드 생성 삽입
    Node *newNode = malloc(sizeof(Node)); // 새 노드 생성
    if(newNode != NULL) printf("새 노드 %s의 메모리 할당 OK \n", label);
    newNode->next = target->next; // 새 노드의 다음 노드에 타깃 노드의 다음 노드를 지정
    strcpy(newNode->label,label); // 새 노드에 라벨이름 저장
    newNode->data = data; // 새 노드에 데이터 저장
    target->next = newNode; // 타킷 노드의 다음 노드에 새 생성 노드를 지정
    return newNode;
}

void removeAfter(Node *target) { // 타깃 노드의 다음 노드를 삭제
    Node *removeNode = target->next; // 타깃 노드의 다음 노드 주소를 저장
    target->next = removeNode->next; // 타깃 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정
    printf("%s 메모리 해제 \n", removeNode->label);
    free(removeNode);
}

void freeAll(Node *head) {
    Node *curr = head->next; // 순회용 포인터에 첫째 노드의 주소 저장
    printf("%s 메모리 해제 ",head->label);
    free(head); // 현재 노드 메모리 해제
    Node *temp; // 다음 노드 주소를 임시 저장하려는 노드
    while(curr != NULL) { // 순회용 포인터가 NULL이 아니면 계속 노드를 방문
        temp = curr->next; // 현재 노드의 다음 노드 주소를 임시로 저장
        printf("%s 메모리 해제 ", curr->label);
        free(curr); // 현재 노드 메모리 해제
         curr = temp; // 순회용 포인터에 다음 노드 주소 저장
    }
    printf("\n");
}

int main() {
    Node *head = malloc(sizeof(Node));  // 구조체 포인터에 메모리 할당하며, 머리 노드 즉, 연결 리스트 생성
    strcpy(head->label,"head"); // 라벨이름 저장
    head->next = NULL; // 다음 노드 주소 
    displayAll(head); // 연결 리스트 차례로 방문 출력    

    addAfter(head,"node1",10); // node1을 헤드 노드 뒤에 삽입
    displayAll(head); // 연결 리스트 차례로 방문 출력
    
    addAfter(head,"node2",20); // node2을 헤드 노드의 뒤에 삽입
    displayAll(head); // 연결 리스트 차례로 방문 출력

    Node *node3 = addAfter(head,"node3",30); // node3을 헤드 노드의 뒤에 삽입
    displayAll(head); // 연결 리스트 차례로 방문 출력

    removeAfter(node3); // node3의 다음 노드 node2를 삭제
    displayAll(head); // 연결 리스트 차례로 방문 출력
    
    freeAll(head); // 연결 리스트 전체를 차례대로 메모리 해제

    return 0;
}

  ㅇ 수행 결과
      
(head) -> NULL
새 노드 node1의 메모리 할당 OK
(head) -> (node1) 10 -> NULL
새 노드 node2의 메모리 할당 OK
(head) -> (node2) 20 -> (node1) 10 -> NULL
새 노드 node3의 메모리 할당 OK
(head) -> (node3) 30 -> (node2) 20 -> (node1) 10 -> NULL
node2 메모리 해제
(head) -> (node3) 30 -> (node1) 10 -> NULL
head 메모리 해제 node3 메모리 해제 node1 메모리 해제