가변 배열(Dynamic Array), 리스트(List)

가변 배열(Dynamic Array), 혹은 리스트(List)는, 가장 기초적인 자료구조라 할 수 있는 배열을 개조해서 크기가 자동으로 조절되게 만든 자료구조입니다. 배열은 처음에 크기를 고정해야 합니다. 여러가지 이유가 있지만, 가장 큰 이유는 속도 때문입니다.

하지만 현실의 프로그래밍에서는 크기를 미리 정해두면 불편함이 많아서, 자동으로 크기가 조절되는 배열이 매우 유용합니다.

---

가변배열의 정의, 추상자료형

가변 배열 (리스트)은 말 그대로 크기가 변할 수 있는 배열입니다. 하지만 크기가 변한다는 것 이외에는 일반적인 배열과 똑같습니다.

우선, 가변 배열에 필요한 매소드가 어떤 것이 있을지 생각해 보면 좋을거 같습니다. 우선 가변 배열은 외부적으로는 크기가 정해져 있지 않고 유연하게 늘어나는 것 처럼 보이지만, 내부적으로는 크기가 정해진 배열이 있고 그 배열이 다 차면 그 보다 크기가 더 큰 배열을 만들어서 모든 데이터를 복사하는 방식입니다. 따라서, 처음 가변 배열을 만들때 크기를 유저가 정해주거나, 정해주지 않으면 내부적으로 일정한 크기의 배열을 만들어야 합니다.

그 외에도 배열에서 일반적으로 쓸 수 있는 메소드는 모두 있어야 합니다. (length, get 등)

int[] arr = [1, 2, 3]; 
arr.length; // 3

int[] arr = [1, 2, 3]; arr[1]; // 1

추가로 배열에서는 불가능하지만 특정 위치에 있는 원소를 삭제하거나, 추가하는 매소드도 있을 수 있습니다.

정리하자면,

• 생성자
  • int 타입의 크기를 받아서 그 크기의 배열을 내부적으로 생성한다
  • 받는 데이터가 없을 경우 임의로 크기가 10인 배열을 내부적으로 생성한다
• 매소드
  • 배열의 현재 크기를 알려주는 매소드
  • 주어진 위치에 있는 원소를 알려주는 매소드
  • 주어진 위치에 원소를 추가하는 매소드
  • 주어진 위치에 원소를 삭제하는 매소드

 

위의 목록은 간단한 추상 자료형이라 할 수 있겠죠? 유저가 어떤 값을 넣으면 어떤 값이 나오는지 명시하지만, 구체적인 구현 방법이나 복잡도는 나타나 있지 않습니다. 따라서 명확하고 효율적으로 구현하는 것은 프로그래머의 몫입니다.

---

가변배열(리스트)의 시간복잡도

연산 종류	시간 복잡도
접근	O(1)
검색	O(n)
삽입	O(n)
추가	O(1)
삭제	O(n)

---