(C언어) 이중 연결리스트( Doubly Linked List): 노드 추가 삭제

이중 연결리스트(Doubly Linked List)를 구현한 C언어 소스입니다.

이중 연결리스트는 각 노드가 다음 노드와 이전 노드를 가리키는 연결된 데이터 구조입니다.

아래의 소스에는 다음과 같은 기능이 구현되어 있습니다.

 

노드 생성 : createNode()

노드 초기화: initializeList()

노드를 리스트의 끝에 추가: append()

노드를 리스트의  맨 처음에 추가: prepend()

노드 삭제: deleteNode() - 헤드 노드 삭제, 특정 노드 삭제

리스트 출력: printList()

 

이중 연결리스트의 구조체 정의는 다음과 같이 정의되어 있습니다.

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

// 이중 연결리스트 구조체 정의
struct DoublyLinkedList {
    struct Node* head;
    struct Node* tail;
};

 

전체 코드는 다음과 같습니다.

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

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

// 이중 연결리스트 구조체 정의
struct DoublyLinkedList {
    struct Node* head;
    struct Node* tail;
};

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

// 이중 연결리스트 초기화
void initializeList(struct DoublyLinkedList* list) {
    list->head = NULL;
    list->tail = NULL;
}

// 노드를 이중 연결리스트의 끝에 추가
void append(struct DoublyLinkedList* list, int data) {
    struct Node* newNode = createNode(data);
    if (list->head == NULL) {
        list->head = newNode;
        list->tail = newNode;
    }
    else {
        list->tail->next = newNode;
        newNode->prev = list->tail;
        list->tail = newNode;
    }
}

// 노드를 이중 연결리스트에서 삭제
void deleteNode(struct DoublyLinkedList* list, struct Node* node) {
    if (node == NULL)
        return;

    if (node == list->head) {
        list->head = node->next;
        if (list->head != NULL)
            list->head->prev = NULL;
    }
    else if (node == list->tail) {
        list->tail = node->prev;
        list->tail->next = NULL;
    }
    else {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    free(node);
}

// 이중 연결리스트 출력
void printList(struct DoublyLinkedList* list) {
    struct Node* current = list->head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 이중 연결리스트 메모리 해제
void freeList(struct DoublyLinkedList* list) {
    struct Node* current = list->head;
    while (current != NULL) {
        struct Node* temp = current;
        current = current->next;
        free(temp);
    }
    initializeList(list);
}

int main() {
    struct DoublyLinkedList myList;
    initializeList(&myList);

    // 노드 추가
    append(&myList, 10);
    append(&myList, 20);
    append(&myList, 30);
    append(&myList, 40);

    // 리스트 출력
    printf("이중 연결리스트: ");
    printList(&myList);

    // 노드 삭제
    deleteNode(&myList, myList.head); // 첫 번째 노드 삭제

    // 리스트 다시 출력
    printf("헤드 노드 삭제 후: ");
    printList(&myList);

    // 특정 노드 찾아 삭제
    int nodeToDelete = 30;
    struct Node* current = myList.head;
    while (current != NULL) {
        if (current->data == nodeToDelete) {
            deleteNode(&myList, current);
            break;
        }
        current = current->next;
    }
    
    // 리스트 다시 출력
    printf("특정 노드(30) 삭제 후: ");
    printList(&myList);

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

    return 0;
}

(Output)

이중 연결리스트: 10 20 30 40 헤드 노드 삭제 후: 20 30 40 특정 노드 삭제 후: 20 40

(C언어) 이중 연결리스트( Doubly Linked List): 노드 추가 삭제

 

 

prepend(): 노드를 맨 처음에 추가하는 코드를 추가했습니다.

void prepend(struct DoublyLinkedList* list, int data) {
    struct Node* newNode = createNode(data);
    if (list->head == NULL) {
        list->head = newNode;
        list->tail = newNode;
    }
    else {
        newNode->next = list->head;
        list->head->prev = newNode;
        list->head = newNode;
    }
}

 

main() 함수에서 다음과 같이 사용하면 됩니다.

    // 노드를 맨 처음에 추가
    prepend(&myList, 5);

(C언어) 이중 연결리스트( Doubly Linked List): 노드 추가 삭제