[자료구조] Array vs Linked List

Array [배열]

Array는 중복을 허용하는 같은 타입의 변수로 이루어져 있으며 크기가 정해져 있고 인접한 메모리 위치에 있는 데이터를 모아놓은 순서가 있는 집합

배열 접근 탐색 삽입 삭제

평균

O(1)

O(n)

O(n)

O(n)

• Index 기준으로 탐색하는 접근의 시간 복잡도가 O(1)이 되어 랜덤 접근이 가능
• 배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용

---

Linked List [연결 리스트]

Linked List는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조

연결리스트 접근 탐색 삽입 삭제

평균

O(n)

O(n)

O(1)

O(1)

• 싱글 연결 리스트: next 포인터만 보유
• 이중 연결 리스트: next 포인터와 prev 포인터를 보유
• 원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 지정

---

Array vs Linked List

랜덤 접근과 순차적 접근

배열은 몇 번째인지만 알면 바로 접근이 가능한 랜덤 접근 방법을 채택한다. 그에 비해 연결리스트는 요소를 알기 위해서는 순차적으로 확인해봐야 하는 순차적 접근을 사용해야 한다.

데이터 추가 및 삭제

데이터를 추가하고 삭제하는 부분은 연결리스트에서 강점을 가진다. 배열의 경우, 값을 추가하려면 그 값을 넣기 전에 한칸씩 뒤로 미는 과정이 필요하다. 그에 비해 연결리스트는 노드를 끊고 거기에 이어주면 그만이다.

용어정리

• 노드: 리스트에서 데이터를 저장하는 단위
• 포인터: 메모리의 주소값을 저장하는 변수
• 헤드 노드: 맨 앞에 있는 노드