썸네일은 본 내용과 전혀 관계 없는 작곡가이자 피아니스트인 프란츠 리스트이다.

List 리스트

선형 자료구조로서 런타임 중 크기를 확장할 수 있는 자료구조
배열 요소의 개수를 특정할 수 없는 경우 사용이 용이하다.

List 구현

배열은 크기를 변경할 수 없는 자료구조인데, 리스트는 배열 기반의 자료구조이다.
리스트는 동작 중 크기를 확장하기 위해(Grow) 포함한 데이터보다 더욱 큰 배열을 사용한다.
데이터는 배열의 끝에서부터 들어가게 된다.

List 삽입

중간에 데이터를 추가할 때에는 이후 데이터들을 뒤로 밀어내고 삽입을 진행한다.

List 삭제

중간에 데이터를 삭제한 뒤 빈자리를 없애기 위해 이후의 데이터들을 앞으로 당긴다.

List Grow

리스트가 꽉 찬 상태에서 추가 데이터가 들어오려고 하는 경우
더 큰 용량의 배열을 생성한 뒤에 데이터를 복사하여 새로운 배열을 사용한다.

시간 복잡도

접근 : O(1)
탐색 : O(n)
삽입 : O(n)
삭제 : O(n)