[자료구조] Linked-List(C 구현)

Linked List

• 연결 리스트는 각 노드가 선형적으로 연결되어 있는 자료구조를 말한다.

특징

1. 맨 처음 삽입한 노드의 주소를 가진다.
2. 각각의 노드는 데이터와 다음 노드의 주소를 가진다.
3. 데이터가 추가될 때마다 새로운 노드를 할당한다. -> 노드끼리의 메모리는 불연속적이다.
4. 요소의 삭제와 추가는 O(1)이며, 특정 원소 접근은 n이다.

장점

1. 동적인 크기의 데이터를 다루기 좋다. 데이터를 삽입할 때마다 메모리를 추가로 할당하기 때문이다.

   • 일반 배열은 크기를 늘릴 수 없음
   • 동적배열(vector) 은 크기가 늘어날 때 재할당과 복사로 오버헤드 발생 O(n)

2. 각 요소 사이에 데이터를 추가하더라도 O(1)로 굉장히 빠르다.

   • 일반 배열과 동적배열은 해당 구역의 뒷부분을 한 칸씩 밀어서 공간을 만들어 내며 오버헤드가 발생 O(n)

단점

1. 각 노드가 다음 노드의 주소도 가지고 있기 때문에 메모리가 비교적 많이 필요함.
2. 특정 데이터에 접근할 때, 배열처럼 index로 접근하지 못해 순회를 해야한다. O(N)

구현

• 구현은 cpp로 이중연결리스트를 구현했다.

#include <stdlib.h>


typedef struct node
{
    struct node* prev;
    struct node* next;
    int data;
} node;

typedef struct list
{
    node* head;
    node* tail;
    int size;
} list;


void initialize(list* list)
{
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

void push_back(list* list, int data) {
    node* new_node = (node*)malloc(sizeof(node));
    new_node->data = data;
    new_node->next = NULL;

    if(list->size == 0) {
        list->head = new_node;
        new_node->prev = NULL;
    }
    else 
    {
        list->tail->next = new_node;
        new_node->prev = list->tail;
    }
    list->tail = new_node;
    list->size += 1;
}

void pop_back(list* list) 
{
    if(list->size == 0)
        return;

    node* temp = list->tail;

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

    free(temp);
    list->size -= 1;
}


node* find(list* list, int target) 
{
    node* cur = list->head;

    while(cur != NULL) 
    {
        if(cur->data == target) 
            return cur;
        cur = cur->next;
    }
    return NULL;
}

void clear(list* list)
{
    node* cur = list->head;
    node* next;

    while (cur != NULL)
    {
        next = cur->next;
        free(cur);
        cur = next;
    }
    initialize(list);
}