Linked List

Linked List

node라고 불리는 일련의 연결된 요소들로 구성

각 노드는 데이터와 다음 노드에 대한 참조(링크)를 가지고 있다.

*배열과 달리 요소들이 메모리상에서 연속적으로 저장되지 않기 때문에 요소의 삽입과 삭제가 용이하다.

• Singly Linked List

각 노드는 데이터와 다음 노드에 대한 포인터를 가지고 있다.

마지막 노드는 NULL을 가리켜 리스트의 끝을 나타낸다.

• Doubly Linked List

각 노드는 데이터와 함께 이전 노드와 다음 노드에 대한 포인터를 가지고 있다.

리스트의 처음과 끝을 양방향으로 탐색할 수 있다.

• Circular Linked List

마지막 노드가 첫 번째 노드를 가리켜 리스트가 원형으로 연결된다.

시작 노드와 끝 노드가 명확히 구분되지 않는다.

 

주요 연산

• Insert

리스트의 처음, 중간, 끝에 새로운 노드를 추가

• Deletion

특정 위치에 있는 노드를 삭제

• Search

리스트에서 특정 값을 가진 노드를 찾는다

• Display

리스트의 모든 노드를 순서대로 출력

 

Linked List

장점

동적 크기 : 필요에 따라 크기를 조정

삽입과 삭제가 빠름: 배열과 달리 요소를 추가하거나 제거할 때, 다른 요소들을 이동할 필요가 없다.

단점

접근 시간: 임의 접근이 어렵고, 특정 요소에 접근하려면 처음부터 순차적으로 탐색해야함.

추가 메모리 사용: 각 노드가 데이터 외에도 포인터를 저장해야 하므로 추가 메모리가 필요하다.

 

그래서 주로 삽입과 삭제가 빈번한 상황에서 유용하게 사용됨.

 

Singly Linked List 예제

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

// 노드 구조체 정의
struct Node {
    int data;
    struct Node* next;
};

// 링크드 리스트 구조체 정의
struct LinkedList {
    struct Node* head;
};

// 새로운 노드를 생성하는 함수
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 리스트에 데이터를 추가하는 함수 (끝에 추가)
void append(struct LinkedList* list, int data) {
    struct Node* newNode = createNode(data);
    if (list->head == NULL) {
        list->head = newNode;
        return;
    }
    struct Node* last = list->head;
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
}

// 리스트의 모든 노드를 출력하는 함수
void display(struct LinkedList* list) {
    struct Node* current = list->head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 메모리를 해제하는 함수
void freeList(struct LinkedList* list) {
    struct Node* current = list->head;
    struct Node* next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    list->head = NULL;
}

// 메인 함수
int main() {
    struct LinkedList list;
    list.head = NULL;

    append(&list, 1);
    append(&list, 2);
    append(&list, 3);

    printf("Linked List: ");
    display(&list);

    // 메모리 해제
    freeList(&list);

    return 0;
}