CS 공부 & 면접 대비 0x02 [자료구조] : 배열과 연결 리스트의 장단점 비교

자료구조: 배열과 연결 리스트의 장단점 비교

---

질문

배열(Array)과 연결 리스트(Linked List)의 장단점은 무엇인가요?

---

답변

배열과 연결 리스트는 모두 데이터를 저장하고 관리하기 위한 선형 자료구조입니다. 각각의 특성과 장단점을 이해하면, 문제의 요구사항에 따라 적합한 자료구조를 선택할 수 있습니다.

• 배열(Array)
  • 장점: 메모리에 연속된 공간으로 저장되어 빠른 순회와 RandomAccess가 가능함.
  • 단점: 중간 삽입/삭제 시 복사 비용 발생, 크기 고정.
• 연결 리스트(Linked List)
  • 장점: 삽입과 삭제 모두 O(1) 시간에 가능.
  • 단점: 임의의 위치에 접근할 수 없어 순차 접근 필요.

---

질문과 답변에 대한 설명

1. 배열(Array)의 장단점

배열이란?
배열은 크기가 고정된 연속적인 메모리 공간에 데이터를 저장하는 자료구조입니다. 데이터는 인덱스(Index)를 통해 빠르게 접근할 수 있습니다.

• 장점:
  • RandomAccess 가능: 배열은 메모리 주소를 기반으로 데이터를 직접 접근하므로 특정 인덱스에 O(1) 시간 복잡도로 접근할 수 있습니다.
  • 빠른 순회: 메모리가 연속적이기 때문에 CPU 캐시 친화적(CPU Cache-friendly)입니다.
  • 효율적인 읽기: 한 번에 데이터를 로드하고 연산할 수 있습니다.
• 단점:
  • 삽입과 삭제의 비효율성:
    중간에 데이터를 삽입하거나 삭제하려면 나머지 데이터를 모두 이동시켜야 합니다. 시간 복잡도는 O(n)입니다.
  • 고정된 크기:
    배열은 선언 시 크기를 고정해야 하므로, 데이터 크기를 초과할 경우 새로운 배열을 생성하고 데이터를 복사해야 합니다.

코드 예시 (Python):

# 배열의 중간에 삽입
arr = [1, 2, 4, 5]
arr.insert(2, 3)  # 중간에 '3' 삽입
print(arr)  # Output: [1, 2, 3, 4, 5]

 

2. 연결 리스트(Linked List)의 장단점

연결 리스트란?
연결 리스트는 데이터를 노드(Node)라는 단위로 저장하고, 각 노드가 다음 노드의 주소를 포함하는 포인터로 연결된 자료구조입니다.

• 장점:
  • 삽입과 삭제가 O(1): 특정 위치의 노드에 접근한 경우, 연결만 변경하면 되므로 삽입과 삭제가 매우 빠릅니다.
  • 동적 크기: 크기가 유동적이며, 배열처럼 크기 제한이 없습니다.
• 단점:
  • 임의 접근 불가: 배열처럼 인덱스를 통한 접근이 불가능하며, 원하는 위치에 도달하려면 처음부터 순차적으로 접근해야 합니다(O(n)).
  • 추가 메모리 필요: 각 노드가 데이터를 저장하는 공간 외에 다음 노드를 가리키는 포인터를 추가로 필요로 합니다.

코드 예시 (Python):

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

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

    def insert(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

ll = LinkedList()
ll.insert(1)
ll.insert(2)
print(ll.head.data)  # Output: 2

 

---

배열과 연결 리스트의 비교

배열(Array), 연결 리스트(Linked List)

메모리 구조	연속적	비연속적
크기 변경	고정	동적
접근 속도	O(1) (인덱스로 접근)	O(n) (순차적으로 탐색)
삽입/삭제 속도	O(n) (중간 삽입/삭제 시)	O(1) (앞/뒤 노드 수정 시)
메모리 효율성	추가 메모리 필요 없음	포인터로 인해 메모리 오버헤드 발생

---

결론

배열과 연결 리스트는 각기 다른 장단점을 지닌 자료구조입니다.

• 배열은 빠른 데이터 접근과 순회가 필요한 경우에 적합합니다.
• 연결 리스트는 빈번한 삽입과 삭제가 요구되는 경우에 유리합니다.