연결 리스트 (Linked List)

Concept

연속된 형태의 자료를 저장하는 구조

Time Complexity

Worst Case

Access : head부터 시작해서 마지막에 있는 데이터에 접근하려면 - O(n)

Search : head부터 시작해서 마지막에 있는 데이터를 찾으려면 - O(n)

Insertion : 노드 앞/뒤에 바로 삽입할 수 있음 - O(1)

Deletion : 해당 노드를 바로 삭제할 수 있음 - O(1)

Average Case

Access - Theta(n)

Search - Theta(n)

Insertion - Theta(1)

Deletion - Theta(1)

Space Complexity

n개의 데이터를 저장할 노드가 n개만큼 필요함 - O(n)

Example

#include <stdio.h>
#include <stdlib.h>
​
typedef struct _node {
    struct _node *prev;
    struct _node *next;
    int value;
} Node;
​
Node* create() {
    Node *new = (Node *) malloc(sizeof(Node));
    new->prev = NULL;
    new->next = NULL;
    new->value = 0;
    return new;
}
​
Node* insert(Node *node, int value) {
    Node *new = create();
    new->value = value;
    new->next = node->next;
    new->prev = node;
​
    new->next->prev = new;
    node->next = new;
    return new;
}
​
Node* append(Node *node, int value) {
    Node *new = create();
    new->value = value;
​
    while (node->next != NULL) {
        node = node->next;
    }
​
    node->next = new;
    new->prev = node;
    return new;
}
​
void delete(Node *node) {
    if(node->next == NULL) {
        node->prev->next = NULL;
    }
    else {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    free(node);
}
​
Node* get(Node *head, int position) {
    Node *current = head;
    while(position--) {
        current = current->next;
    }
    return current;
}
​
Node* search(Node *head, int value) {
    Node *current = head;
    while (current != NULL) {
        if (current->value == value) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}
​
void modify(Node *node, int value) {
    node->value = value;
}
​
void print(Node *head) {
    Node *current = head;
    while(current != NULL) {
        printf("%d ", current->value);
        current = current->next;
    }
    printf("\n");
}