[자료구조 - 1 ] 배열(Array)와 연결 리스트(Linked List) 차이점

배열(Array)와 연결 리스트(Linked List)는 각각의 메모리 구조, 시간 복잡도, 그리고 사용 상황에 따라 장단점이 있다.

---

1. 메모리 구조

• Array
  • 데이터를 연속적으로 저장하며, 고정된 크기의 메모리 블록을 사용함.
  • 데이터가 연속적으로 저장되므로 즉시 접근(랜덤 접근)이 가능하여 O(1)의 접근 시간 복잡도를 가짐.
  • 메모리 낭비가 발생할 수 있음: 배열은 정해진 크기보다 작은 데이터를 저장해도 미리 할당된 메모리를 점유하기 때문.
  • 스택(Stack) 영역에서 할당되며 컴파일 시 크기가 정해짐.

배열 구조

 

 

• Linked List
  • 데이터를 불연속적으로 저장하며, 각 노드가 데이터와 다음 노드의 주소를 저장하는 구조로 이루어짐.
  • 데이터 접근 시 순차 접근만 가능하여 특정 인덱스를 조회하려면 O(n)의 시간이 소요됨.
  • 필요한 메모리만 동적으로 할당하므로 메모리 낭비가 적음.
  • 추가적으로 next 주소를 저장해야 하므로 배열보다 더 많은 메모리를 필요로 함.
  • 힙(Heap) 영역에서 할당되며 런타임 시 크기를 동적으로 조정 가능함.

연결 리스트 구조

 

---

2. 시간 복잡도

연산ArrayLinked List

접근	O(1)	O(n)
삽입/삭제	O(n) (중간 위치 기준)	O(1) (노드 앞뒤 기준)

• 배열은 중간 위치에 데이터를 삽입하거나 삭제할 때 나머지 요소를 이동시켜야 하므로 O(n)의 시간이 걸림.
• 연결 리스트는 노드 간 연결만 수정하면 되므로 O(1)의 삽입/삭제가 가능함.

 

---

3. 사용 상황

• Array
  • 데이터의 개수를 미리 알고 있을 때 적합.
  • 데이터 접근이 빈번하고 조회 작업이 중요한 경우 사용.
  • 메모리를 효율적으로 관리해야 하거나, 메모리의 낭비를 감수할 수 있을 때 적합.
• Linked List
  • 데이터의 크기를 예측하기 어려운 경우, 즉 동적으로 크기를 조정해야 하는 경우 적합.
  • 삽입/삭제 작업이 빈번하지만 데이터 조회가 자주 일어나지 않는 경우 사용.
  • 메모리 낭비를 줄이고자 할 때 적합하지만, 각 노드의 next 주소 저장 공간을 고려해야 함.

---

요약

• 배열은 고정된 크기로 빠른 접근 속도가 강점이나, 메모리 낭비와 크기 조정이 어렵다는 단점이 있다.
• 연결 리스트는 크기를 동적으로 조정할 수 있어 메모리 활용이 효율적이며 삽입/삭제에 유리하지만, 접근 속도가 느리다는 단점이 있다.

따라서, 상황에 따라 데이터의 크기 예측 가능성, 접근과 삽입/삭제 빈도, 그리고 메모리 효율성을 고려하여 적절히 선택하는 것이 중요하다.