[자료구조] 배열 & 연결리스트(Array & LinkedList)

배열과 연결 리스트

배열과 연결 리스트는 데이터를 저장하고 관리하는 데 사용되는 기본적인 자료구조이다.

---

배열(Array)

 

배열(Array)이란?

배열이란 동일한 데이터 타입을 가진 원소들이 연속적으로 배치된 자료구조이다.

 

특징

• 고정된 크기를 가지며, 크기 변경이 어렵다.
• 인덱스를 사용하여 원소에 빠르게 접근할 수 있다. 이때, 원소에 대한 접근 속도는 O(1)이다.
• 크기를 미리 정해야 하므로 필요한 크기보다 크게 잡아야 할 수 있다.(메모리 낭비 가능성)

장단점

• 장점
  - 인덱스를 이용한 빠른 접근 가능 (O(1))
  - 연속된 메모리 할당으로 캐시 적중률이 높음
• 단점
  - 크기가 고정되어 있어 유연성이 부족함
  - 삽입/삭제 연산이 비효율적임 (O(n))

 

시간 복잡도

• 삽입: 특정 위치에 값을 삽입하는 경우, 기존 값들을 이동해야 하므로 평균 O(n)
• 삭제: 특정 위치의 값을 삭제하는 경우, 뒤의 값을 이동해야 하므로 평균 O(n)
• 검색
  - 인덱스로 접근 시 O(1)
  - 값으로 접근 시 O(n)

---

연결 리스트(Linked List)

연결 리스트란?

연결 리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이다.

각 노드는 데이터와 다른 노드를 가리키는 포인터로 이루어져 있다.

첫 번째 노드를 head, 마지막 노드를 tail이라고 한다.

 

종류

• 단일 연결 리스트(Singly Linked List)
• 이중 연결 리스트(Doubly Linked List)
• 원형 연결 리스트(Circular Linked List)

 

장단점

• 장점
  - 동적으로 메모리를 할당하므로 크기 제한이 없음
  - 삽입/삭제가 배열보다 효율적임(O(1) - 단, 탐색 제외)
• 단점
  - 인덱스를 통한 접근이 불가능하므로 탐색 시간이 오래 걸림(O(n))
  - 포인터를 저장하기 위한 추가 메모리 필요

시간 복잡도

• 삽입
  - 리스트의 앞/뒤/중간에 새로운 노드를 추가하는 연산
  - 삽입 위치를 탐색하는데 O(n), 삽입 자체는 O(1)
• 삭제
  - 특정 노드를 제거하기 위해 이전 노드 탐색 필요(단일 연결 리스트의 경우)
  - 평균적으로 O(n)
• 검색
  - 값을 찾기 위해 노드를 순차적으로 탐색하므로 O(n)

---

배열과 연결 리스트의 비교

구분	배열	연결 리스트
메모리 구조	연속된 메모리	비연속적인 메모리
접근 속도	O(1) (인덱스로 접근)	O(n) (탐색 필요)
삽입/삭제 속도	O(n)	O(1) (탐색 제외)
메모리 효율성	고정 크기, 낭비 가능	동적 크기, 추가 메모리 필요
캐시 적중률	높음	낮음