배열 vs 링크드 리스트

배열 vs 링크드 리스트

배열(Array)

• 정의: 연속된 메모리 공간에 순차적으로 데이터를 저장하는 자료구조
• 메모리 구조: 연속적인 메모리 할당, 인덱스를 통한 직접 접근 가능
• 크기: 대부분의 언어에서 고정된 크기로 선언 (일부 언어는 동적 배열 지원)

배열의 특징

• 인덱싱: O(1) 시간에 임의의 위치 접근 가능
• 메모리 효율: 순차적 메모리 할당으로 캐시 지역성 우수
• 추가/삭제: 요소 추가/삭제 시 다른 요소들의 이동 필요 (O(n) 시간 복잡도)
• 크기 제한: 선언 시 크기 고정 (동적 배열은 재할당 통해 확장)

배열의 시간 복잡도

• 접근: O(1) - 인덱스를 통한 직접 접근
• 검색: O(n) - 정렬되지 않은 배열에서 순차 검색
• 삽입: O(n) - 최악의 경우 (맨 앞에 삽입)
• 삭제: O(n) - 최악의 경우 (맨 앞에서 삭제)

배열 구현 예시 (Java)

// 정적 배열 선언
int[] staticArray = new int[5];

// 배열 요소 접근
staticArray[0] = 10;
int value = staticArray[0];

// 동적 배열 (ArrayList)
import java.util.ArrayList;

ArrayList<Integer> dynamicArray = new ArrayList<>();
dynamicArray.add(10); // 요소 추가
int element = dynamicArray.get(0); // 요소 접근
dynamicArray.remove(0); // 요소 삭제

링크드 리스트(Linked List)

• 정의: 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성된 자료구조
• 메모리 구조: 비연속적 메모리 할당, 포인터를 통한 노드 연결
• 크기: 동적으로 크기가 변경 가능

링크드 리스트의 특징

• 메모리 할당: 필요할 때마다 노드 동적 할당
• 삽입/삭제 효율: 포인터만 변경하면 되므로 O(1) 시간에 가능 (위치를 알고 있을 경우)
• 순차 접근: 특정 위치 접근을 위해 처음부터 순차적으로 탐색 필요
• 추가 메모리: 데이터 외에 포인터 저장을 위한 추가 메모리 필요

링크드 리스트의 시간 복잡도

• 접근: O(n) - 순차적 접근만 가능
• 검색: O(n) - 처음부터 순차 검색
• 삽입: O(1) - 위치를 알고 있을 경우 (헤드/테일)
• 삭제: O(1) - 위치를 알고 있을 경우 (헤드/테일)

링크드 리스트 종류

1. 단일 연결 리스트 (Singly Linked List)
   • 각 노드가 데이터와 다음 노드 포인터 포함
   • 한 방향으로만 순회 가능
2. 이중 연결 리스트 (Doubly Linked List)
   • 각 노드가 데이터, 이전 노드 포인터, 다음 노드 포인터 포함
   • 양방향 순회 가능
   • 추가 메모리 사용
3. 원형 연결 리스트 (Circular Linked List)
   • 마지막 노드가 첫 번째 노드를 가리킴
   • 끝없는 순회 가능

링크드 리스트 구현 예시 (Java)

// 단일 연결 리스트 노드 클래스
class Node {
    int data;
    Node next;
    
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// 단일 연결 리스트 클래스
class LinkedList {
    Node head;
    
    // 노드 추가
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        
        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 class LinkedListExample {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.printList(); // 출력: 1 -> 2 -> 3 -> null
    }
}

배열과 링크드 리스트 비교

특성	배열	링크드 리스트
메모리 할당	연속적	비연속적
요소 접근	O(1) - 직접 접근	O(n) - 순차 접근
메모리 효율	데이터만 저장	데이터 + 포인터 저장
삽입/삭제 효율	O(n)	O(1) - 위치 알고 있을 경우
크기 변경	고정 크기 (동적 배열은 재할당)	동적 크기 변경 용이
캐시 지역성	우수	낮음
구현 복잡도	간단	상대적으로 복잡

사용 시나리오

배열이 적합한 경우

• 요소에 대한 빠른 접근이 필요할 때
• 데이터 크기가 미리 알려져 있을 때
• 메모리 효율성이 중요할 때
• 캐시 성능이 중요한 경우
• 간단한 자료구조가 필요할 때

링크드 리스트가 적합한 경우

• 데이터의 삽입/삭제가 빈번할 때
• 데이터 크기를 미리 알 수 없거나 자주 변경될 때
• 메모리가 제한적이지 않을 때
• 중간 위치에서의 삽입/삭제가 많은 경우
• 동적 메모리 할당이 필요한 경우

실제 응용 사례

• 배열:
  • 이미지 처리 (픽셀 데이터)
  • 행렬 연산
  • 해시 테이블 구현
  • 정렬 알고리즘

• 링크드 리스트:
  • 스택 및 큐 구현
  • 메모리 관리 (가용 메모리 블록 관리)
  • 다항식 표현
  • 그래프의 인접 리스트 표현
  • LRU 캐시 구현

관련 항목

• 자료구조
• 스택 vs 큐
• 트리 구조