[C언어] Heap기반 연결리스트(Linked list)

연결리스트 목차

1. 연결리스트  구조체 선언
2. 연결리스트 CRUD
3. 이중 연결 리스트
4. 이중 연결 리스트 CRUD 
5. Heap으로 구현한 연결리스트
6. Heap으로 구현한 이중 연결 리스트

 

 

     동적 할당 기반 연결리스트

동적할당을 하면 Heap 공간에 데이터가 저장된다.

이전에 다뤘던 배열기반 연결리스트는 데이터 공간을 미리 선언해두고 이용했기 때문에

데이터의 수를 삽입/삭제할 때 유동적으로 융통성있게 활용하는 것이 어려웠다.

그래서 이번에는 calloc을 이용해서 연결리스트를 구현해보고자한다.

 

동적할당이기 때문에 자료를 삭제할 때 free를 해주어서

메모리 공간을 다시 확보해줘야 하는 것을 기억해야한다.

 

     C언어  동적 할당 기반 연결리스트 구현

간단히 새 노드를 삽입하여 연결하는 부분만 살펴보면 다음과 같다.

    //새노드 연결
    newNode = (Node*)calloc(1, sizeof(Node));
    if(newNode == (Node*)0x0) return -1;

    //데이터 넣기
    newNode->id = id;
    newNode->data = data;

    //연결 관계 정리
    newNode->next = prev->next;
    prev->next = newNode;

 

 

     C언어  동적 할당 기반 연결리스트 CRUD 구현

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

struct Node{
    int id;
    int data;
    Node* next;
};

Node Head;

int create(int id, int data){
    Node* newNode;
    Node* prev = &Head;

    //마지막 노드까지 이동
    while(prev->next){
        prev = prev->next;
    }

    //새 노드 연결
    newNode = (Node*)calloc(1, sizeof(Node));
    if(newNode == (Node*)0x0) return -1;

    //데이터 넣기
    newNode->id = id;
    newNode->data = data;

    //연결 관계 정리
    newNode->next = NULL;
    prev->next = newNode;
    return 1;
}

//특정 노드 뒤에 삽입
int insert(Node* head, int id, int data){

    //새 노드 연결
    Node* newNode;
    newNode = (Node*)calloc(1, sizeof(Node));
    if(newNode == (Node*)0x0) return -1;

    //데이터 넣기
    newNode->id = id;
    newNode->data = data;

    //연결 관계 정리
    newNode->next = head->next;
    head->next = newNode;
    return 1;
}

Node* search(int id){
    Node* prev = &Head;
    while(prev->next){
        if(prev->next->id == id){
            return prev->next;
        }else{
            prev = prev->next;
        }
    }
    return NULL;
}

int update(int id, int data){
    Node* prev = &Head;
    while(prev->next){
        if(prev->next->id == id){
            prev->next->data = data;
            return 1;
        }else{
            prev = prev->next;
        }
    }
    return -1;
}

int remove(int id){
    Node* prev = &Head;
    while(prev->next){
        if(prev->next->id == id){
            prev->next = prev->next->next;
            free(prev->next);
            return 1;
        }else{
            prev = prev->next;
        }
    }
    return -1;
}

int main(void){
    create(1, 3);
    create(2, 5);
    create(3, 7);
    Node* loc = search(2);
    insert(loc, 4, 10);
    
    Node* prev = &Head;
    while(prev->next){
        printf("ID(%d)'s data: %d \n", prev->next->id, prev->next->data);
        prev = prev->next;
    }

    update(2, 9);
    printf("SEARCH id(2)'s data : %d\n",search(2)->data);

    remove(1);
    prev = &Head;
    while(prev->next){
        printf("ID(%d)'s data: %d \n", prev->next->id, prev->next->data);
        prev = prev->next;
    }
}

 

좀 지저분하다. 대충 이해하면 될 것같다.

 

     C언어  동적 할당 기반 이중 연결리스트 구현

오로지 썸네일만을 위한 이미지

이중연결리스트를 동적 할당으로 구현한 것을

간단히 insert부분과 remove부분만 보면 다음과 같다.

 

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

struct Node{
    int id;
    int data;
    Node* next;
    Node* prev;
};

Node Head;

//특정 노드 뒤에 삽입
int insert(Node* head, int id, int data){

    //새 노드 연결
    Node* newNode;
    newNode = (Node*)calloc(1, sizeof(Node));
    if(newNode == (Node*)0x0) return -1;

    //데이터 넣기
    newNode->id = id;
    newNode->data = data;

    //연결 관계 정리
    newNode->next = head->next;
    head->next = newNode;
    head->next->prev = newNode;
    newNode->prev = head;
    return 1;
}


int remove(int id){
    Node* p = &Head;
    Node* target;
    while(p->next){
        if(p->next->id == id){
            target = p->next;
            break;
        }else{
            p = p->next;
        }
    }

    if(target == (Node*)0x0) return -1;
    target->prev->next = target->next;
    if(target->next) target->next->prev = target->prev;
    free(target);
    return 1;
}