배열(순차리스트)

1. 개념

• index를 가진 원소들이 순차적으로 나열되어 있는 자료구조

 

2. 종류

• 정적배열과 동적배열이 있음
• 정적배열 : 처음 C언어 문법 배울때 쓰는 배열, 할당할때 정한 사이즈를 넘어가면 쓰지 못함
• 동적배열 : C++기준 vector, 배열의 크기를 사용하면서 바꿀 수 있게 구현한 것
  즉 동적배열엔 resize기능과 append기능이 필요

 

3. 구현

• C++기반의 Array STL : https://smallpants.tistory.com/79
• C++기반의 Vector STL : https://smallpants.tistory.com/77

 

4. 시간복잡도

• 원소 접근 : O(1)
• 원소 탐색 : O(1)
• 원소 대입 : O(1)
• 원소 삭제 : O(n)

접근, 탐색, 대입은 인덱스를 이용해서 한번에 가능하지만

삭제 시에는 다른 값들을 한칸씩 옮겨줘야 하므로 비효율이 발생함