본문으로 건너뛰기

Array와 Linked List

1. Array(배열)의 이해​

1.1 배열의 기본 개념​

  • 메모리 상에 연속적으로 데이터를 저장하는 자료구조입니다
  • 각 원소는 인덱스를 통해 직접 접근이 가능합니다
  • 선언 시 크기를 미리 지정해야 합니다
  • 배열의 크기를 변경할 수 없습니다

1.2 배열의 특징​

  • 데이터가 메모리에 연속적으로 저장됩니다
  • 인덱스를 통한 빠른 접근이 가능합니다
    • 시간 복잡도: O(1)
    • 각 원소의 크기가 정해져 있고 배열의 메모리 시작 주소와 인덱스 값만으로 원소에 접근하는 것이 가능합니다
  • 크기가 고정되어 있습니다
    • 동적 배열의 경우 자동으로 크기가 조절됩니다
    • 하지만 내부적으로는 새로운 메모리 할당이 발생합니다

1.3 배열의 주요 연산​

배열 선언 예시

# 정적 배열 선언
arr = [0] * 5

# 동적 배열 사용
dynamic_arr = []
dynamic_arr.append(1)

배열 요소 접근 예시

arr = [1, 2, 3, 4, 5]
print(arr[2])  # 인덱스 2의 값인 3 출력

1.4 동적 배열​

  • 배열은 고정된 크기만큼 연속된 메모리를 할당받습니다.
  • 실제 데이터의 크기를 가늠하기 어려운 경우, 동적 배열을 사용하여 메모리를 효율적으로 사용할 수 있습니다.
  • 대부분의 언어가 동적 배열을 지원하며, 자바에서는 ArrayList, 파이썬에서는 list가 동적 배열로 사용됩니다.
    • 파이썬은 정적 배열이 없으며, 모든 배열은 동적 배열로 구현됩니다.

작동 원리

  • 미리 초기값은 작게 잡아 배열을 생성합니다.
  • 배열이 가득 차면 더 큰 배열을 새로 할당하고 기존 데이터를 복사합니다.
  • 대개는 더블링이라 하여 기존 배열의 크기를 2배로 늘리는 방식을 사용합니다.
    • 언어마다 늘려가는 비율이 다를 수 있습니다.

시간 복잡도

  • 최악의 경우 삽입 시 배열이 가득 차 새로운 배열을 할당하고 기존 데이터를 복사해야 합니다.
  • 이 때 시간 복잡도는 O(n)이 소요됩니다.
  • 분할 상환 분석에 따르면 삽입 시간 복잡도는 O(1)이라고 할 수 있습니다.

2. Linked List(연결 리스트)의 이해​

2.1 연결 리스트의 기본 개념​

  • 각 노드가 데이터와 포인터를 가지고 있는 자료구조입니다
  • 노드들은 메모리 상에서 불연속적으로 존재합니다
  • 포인터로 다음 노드를 가리키며 연결됩니다

2.2 연결 리스트의 특징​

  • 동적으로 크기가 변할 수 있습니다
  • 메모리를 효율적으로 사용할 수 있습니다
  • 중간 삽입/삭제가 용이합니다
  • 특정 인덱스 접근 시 순차적으로 탐색해야 합니다

2.3 연결 리스트 구현​

노드 클래스 구현

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

연결 리스트 기본 구조

class LinkedList:
    def __init__(self):
        self.head = None
        self.length = 0

3. Array와 Linked List 비교​

3.1 성능 비교​

  • 메모리 사용
    • Array: 연속된 메모리 공간 필요
    • Linked List: 분산된 메모리 사용 가능
  • 접근 속도
    • Array: O(1)로 즉시 접근
    • Linked List: O(n)으로 순차 접근
  • 삽입/삭제
    • Array: O(n) 소요
    • Linked List: O(1) 소요 (위치를 알고 있는 경우)

3.2 적합한 사용 상황​

  • Array 사용이 좋은 경우
    • 빈번한 데이터 검색이 필요할 때
    • 데이터 크기가 고정적일 때
    • 캐시 지역성이 중요할 때
  • Linked List 사용이 좋은 경우
    • 삽입/삭제가 빈번할 때
    • 데이터 크기가 가변적일 때
    • 메모리 공간의 효율성이 중요할 때