[c언어] 링크드리스트(Linked List)

프로그래밍

[c언어] 링크드리스트(Linked List)

업글 2021. 1. 13. 06:39

안녕하세요 업글입니다! 이번 포스팅에서는 링크드리스트에 대해서 설명드리겠습니다.

링크드리스트에 대한 설명

각 노드끼리 연결되어 자료를 관리하는 자료구조입니다. 포인터를 통해서 노드에서 다른노드를 가르킴으로써 노드끼리 연결할 수 있습니다. 그러므로 각 노드에는 노드를 가르킬 수 있는 포인터를 포함하고 있습니다.

링크드리스트를 이해하기 위해서는 포인터, 힙, 동적 메모리 할당에 대한 이해가 필요합니다.

각각에 대해서 간단하게 설명하도록 하겠습니다.

1) 포인터

포인터란 메모리의 주소를 저장할 수 있는 변수입니다.

변수를 선언 시 해당 변수는 메모리의 어떠한 영역에 위치하게 됩니다. 이 때 어떤 영역에 위치하는 지 표현 하는 것이 주소입니다. 각 변수는 유일한 주소를 가지게 됩니다. 포인터가 주소를 저장하는 것을 주소를 가르킨다라고 표현하기도 합니다. 그러므로 포인터는 가리키는 메모리의 주소를 통해서 해당 주소의 변수에 접근하여 값을 읽어오거나 수정할 수 있습니다. 링크드리스트에서는 노드 포인터를 통해서 연결하고자 하는 노드의 주소를 가르키게 됩니다.

2) 힙과 동적 메모리 할당

힙은 메모리영역 중 하나로 프로그램이 실행되며 필요한 만큼 할당하여 사용할 수 있는 메모리 영역을 말합니다. 힙 영역에서 사용 할 메모리를 할당받는 것을 동적 메모리 할당이라고 합니다. malloc을 통해서 동적 메모리 할당을 하며 할당받은 메모리를 해제하기 위해서는 free를 사용하게 됩니다. 동적 메모리 할당 후 할당된 메모리 영역을 미 사용 시에는 free를 통해서 무조건 해제 해야 한다는 점 주의바랍니다.

프로그램 실행 시에 사용 해야 할 메모리의 크기가 결정되는 상황에서 동적 메모리 할당이 필요하게 됩니다. 링크드리스트는 데이터가 입력될 때 노드를 힙 영역에 할당하고 삭제할 때 노드를 힙 영역에서 해제하게 됩니다. 그러므로 링크드리스트는 배열과 다르게 프로그램 실행 시에 크기가 변경될 수 있으며 힙 영역에서 사용할 공간이 있을 때 까지 크기를 증가시킬 수 있다는 장점이 있습니다.

링크드리스트 종류

링크드리스트는 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked List)로 나눌 수 있습니다. 이는 단방향 연결리스트, 양방향 연결리스트로도 표현되곤 합니다. 단일 연결 리스트는 노드가 1개의 노드를 가르키는 구조이지만 이중 연결 리스트는 노드가 2개의 노드를 가리키는 구조입니다. 단일 연결 리스트는 한방향으로 탐색할 수 있지만 이중 연결 리스트는 양방향으로 탐색할 수 있다는 장점이 있습니다.

링크드리스트 사용 이유

링크드리스트는 데이터 삽입 및 삭제가 빈번하게 일어나는 경우 주로 사용할 수 있습니다. 어레이 리스트와 비교했을 때 어레이 리스트의 경우 중간 인덱스에 데이터를 삽입하거나 삭제해야하는 경우 삽입 및 삭제 후 데이터들을 1인덱스씩 이동 시켜 줘야 하기 때문에 연산시간이 오래 걸리게됩니다.

링크드리스트의 경우 데이터 삽입 시 노드를 추가하고 해당하는 위치에서 기존 노드들의 연결을 끊고 기존노드들과 새로운 노드에 연결하면됩니다. 데이터 삭제 시 이전 노드와 다음 노드를 연결하고 해당 노드를 해제하여 삭제하면 됩니다.그러나 탐색 시 이진 탐색(bineary search)과 같은 방법을 사용할 수 없고 순차적으로 진행해야하며 인덱스 참조가 불가능하고 순차적으로 노드를 이동해가며 데이터의 값을 읽어 와야 된다는 단점이 있습니다.

단일 연결리스트 코드

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

#define NO (0)
#define YES (!NO)

typedef struct ST_Node {
    int32_t data;
    struct ST_Node* next;
}ST_Node;

typedef struct ST_LinkedList {
    int32_t size;
    ST_Node* front;
    ST_Node* back;
}ST_LinkedList;

void LinkedListInit(ST_LinkedList * linkedList)
{
    linkedList->size = 0;
    linkedList->front = NULL;
    linkedList->back = NULL;
}

void LinkedListDelete(ST_LinkedList* linkedList)
{
    int32_t i;
    ST_Node* del;

    for(i = 0; i < linkedList->size; i++){
        del = linkedList->front;
        linkedList->front = linkedList->front->next;
        free(del);
    }

    LinkedListInit(linkedList);
}

int32_t IsLinkedListEmpty(ST_LinkedList* linkedList)
{
    int32_t result;

    if (linkedList->size == 0) {
        result = YES;
    }
    else {
        result = NO;
    }

    return result;
}

void LinkedListFrontPush(ST_LinkedList* linkedList, int32_t data)
{
    ST_Node* add;

    add = (ST_Node*)malloc(sizeof(ST_Node));

    if (add == NULL) {
        printf("heap is full\n");
    }
    else {
        add->data = data;
        add->next = linkedList->front;
        linkedList->front = add;

        if (IsLinkedListEmpty(linkedList) == YES) {
            linkedList->back = add;
        }

        linkedList->size++;
    }
}

int32_t LinkedListFrontPop(ST_LinkedList* linkedList)
{
    int32_t result = 0;
    ST_Node* del;

    if (IsLinkedListEmpty(linkedList) == YES) {
        printf("linkedlist is empty\n");
    }
    else {
        result = linkedList->front->data;
        del = linkedList->front;
        linkedList->front = linkedList->front->next;
        free(del);
        linkedList->size--;
    }

    return result;
}

void LinkedListBackPush(ST_LinkedList* linkedList, int32_t data)
{
    ST_Node* add;

    add = (ST_Node*)malloc(sizeof(ST_Node));

    if (add == NULL) {
        printf("heap is full\n");
    }
    else {
        add->data = data;
        add->next = NULL;
       
        if (IsLinkedListEmpty(linkedList) == YES) {
            linkedList->front = add;
            linkedList->back = add;
        }
        else {
            linkedList->back->next = add;
            linkedList->back = add;
        }
        linkedList->size++;
    }
}

int32_t LinkedListBackPop(ST_LinkedList* linkedList)
{
    int32_t result = 0;
    ST_Node* temp;

    if (IsLinkedListEmpty(linkedList) == YES) {
        printf("linkedlist is empty\n");
    }
    else {
        result = linkedList->back->data;
        temp = linkedList->front;

        while (temp->next != NULL && temp->next->next != NULL) {
            temp = temp->next;
        }
        temp->next = NULL;
        free(linkedList->back);

        linkedList->back = temp;
        linkedList->size--;
    }

    return result;
}

void LinkedListInsertion(ST_LinkedList* linkedList, uint32_t position, int32_t data)
{
    int32_t i;
    ST_Node* add;
    ST_Node* cur;

    if (position > linkedList->size) {
        printf("position error\n");
    }
    else if (position == 0) {
        LinkedListFrontPush(linkedList, data);
    }
    else if (position == linkedList->size) {
        LinkedListBackPush(linkedList, data);
    }
    else {
        add = (ST_Node*)malloc(sizeof(ST_Node));

        if (add == NULL) {
            printf("heap is full\n");
        }
        else {
            cur = linkedList->front;
            for (i = 1; i < position; i++) {
                cur = cur->next;
            }
            add->data = data;
            add->next = cur->next;
            cur->next = add;         
            linkedList->size++;
        }
    }
}

int32_t LinkedListPop(ST_LinkedList* linkedList, uint32_t position)
{
    int32_t result = 0;
    int32_t i;
    ST_Node* cur, *del;

    if (IsLinkedListEmpty(linkedList) == YES) {
        printf("linkedlist is empty\n");
    }
    else {
        if (position >= linkedList->size) {
            printf("position error\n");
        }
        else if (position == 0) {
            result = LinkedListFrontPop(linkedList);
        }
        else if (position == linkedList->size-1) {
            result = LinkedListBackPop(linkedList);
        }
        else {
            cur = linkedList->front;
            for (i = 1; i < position; i++) {
                cur = cur->next;
            }
            result = cur->next->data;
            del = cur->next;
            cur->next = cur->next->next;
            free(del);
            linkedList->size--;
        }
    }

    return result;
}

void LinkedListPrint(ST_LinkedList* linkedList)
{
    ST_Node* cur;
    int32_t i;

    cur = linkedList->front;
    for (i = 0; i < linkedList->size; i++) {
        printf("i=%d, data=%d\n", i, cur->data);
        cur = cur->next;
    }
}


int main()
{
    ST_LinkedList linkedList;
    int32_t i;
    int32_t data[3];

    LinkedListInit(&linkedList);

    for (i = 0; i < 2; i++) {
        LinkedListFrontPush(&linkedList, i);
        LinkedListBackPush(&linkedList, i);
    }
    LinkedListInsertion(&linkedList, 1, 10);
    LinkedListInsertion(&linkedList, 3, 30);

    LinkedListPrint(&linkedList);
    printf("\n");

    data[0] = LinkedListPop(&linkedList, 4);
    data[1] = LinkedListFrontPop(&linkedList);
    data[2] = LinkedListBackPop(&linkedList);

    LinkedListPrint(&linkedList);
    
    printf("popData = %d, %d, %d\n", data[0], data[1], data[2]);

    LinkedListDelete(&linkedList);

    return 0;
}

이중 연결 리스트 코드

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

#define NO (0)
#define YES (!NO)


typedef struct ST_Node {
    int32_t data;
    struct ST_Node* next;
    struct ST_Node* prev;
}ST_Node;

typedef struct ST_LinkedList {
    int32_t size;
    ST_Node* front;
    ST_Node* back;
}ST_LinkedList;

void LinkedListInit(ST_LinkedList* linkedList)
{
    linkedList->size = 0;
    linkedList->front = NULL;
    linkedList->back = NULL;
}

void LinkedListDelete(ST_LinkedList* linkedList)
{
    int32_t i;
    ST_Node* del;

    for (i = 0; i < linkedList->size; i++) {
        del = linkedList->front;
        linkedList->front = linkedList->front->next;
        free(del);
    }

    LinkedListInit(linkedList);
}

int32_t IsLinkedListEmpty(ST_LinkedList* linkedList)
{
    int32_t result;

    if (linkedList->size == 0) {
        result = YES;
    }
    else {
        result = NO;
    }

    return result;
}

void LinkedListFrontPush(ST_LinkedList* linkedList, int32_t data)
{
    ST_Node* add;

    add = (ST_Node*)malloc(sizeof(ST_Node));

    if (add == NULL) {
        printf("heap is full\n");
    }
    else {
        add->data = data;
        add->prev = NULL;
        
        if (IsLinkedListEmpty(linkedList) == YES) {
            add->next = NULL;
            linkedList->back = add;
        }
        else {
            add->next = linkedList->front;
            linkedList->front->prev = add;
        }
        linkedList->front = add;
        linkedList->size++;
    }
}

int32_t LinkedListFrontPop(ST_LinkedList* linkedList)
{
    int32_t result = 0;
    ST_Node* del;

    if (IsLinkedListEmpty(linkedList) == YES) {
        printf("linkedlist is empty\n");
    }
    else {
        result = linkedList->front->data;
        del = linkedList->front;
        linkedList->front = linkedList->front->next;
        if (linkedList->front != NULL) {
            linkedList->front->prev = NULL;
        }
        free(del);
        linkedList->size--;
    }

    return result;
}

void LinkedListBackPush(ST_LinkedList* linkedList, int32_t data)
{
    ST_Node* add;

    add = (ST_Node*)malloc(sizeof(ST_Node));

    if (add == NULL) {
        printf("heap is full\n");
    }
    else {
        add->data = data;
        add->next = NULL;
        
        if (IsLinkedListEmpty(linkedList) == YES) {
            add->prev = NULL;
            linkedList->front = add;
        }
        else {
            add->prev = linkedList->back;
            linkedList->back->next = add;
        }
        linkedList->back = add;
        linkedList->size++;
    }
}

int32_t LinkedListBackPop(ST_LinkedList* linkedList)
{
    int32_t result = 0;
    ST_Node* del;

    if (IsLinkedListEmpty(linkedList) == YES) {
        printf("linkedlist is empty\n");
    }
    else {
        result = linkedList->back->data;
        
        del = linkedList->back;
        linkedList->back = linkedList->back->prev;
        if (linkedList->back != NULL) {
            linkedList->back->next = NULL;
        }
        free(del);

        linkedList->size--;
    }

    return result;
}

void LinkedListInsertion(ST_LinkedList* linkedList, uint32_t position, int32_t data)
{
    int32_t i;
    ST_Node* add;
    ST_Node* cur;

    if (position > linkedList->size) {
        printf("position error\n");
    }
    else if (position == 0) {
        LinkedListFrontPush(linkedList, data);
    }
    else if (position == linkedList->size) {
        LinkedListBackPush(linkedList, data);
    }
    else {
        add = (ST_Node*)malloc(sizeof(ST_Node));

        if (add == NULL) {
            printf("heap is full\n");
        }
        else {
            if (position <= linkedList->size / 2) {
                cur = linkedList->front;
                for (i = 0; i < position; i++) {
                    cur = cur->next;
                }    
            }
            else {
                cur = linkedList->back;
                int32_t loop = linkedList->size - position;
                for (i = 1; i < loop; i++) {
                    cur = cur->prev;
                }
            }
            add->data = data;
            add->next = cur;
            add->prev = cur->prev;

            cur->prev = add;
            add->prev->next = add;
            linkedList->size++;
        }
    }
}

int32_t LinkedListPop(ST_LinkedList* linkedList, uint32_t position)
{
    int32_t result = 0;
    int32_t i;
    ST_Node* cur;

    if (IsLinkedListEmpty(linkedList) == YES) {
        printf("linkedlist is empty\n");
    }
    else {
        if (position >= linkedList->size) {
            printf("position error\n");
        }
        else if (position == 0) {
            result = LinkedListFrontPop(linkedList);
        }
        else if (position == linkedList->size - 1) {
            result = LinkedListBackPop(linkedList);
        }
        else {
            if (position <= linkedList->size / 2) {
                cur = linkedList->front;
                for (i = 0; i < position; i++) {
                    cur = cur->next;
                }
            }
            else {
                cur = linkedList->back;
                int32_t loop = linkedList->size - position;
                for (i = 1; i < loop; i++) {
                    cur = cur->prev;
                }
            }
            result = cur->data;
            cur->next->prev = cur->prev;
            cur->prev->next = cur->next;
            free(cur);
            linkedList->size--;
        }
    }

    return result;
}

void LinkedListPrint(ST_LinkedList* linkedList)
{
    ST_Node* cur;
    int32_t i;

    cur = linkedList->front;
    for (i = 0; i < linkedList->size; i++) {
        printf("i=%d, data=%d\n", i, cur->data);
        cur = cur->next;
    }
}


int main()
{
    ST_LinkedList linkedList;
    int32_t i;
    int32_t data[3];

    LinkedListInit(&linkedList);

    for (i = 0; i < 2; i++) {
        LinkedListFrontPush(&linkedList, i);
        LinkedListBackPush(&linkedList, i);
    }
    LinkedListInsertion(&linkedList, 1, 10);
    LinkedListInsertion(&linkedList, 3, 30);

    LinkedListPrint(&linkedList);
    printf("\n");

    data[0] = LinkedListPop(&linkedList, 4);
    data[1] = LinkedListFrontPop(&linkedList);
    data[2] = LinkedListBackPop(&linkedList);

    LinkedListPrint(&linkedList);

    printf("popData = %d, %d, %d\n", data[0], data[1], data[2]);

    LinkedListDelete(&linkedList);

    return 0;
}

'프로그래밍' 카테고리의 다른 글

[c언어/c++] 분기문(switch) 제거 (0)	2021.01.21
[c언어] 스택(Stack) (0)	2021.01.14
[c언어] 큐(Queue) (0)	2021.01.01
c언어/c++ do while(0) (0)	2020.12.21
c언어/c++ do while문 (2)	2020.12.18

현재글[c언어] 링크드리스트(Linked List)

프로그래밍 및 독서와 같은 자기발전을 위한 정보를 공유하는 블로그입니다!

median filter, Linked List, 자료구조, Break, 코딩, 패킷 분할, 분기문제거, While, 패킷 합침, 프로그래밍, C++, 링크드리스트 큐, 메디안필터, C언어, 링크드리스트, C/C++, continue, 반복문, 패킷 분리, 프로세스 우선순위,

Today :
Yesterday :

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

업글인간의 정보 리뷰