1. 연결 리스트의 목적과 이론

연결 리스트(Linked List)는 컴퓨터 과학에서 데이터 요소들을 순서대로 저장하는 자료구조입니다. 연결 리스트는 노드(Node)들의 집합으로 구성되며, 각 노드는 데이터 요소와 다음 노드를 가리키는 포인터로 이루어져 있습니다. 연결 리스트는 배열과 달리 물리적인 메모리의 연속성을 요구하지 않아 데이터의 삽입과 삭제가 상대적으로 효율적으로 이루어질 수 있습니다. 다양한 종류의 연결 리스트가 있습니다.

2. 연결 리스트의 장점과 단점

2-1) 장점

• 동적 크기 조절 가능
• 삽입과 삭제가 배열보다 효율적
• 메모리 절약 가능

2-2) 단점

• 특정 요소에 접근할 때 포인터 참조로 인한 속도 저하
• 추가적인 메모리 사용 (포인터 저장)
• 배열과 비교하여 메모리 캐시 활용이 어려움

3. 연결 리스트와 배열의 공통점과 차이점

3-1) 공통점

• 데이터 요소 저장을 위한 자료구조
• 선형 데이터 구조

3-2) 차이점

• 연결 리스트는 요소들이 포인터로 연결되어 메모리 상에 연속적으로 위치하지 않음
• 배열은 요소가 연속적인 메모리에 저장되므로 빠른 인덱스 접근 가능

4. 연결 리스트의 구조

연결 리스트의 구조는 데이터와 다음 요소를 가리키는 포인터로 이루어진 노드로 구성됩니다. 각 노드는 데이터 필드와 다음 노드를 가리키는 포인터 필드로 구성됩니다. 마지막 노드의 포인터는 보통 NULL 값이 됩니다.

4-1) 연결 리스트의 구성요소

1. 노드(Node): 데이터와 포인터로 구성된 단위 요소.
2. 헤드(Head): 연결 리스트의 시작점을 가리키는 포인터.
3. 테일(Tail): 연결 리스트의 끝을 가리키는 포인터 (단일 연결 리스트에서는 마지막 노드, 이중 연결 리스트에서는 마지막 노드와 첫 노드를 연결).
4. 데이터 필드(Data field): 각 노드에 저장된 실제 데이터.
5. 포인터 필드(Pointer field): 다음(또는 이전) 노드를 가리키는 포인터.

4-2) 연결 리스트의 연산 및 시간복잡도

• 삽입: 특정 위치에 노드를 삽입할 때, 해당 위치까지 순차적으로 찾아가야 합니다. 시간 복잡도는 O(n)입니다.
• 삭제: 특정 위치의 노드를 삭제할 때, 해당 위치까지 순차적으로 찾아가야 하며 삭제 작업은 O(n) 시간이 소요됩니다.
• 탐색: 특정 데이터를 찾을 때, 처음부터 순차적으로 탐색해야 하므로 시간 복잡도는 O(n)입니다.

5. 연결리스트 종류

5-1) 단일 연결 리스트 (Singly Linked List):

• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
• 각 노드가 다음 노드만을 가리키기 때문에 순방향으로만 탐색 가능합니다.

5-2) 이중 연결 리스트 (Doubly Linked List):

• 각 노드는 데이터, 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터로 구성됩니다.
• 양방향으로 탐색이 가능하며, 리스트의 양쪽 끝에서의 삽입과 삭제가 효율적입니다.

5-3) 원형 연결 리스트 (Circular Linked List):

• 마지막 노드가 첫 번째 노드를 가리키며, 첫 번째 노드가 마지막 노드를 가리킵니다.
• 원형으로 구성되어 있어 무한히 반복되는 구조입니다.

5-4) 이중 원형 연결 리스트 (Doubly Circular Linked List):

• 이중 연결 리스트와 원형 연결 리스트를 결합한 형태입니다.
• 각 노드는 이전 노드와 다음 노드를 가리키는 포인터로 이루어져 있으며, 마지막 노드가 첫 번째 노드를, 첫 번째 노드가 마지막 노드를 가리킵니다.

6. 연결 리스트 활용 문제 풀어보기

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

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

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 1. 
void append((A), (B)) {
    struct Node* new_node = createNode(data);
    if (*head == NULL) {
        *head = new_node;
        return;
    }
    struct Node* current = *head;
    while (current->next) {
        current = current->next;
    }
    current->next = new_node;
}

int main() {
    struct Node* myList = NULL;

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

    return 0;
}

Q1. A와 B에 들어가는 변수를 써주세요

• (A) :
• (B) :

Q2. 데이터와 포인터로 구성된 단위 요소는 무엇이라고 할까요?