Linked List vs. Array

Array vs. Linked List

데이터 구조는 프로그래밍에서 데이터를 효율적으로 저장하고 관리하기 위한 방법을 제공합니다. 이 중에서도 배열과 연결 리스트는 가장 기본적이면서도 중요한 데이터 구조이다.
두 구조는 서로 다른 특성과 장단점을 가지고 있어 적절한 상황에 맞게 선택해 사용해야 한다.

배열은 인덱스를 통한 빠른 접근과 간단한 구현이 장점이지만, 크기가 고정되어 있고 중간 삽입/삭제가 비효율적이다.
반면 연결 리스트는 동적 크기 조정과 효율적인 삽입/삭제가 장점이지만, 임의 접근이 불가능하고 추가 메모리를 사용한다.

적절한 상황에 맞는 자료구조 선택은 효율적인 프로그램 개발의 핵심이다. 따라서 문제의 특성과 요구사항을 잘 분석하여 최적의 자료구조를 선택해야 한다. 때로는 두 자료구조의 장점을 결합한 하이브리드 접근 방식이나 다른 고급 자료구조를 활용하는 것이 더 나은 해결책이 될 수도 있다.

연결 리스트(Linked List)

연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성된 선형 데이터 구조이다.
노드들은 메모리 상에 연속적으로 위치하지 않고, 포인터를 통해 연결된다.

1. 연결 리스트의 특징

   • 메모리 구조: 노드들이 메모리상에 불연속적으로 위치한다.
   • 접근 방식: 헤드(시작 노드)부터 순차적으로 탐색해야 한다.
   • 크기: 동적으로 크기가 변할 수 있다.
   • 구성 요소: 각 노드는 데이터와 다음 노드를 가리키는 포인터(및 이전 노드를 가리키는 포인터)로 구성된다.

2. 연결 리스트의 종류

   • 단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드만을 가리킨다.
   • 이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드 모두를 가리킨다.
   • 원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리켜 원형을 형성한다.

3. 연결 리스트의 구현 예제

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

   # Python에서의 단일 연결 리스트 구현 class Node: def __init__(self, data): self.data = data self.next = None class SinglyLinkedList: def __init__(self): self.head = None # 리스트 끝에 노드 추가 def append(self, data): new_node = Node(data) # 리스트가 비어있는 경우 if self.head is None: self.head = new_node return # 마지막 노드 찾기 last = self.head while last.next: last = last.next # 마지막 노드의 다음을 새 노드로 설정 last.next = new_node # 리스트 출력 def print_list(self): current = self.head while current: print(current.data, end=" -> ") current = current.next print("None") # 연결 리스트 사용 예 linked_list = SinglyLinkedList() linked_list.append(1) linked_list.append(2) linked_list.append(3) linked_list.print_list() # 출력: 1 -> 2 -> 3 -> None

장점:

• 동적 크기 조정 가능
• 중간 삽입/삭제가 효율적(노드 포인터만 변경)
• 메모리 사용의 유연성
• 데이터의 재배치 없이 요소 추가/삭제 가능

단점:

• 임의 접근 불가능(순차적 접근 필요)
• 추가 메모리 사용(포인터 저장 공간 필요)
• 캐시 지역성 활용이 어려움
• 역방향 탐색이 어려움(단일 연결 리스트의 경우)

배열(Array)

배열은 같은 타입의 요소들을 연속된 메모리 공간에 저장하는 자료구조이다.
각 요소는 인덱스를 통해 직접 접근할 수 있다.

1. 배열의 특징

   • 메모리 구조: 요소들이 메모리상에 연속적으로 저장된다.
   • 인덱스 접근: 인덱스를 통해 O(1) 시간에 요소에 직접 접근 가능하다.
   • 크기: 많은 언어에서 배열은 생성 시 크기가 고정되며, 변경이 불가능하다(정적 배열). 그러나 동적 배열은 크기가 가변적이다.
   • 데이터 타입: 일반적으로 모든 요소는 동일한 데이터 타입을 가진다.

2. 배열의 종류

   • 1차원 배열: 하나의 인덱스로 요소에 접근한다.
   • 다차원 배열: 여러 인덱스를 사용하여 요소에 접근한다(예: 행렬).
   • 정적 배열: 크기가 고정된 배열이다.
   • 동적 배열: 크기가 가변적인 배열로, 내부적으로 크기 조정을 자동으로 처리한다.

3. 배열의 구현 예제

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   # Python에서의 배열 (리스트) 사용 예 # 1차원 배열 생성 arr = [1, 2, 3, 4, 5] # 요소 접근 print(arr[2]) # 출력: 3 # 요소 변경 arr[2] = 10 print(arr) # 출력: [1, 2, 10, 4, 5] # 배열 끝에 요소 추가 arr.append(6) print(arr) # 출력: [1, 2, 10, 4, 5, 6] # 특정 위치에 요소 삽입 arr.insert(1, 7) print(arr) # 출력: [1, 7, 2, 10, 4, 5, 6] # 요소 삭제 arr.remove(10) print(arr) # 출력: [1, 7, 2, 4, 5, 6]

장점:

• 인덱스를 통한 빠른 접근(O(1))
• 간단한 구현과 사용법
• 메모리 효율성(연속된 메모리 블록 사용)
• 캐시 지역성(Cache Locality) 활용으로 성능 향상

단점:

• 크기가 고정되어 있는 경우가 많음(정적 배열)
• 중간 삽입/삭제가 비효율적(O(n))
• 크기 조정 시 모든 요소 복사 필요(동적 배열)
• 메모리 사용의 비효율성(사용하지 않는 공간 발생 가능)

배열과 연결 리스트 비교 분석

* 동적 배열의 경우 재할당이 필요할 수 있음
** 이중 연결 리스트에서 테일 포인터를 사용하는 경우
*** 위치를 찾는 데 O(n)이 소요되지만, 실제 삽입/삭제 연산은 O(1)

메모리 사용량 비교

배열과 연결 리스트는 데이터 저장 방식에 따라 메모리 사용 측면에서 상당한 차이를 보인다.
각각의 자료구조는 할당 방식, 오버헤드, 그리고 동적 확장성 등에서 서로 다른 특성을 가지며, 이를 이해하는 것은 시스템 성능과 메모리 효율을 극대화하는 데 도움이 된다.

1. 배열의 메모리 사용량

   • 배열은 연속된 메모리 블록에 요소들을 저장하므로, 각 요소는 자료형에 필요한 만큼의 메모리(예: 정수형의 경우 4바이트)를 정확하게 차지한다.
   • 미리 배열의 크기를 할당하면 추가적인 포인터나 메타데이터 없이 순수 데이터만 저장되므로, 동일한 수의 요소를 저장할 때 최소한의 메모리 오버헤드로 운영된다.
   • 다만, 동적 크기 조정을 지원하는 배열 기반 자료구조(예: Java의 ArrayList)는 요소 추가를 위해 미리 여유 공간을 확보하거나 크기를 재할당할 때 일부 메모리가 낭비될 수 있다.

2. 연결 리스트의 메모리 사용량

   • 연결 리스트는 각 요소를 노드 단위로 저장하며, 각 노드는 데이터 외에 하나 이상의 포인터(예: 단일 연결 리스트는 다음 노드에 대한 참조, 이중 연결 리스트는 이전과 다음 모두에 대한 참조)를 포함한다.
   • 특히 JVM과 같이 객체 오버헤드가 존재하는 언어에서는 각 노드에 객체 헤더와 메모리 정렬을 위한 추가 바이트가 필요하므로, 단일 연결 리스트의 경우 데이터 하나당 24바이트까지 사용될 수 있다.
   • 결과적으로 동일한 양의 데이터를 저장할 때, 연결 리스트는 배열보다 최소 2배 이상의 메모리를 사용하며, 자바 같은 환경에서는 최대 6배까지 메모리 사용량이 늘어날 수 있다.

요약하면, 배열은 일관되고 연속적인 메모리 할당 덕분에 요소 저장에 최소의 오버헤드를 가지며, 메모리 활용 측면에서 효율적이이다. 반면, 연결 리스트는 데이터의 동적 관리와 삽입·삭제가 용이하지만, 각 노드에 추가적인 포인터와 헤더 정보가 포함되므로 같은 데이터를 저장할 때 배열보다 훨씬 많은 메모리를 필요로 한다.

언제 어떤 자료구조를 사용할까?

1. 배열을 선택해야 할 때

   • 요소에 빠르게 접근해야 할 때(인덱스 기반 접근)
   • 데이터 크기가 미리 알려져 있고 변경이 적을 때
   • 메모리 사용을 최소화해야 할 때
   • 캐시 효율성이 중요할 때
   • 단순한 데이터 구조가 필요할 때

2. 연결 리스트를 선택해야 할 때

   • 데이터의 삽입과 삭제가 빈번할 때
   • 데이터의 크기가 동적으로 변할 때
   • 메모리 할당에 제약이 있어 유연성이 필요할 때
   • 요소 접근보다 삽입/삭제 성능이 중요할 때
   • 다른 자료구조(스택, 큐 등)의 기반 구조로 사용할 때

실제 응용 사례

1. 배열 응용 사례

   • 행렬 연산 및 이미지 처리
   • 해시 테이블의 기반 구조
   • 정렬 알고리즘(퀵 정렬, 병합 정렬 등)
   • 동적 프로그래밍 테이블
   • 캐시 구현

2. 연결 리스트 응용 사례

   • 스택 및 큐 구현
   • 메모리 관리(메모리 할당 및 가비지 컬렉션)
   • 해시 테이블의 체이닝 방식
   • 그래프의 인접 리스트 표현
   • LRU(Least Recently Used) 캐시 구현

참고 및 출처