연결리스트

노드라는 개별 요소들이 포인터로 연결된 동적 자료 구조이다. 배열과 달리 연속된 메모리 공간을 필요로 하지 않으며 크기를 동적으로 조절할 수 있다. 

 

예시 ) 단일 연결 리스트 

 

struct Node* next를 이용해 다음 노드의 주소를 저장하는 단일 연결 방식 

 

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

// 노드 구조 정의
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 새로운 노드 생성
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 맨 앞에 노드 추가
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* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// 노드 삭제 (값 기준)
void deleteNode(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; // 값이 없으면 삭제 X

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

// 리스트 출력
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 메모리 해제
void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    Node* head = NULL;

    insertAtHead(&head, 10);
    insertAtTail(&head, 20);
    insertAtTail(&head, 30);

    printf("연결 리스트: ");
    printList(head);

    deleteNode(&head, 20);
    printf("삭제 후: ");
    printList(head);

    freeList(head);
    return 0;
}