자료 구조 [배열과 연결 리스트]

자료 구조는 데이터를 효율적으로 저장하고 관리하기 위해 필수적인 개념입니다. 프로그래밍에서 흔히 사용되는 두 가지 중요한 자료 구조로 배열(Array)과 연결 리스트(Linked List)가 있습니다. 이번 글에서는 배열과 연결 리스트를 기초부터 고급 개념까지 소개하고, Java와 C로 구현 예제를 제공하겠습니다.

배열 (Array)

배열은 동일한 타입의 요소들을 연속된 메모리 공간에 저장하는 자료 구조입니다. 인덱스를 사용해 빠르게 접근할 수 있기 때문에 성능이 중요한 상황에서 자주 사용됩니다. 배열의 크기는 고정되어 있으며, 요소의 추가나 삭제 시 비용이 높다는 단점이 있습니다.

배열의 특징

• 인덱스를 사용한 빠른 접근: 배열은 O(1)의 시간 복잡도로 임의의 인덱스에 접근할 수 있습니다.
• 고정된 크기: 배열의 크기는 선언 시점에 정해지며 이후 변경할 수 없습니다.
• 연속된 메모리 할당: 모든 요소가 연속된 메모리 공간에 저장되므로 메모리 관리가 간단합니다.

Java로 배열 예제

public class ArrayExample {
    public static void main(String[] args) {
        // 정수형 배열 선언 및 초기화
        int[] numbers = {1, 2, 3, 4, 5};

        // 배열 요소 출력
        for (int i = 0; i < numbers.length; i++) {
            System.out.println("Element at index " + i + ": " + numbers[i]);
        }
    }
}

C로 배열 예제

#include <stdio.h>

int main() {
    // 정수형 배열 선언 및 초기화
    int numbers[] = {1, 2, 3, 4, 5};
    int length = sizeof(numbers) / sizeof(numbers[0]);

    // 배열 요소 출력
    for (int i = 0; i < length; i++) {
        printf("Element at index %d: %d\n", i, numbers[i]);
    }

    return 0;
}

배열의 장단점

• 장점: 빠른 인덱스 접근(O(1)), 간단한 구현.
• 단점: 크기 고정, 삽입 및 삭제의 비효율성(O(n)).

연결 리스트 (Linked List)

연결 리스트는 요소들이 메모리상에 연속되지 않고, 각 요소가 다음 요소를 가리키는 포인터를 가지고 있는 자료 구조입니다. 배열과 달리 크기가 동적으로 변할 수 있으며, 삽입과 삭제가 용이합니다.

연결 리스트의 특징

• 동적 크기: 필요에 따라 요소를 추가하거나 제거할 수 있어 크기가 동적으로 변합니다.
• 노드(Node): 연결 리스트의 각 요소는 노드라고 불리며, 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
• 접근 시간: 인덱스를 사용한 접근이 불가능하며, 특정 요소에 접근하기 위해선 리스트를 순차적으로 탐색해야 합니다(O(n)).

Java로 연결 리스트 예제

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListExample {
    Node head;

    // 연결 리스트에 노드 추가
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 연결 리스트 요소 출력
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        LinkedListExample list = new LinkedListExample();
        list.add(1);
        list.add(2);
        list.add(3);
        list.printList();
    }
}

C로 연결 리스트 예제

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

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

// 연결 리스트에 노드 추가
void add(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
    } else {
        struct Node* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

// 연결 리스트 요소 출력
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("null\n");
}

int main() {
    struct Node* head = NULL;
    add(&head, 1);
    add(&head, 2);
    add(&head, 3);
    printList(head);

    return 0;
}

연결 리스트의 장단점

• 장점: 동적 크기, 요소 삽입 및 삭제가 용이(O(1) - 삽입 및 삭제 시 노드를 알 경우).
• 단점: 인덱스 접근이 불가능(O(n)), 추가적인 메모리 사용(포인터).

배열과 연결 리스트 비교

특성	배열	연결 리스트
크기	고정됨	동적
접근 시간	O(1) (인덱스 접근)	O(n) (순차 접근)
삽입/삭제	O(n) (중간 삽입/삭제)	O(1) (노드 참조 시)
메모리 사용	연속적 할당	비연속적, 포인터 필요

배열과 연결 리스트는 각각의 장단점이 있기 때문에, 특정 상황에 맞게 적절한 자료 구조를 선택하는 것이 중요합니다. 배열은 크기가 고정되어 있지만 빠른 접근이 필요할 때 유용하며, 연결 리스트는 요소의 빈번한 추가/삭제가 있을 때 적합합니다.

결론

배열과 연결 리스트는 프로그래밍에서 가장 기본적인 자료 구조로, 데이터를 효율적으로 저장하고 관리하기 위해 필수적으로 알아야 합니다. 배열은 고정된 크기와 빠른 접근 속도가 장점이지만, 삽입과 삭제가 어렵다는 단점이 있습니다. 반면 연결 리스트는 크기가 동적이고 삽입과 삭제가 용이하지만, 인덱스를 통한 빠른 접근이 불가능합니다.

배열과 연결 리스트의 차이를 잘 이해하고, 상황에 맞는 자료 구조를 선택하는 것이 프로그램의 성능을 최적화하는 데 큰 도움이 됩니다.