이중연결리스트 (C언어)

이중연결리스트를 이중 포인터로 선언할 수 도 있지만
이중연결리스트 구조체를 따로 선언해서 구현하는 것이 가독성과 유지보수에 더 좋다.

 

 

 

*  새로운 노드를 생성하는 함수가 있음

삽입함수 /  삭제함수가 n번째 위치에(를) 삽입 / 삭제하는 형식

---

 

이중연결리스트는 앞뒤노드와 다 연결해야 되기 때문에
뒤노드가 NULL인 경우도 인지하고 있어야 한다

 

 

if(temp->next)   ==   if( temp->next 이 참일때, 0이 아닐때 )  

 

---

 

그래서 뒤노드가 NULL이 아니면   뒤노드->prev = newNode   이걸 연결해 주는 거다

                                                 (앞노드->next)

 

---

 

이중연결리스트의 append 함수는

 

1번째 위치에서는 연결을 한 후
head가 NULL인 경우를 인지하고
new_node를 head로 설정해줘야 하는 것을 기억해야 한다

그 외 위치에서는
new_node 먼저 연결하고
뒤노드가 NULL 인 경우를 인지하면 된다

---

이중연결리스트의 delete함수는

1번째 위치에서는 삭제한 후
list->head가 NULL 아닌 경우에만 ( if(list->head) )   prev까지 연결해준다

그 외 위치에서는
temp 포인터를 활용해서  2개의 선을 연결해주면 된다
temp->next가 NULL 이 아닌 경우에만  prev도 연결해준다
(뒤노드가 있는 경우, 중간 위치인 경우)

 

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

typedef struct Node {       // 구조체 Node 선언
    char data;
    struct Node* prev;
    struct Node* next;
} Node;                    // typedef로 선언했을 때는 이게 자료형 이름

typedef struct {          // 구조체 이중연결리스트 선언
    Node* head;           // 구조체 Node (자료형)
    int size;
} DoublyLinkedList;

// 리스트 초기화
void initList(DoublyLinkedList* list) {    // 구조체 포인터
    list->head = NULL;                     // NULL로 초기화
    list->size = 0;
}

// 새로운 노드 생성
Node* createNode(char data) {      // 구조체 포인터 반환
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 리스트에 요소 추가 (add)
void add(DoublyLinkedList* list, int pos, char data) {    // 반환형 : void
    if (pos < 1 || pos > list->size + 1) {     // case 1
        printf("invalid position\n");       // 예외처리
        return;
    }
    
    Node* newNode = createNode(data);
    
    if (pos == 1) {                 // 맨 앞에 노드 추가   case 2
        newNode->next = list->head;
        if (list->head) list->head->prev = newNode;
        
        list->head = newNode;     // new_node를 head로 만들어주기
    } 
    else {                        // 중간 또는 끝에 노드 추가     case 3
        Node* temp = list->head;
        for (int i = 1; i < pos - 1; i++) temp = temp->next;
        
        newNode->next = temp->next;
        newNode->prev = temp;
        if (temp->next) temp->next->prev = newNode;   // 뒤노드가 NULL이 아닌 경우
        temp->next = newNode;
    }
    
    list->size++;
}

// 리스트에서 요소 삭제 (delete)
void delete(DoublyLinkedList* list, int pos) {
    if (pos < 1 || pos > list->size) {      // case 1
        printf("invalid position\n");
        return;
    }

    Node* temp = list->head;

    if (pos == 1) {                    // 첫 번째 요소 삭제    case 2
        list->head = temp->next;
        if (list->head) list->head->prev = NULL;
    } 
    else {                                // case 3
        for (int i = 1; i < pos; i++) temp = temp->next;
        temp->prev->next = temp->next;
        if (temp->next) temp->next->prev = temp->prev;
    }

    free(temp);                 // 메모리 해제
    list->size--;
}

// 리스트에서 특정 위치 요소 가져오기 (get)
void get(DoublyLinkedList* list, int pos) {
    if (pos < 1 || pos > list->size) {
        printf("invalid position\n");
        return;
    }

    Node* temp = list->head;
    for (int i = 1; i < pos; i++) temp = temp->next;
    
    printf("%c\n", temp->data);
}

// 리스트 출력 (print)
void print(DoublyLinkedList* list) {
    Node* temp = list->head;
    while (temp) {
        printf("%c", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    DoublyLinkedList list;
    initList(&list);         // 선언 후에 초기화를 꼭 해야한다. 
                             // 매개변수가 포인터이기 때문에 () 안에 주소를 넣는다

    int n;
    scanf("%d", &n); // 연산 개수 입력

    for (int i = 0; i < n; i++) {
        char op;
        int pos;
        char value;
        
        scanf(" %c", &op); // 연산 종류 입력
        
        if (op == 'A') { // 추가 연산
            scanf("%d %c", &pos, &value);
            add(&list, pos, value);
        } 
        else if (op == 'D') { // 삭제 연산
            scanf("%d", &pos);
            delete(&list, pos);
        } 
        else if (op == 'G') { // 특정 위치 값 출력
            scanf("%d", &pos);
            get(&list, pos);
        } 
        else if (op == 'P') { // 리스트 출력
            print(&list);
        }
    }

    return 0;
}

 

 

 

 

*  노드 삽입 함수가 유형이 두개 :  앞쪽에 노드 삽입 ,  뒤쪽에 노드 삽입

 

노드 추가 함수는  1. (if) 노드가 없는 경우 ,  2. 아닌 경우

노드 삭제 함수는   1. (if 예외처리) 삭제할 노드가 없는 경우 ,   2. 아닌 경우

 

여기 노드 삭제 함수는 while문으로 삭제할 data를 찾아서 그 노드를 삭제한다

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

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

// 이중 연결 리스트 구조체 정의
typedef struct {
    Node* head; // 리스트의 첫 번째 노드
} DoublyLinkedList;

// 리스트 초기화
void initList(DoublyLinkedList* list) {
    list->head = NULL;
}

// 앞쪽에 노드 삽입
void insertFront(DoublyLinkedList* list, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = list->head;

    if (list->head != NULL)
        list->head->prev = newNode;

    list->head = newNode;      // head 가 newnode를 가리키게 하면 됨
}

// 뒤쪽에 노드 삽입
void insertEnd(DoublyLinkedList* list, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (list->head == NULL) {
        newNode->prev = NULL;
        list->head = newNode;
        return;
    }

    Node* temp = list->head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    temp->next = newNode;
    newNode->prev = temp;
}

// 노드 삭제
void deleteNode(DoublyLinkedList* list, int data) {
    Node* temp = list->head;

    // 삭제할 노드 찾기
    while (temp != NULL && temp->data != data) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("삭제할 노드가 없습니다.\n");
        return;
    }

    // 앞 노드와 연결
    if (temp->prev != NULL)
        temp->prev->next = temp->next;
    else
        list->head = temp->next; // 삭제 노드가 헤드라면 갱신

    // 뒤 노드와 연결
    if (temp->next != NULL)
        temp->next->prev = temp->prev;

    free(temp);
}

// 앞에서 뒤로 출력
void displayForward(DoublyLinkedList* list) {
    Node* temp = list->head;
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 뒤에서 앞으로 출력
void displayBackward(DoublyLinkedList* list) {
    if (list->head == NULL) return;

    Node* temp = list->head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}

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

// 메인 함수
int main() {
    DoublyLinkedList list;
    initList(&list); // 리스트 초기화

    insertFront(&list, 10);
    insertEnd(&list, 20);
    insertEnd(&list, 30);
    insertFront(&list, 5);

    printf("앞에서 출력: ");
    displayForward(&list);  // 출력: 5 <-> 10 <-> 20 <-> 30 <-> NULL

    printf("뒤에서 출력: ");
    displayBackward(&list); // 출력: 30 <-> 20 <-> 10 <-> 5 <-> NULL

    deleteNode(&list, 20);

    printf("삭제 후 출력: ");
    displayForward(&list);  // 출력: 5 <-> 10 <-> 30 <-> NULL

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

    return 0;
}