[C언어] 배열 기반 연결리스트(Linked List)

연결리스트 목차

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

 

 

     연결리스트

배열의 경우 자료를 읽기는 쉽지만 삽입/삭제는 어렵다. 많은 자료의 이동을 동반하기 때문이다.

이에 반해 연결리스트는 자료를 중간에 삽입하고 삭제하는데 꽤 편리하다. 

 

 

연결리스트는 next라는 자기참조객체를 통해서 구현된다. 

개체 하나를 삽입하고 싶다면 삽입할 위치의 전의 next 연결을 끊고

삽입하려는 개체와 연결한다. 삽입한 개체는 다음의 개체에 next연결을 넣는다.

삭제의 경우는 이전과 다음의 개체를 연결하고 삭제하려는 개체의 연결을 끊으면 된다.

 

 

 

     C언어 배열 기반 연결리스트 구현

C언어를 이용해서 배열기반의 연결리스트를 생성해보면 다음과 같다.

#include <stdio.h>
#define MAX_SIZE 20
struct Node{
    int data;
    Node* next;
};

Node Head;
Node nodes[MAX_SIZE];

int main(void){
    int i;
    Node* head = &Head;
    for(i=0; i<MAX_SIZE; i++){
        int data;
        scanf("%d", &data);
        nodes[i].data = data;
        if(head->next == (Node*)0x0){
            head->next = &nodes[i];
            head = head->next;
        }
    }
    for(i=0; i<MAX_SIZE; i++){
        printf("%dth node: %d\n", i, nodes[i].data);
    }
}

Head를 선언해서 이를 이용하여 연결리스트를 탐색한다.

 

 

 

 

     연결리스트 CRUD 구현

CRUD(생성, 읽기, 업데이트, 삭제)와 관련된 코드를

이어서 더 작성해보면 다음과 같을 것이다.

#include <stdio.h>
#define MAX_SIZE 20
struct Node{
    int id;
    int data;
    Node* next;
};

Node Head;
Node nodes[MAX_SIZE];
int lastNode = 0;

//배열공간에 새로운 데이터 삽입 성공시 1 반환, 실패 -1 반환
int create(int id, int data){
    if(lastNode != MAX_SIZE){
        nodes[lastNode++] = {id, data, NULL};
        return 1;
    }
    return -1;
}

//해당 id 개체를 찾으면 data 반환, 없으면 -1 반환
int search(int id){
    Node* p = Head.next;
    while(p){
        if(p->id == id) return p->data;
        else{
            p = p->next;
        }
    }
    return -1;
}

//해당 id 개체를 찾고 수정하면 1 반환, 실패하면 -1 반환
int update(int id, int data){
    Node* p = Head.next;
    while(p){
        if(p->id == id){
            p->data = data;
            return 1;
        }else{
            p = p->next;
        }
    }
    return -1;
}

//해당 id개체를 찾고 삭제 성공시 1 반환, 실패하면 -1 반환
int remove(int id){
    Node* p = Head.next;
    Node* prev;
    while(p){
        if(p->id == id){
            prev->next = p->next;
            p->next = NULL;
            p->data = 0;
            p->id = -1;
            return 1;
        }else{
            prev = p;
            p = p->next;
        }
    }
    return -1;
}

 

 

 

 

     이중연결리스트

단순 연결리스트는 next가 다음 개체만을 가르켰다면

이중연결리스트는 이전 개체와 다음개체를 모두 가르키도록

prev, next를 갖도록 한다.

이중 연결리스트로 작성하면 삭제부분이 더 편리하다.

삭제할 개체의 이전객체와 다음객체를 연결하기 더 쉽기 때문이다.

 

 

 

 

     C언어 배열 기반 이중연결리스트 구현

C언어를 이용해서 배열기반의 이중연결리스트를 생성해보면 다음과 같다.

#include <stdio.h>
#define MAX_SIZE 20
struct Node{
    int id;
    int data;
    Node* next;
    Node* prev;
};

Node Head;
Node nodes[MAX_SIZE];
int lastNode = 0;

//중략//

//해당 id개체를 찾고 삭제 성공시 1 반환, 실패하면 -1 반환
int remove(int id){
    Node* p = Head.next;
    while(p){
        if(p->id == id){
            p->prev->next = p->next;
            p->data = 0;
            p->id = -1;
            return 1;
        }else{
            p = p->next;
        }
    }
    return -1;
}

 

 

 

틀린 부분이 있다면 댓글 부탁드립니다.