[자료구조]Array, Linked list 차이

배열과 연결리스트 활용

---

• 배열은 고정된 크기의 데이터를 저장하고 자주 데이터에 접근하는 경우에 유용하게 사용
• 연결리스트는 데이터의 추가와 삭제가 빈번하게 일어나거나, 복잡한 형태의 자료구조를 만들 때 사용

Array(배열)

---

• 장점
  • 논리적 저장 순서와 물리적 저장 순서가 일치한다
  • 인덱스(index)를 이용해 원소에 접근할 수 있다(인덱스 값을 알고 있으면 O(1)의 시간복잡도로 접근)
• 단점
  • 삭제, 삽입시 배열의 연속적인 특징이 깨짐(빈 공간이 생긴다)
  • 따라서 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 된다.
  • 데이터의 삽입 또는 삭제 등의 연산이 빈번하게 발생하여 데이터의 수가 다이나믹하게 변하게 되는 자료구조에서는 배열을 활용하는 것이 비효율적

Linked List(연결리스트)

---

• 장점
  • 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 저장한다.
  • 언제든지 메모리 할당/해제할 수 있어 메모리 공간을 유동적으로 사용할 수 있다.
  • 삭제와 삽입을 O(1)에 처리
• 단점
  • 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생
  • 자료에 대한 접근이 잦은 자료구조에서는 연결리스트의 사용을 지양해야 한다.