---

연결 리스트(Linked List)

연결 리스트는 노드들이 포인터로 서로 연결된 선형 리스트입니다.

Keywords: #연결리스트 #자료구조 #노드 #포인터

---

연결 리스트의 정의

• 노드: 데이터와 다음 노드를 가리키는 포인터로 구성
• 포인터: 다음 노드와의 연결을 지시

---

연결 리스트의 특징

1. 동적 크기: 미리 크기 지정 필요 없음
2. 효율적인 삽입 및 삭제: 중간 위치에서도 효율적
3. 메모리 사용: 데이터와 포인터 저장으로 추가 메모리 필요

---

연결 리스트의 사용 사례

• 다양한 자료형 구현: 스택, 큐, 연관 리스트 등
• 가변 크기의 데이터 구조: 동적 메모리 할당 필요 시
• 효율적인 삽입/삭제: 중간 위치의 빈번한 삽입 및 삭제

---

연결 리스트의 구현

연결 리스트는 노드 기반으로 구현됩니다. 노드는 데이터와 포인터로 구성됩니다.

---

연결 리스트 초기화

파이썬:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = None

C:

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* head = NULL;

---

노드 추가

파이썬:

def append(data):
    global head
    new_node = Node(data)
    if not head:
        head = new_node
        return
    curr = head
    while curr.next:
        curr = curr.next
    curr.next = new_node

C:

void append(int data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    if (!head) {
        head = new_node;
        return;
    }
    struct Node* curr = head;
    while (curr->next) {
        curr = curr->next;
    }
    curr->next = new_node;
}

---

노드 삭제

파이썬:

def delete(data):
    global head
    if not head:
        return
    if head.data == data:
        head = head.next
        return
    curr = head
    while curr.next and curr.next.data != data:
        curr = curr.next
    if curr.next:
        curr.next = curr.next.next

C:

void delete(int data) {
    if (!head) return;
    if (head->data == data) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
        return;
    }
    struct Node* curr = head;
    while (curr->next && curr->next->data != data) {
        curr = curr->next;
    }
    if (curr->next) {
        struct Node* temp = curr->next;
        curr->next = curr->next->next;
        free(temp);
    }
}

---

연결 리스트는 중간 노드의 삽입 및 삭제는 효율적이지만, 임의의 위치 접근은 처음부터 순회해야 하므로 비효율적입니다.

---