자료구조 : 개념 :: 배열 리스트( Array List )

List based on array

List의 특징 :

- 순서가 있고 중복을 허용하는 items의 collection
- items는 나열된 순서에 따라 위치(index)를 갖는다.
- index를 이용해 전후단 뿐 아니라 임의의 위치에서 삽입/삭제 가 가능하다.
- 가장 자유로운 선형 자료구조
- 삽입 : insert / 삭제 : delete

ArrayList 주요 연산

- insert( pos, item )  :  pos에 item 삽입 
- delete( pos )  :  pos 위치의 item 삭제
- isEmpty( )  :  공백 판별
- getEntry( pos )  :  pos위치의 item 반환 

ArrayList와 LinkedList의 비교

  ArrayList
    - 탐색 O(1)
    - 삽입/삭제 O(n)
    - 구현이 쉬웁
    - 메모리 제한 / 애초에 크기를 정하여 넉넉히 할당 => 크기증가가 필요할 때, 더 큰 배열에 복사-이동 및 기존배열 삭제

  Linked-List 
    - 탐색 O(n)
    - 삽입/삭제 O(1)
    - 구현이 어려움
    - 메모리 제한 X / 필요시마다 메모리 증가

ArrayList의 응용 종류

- 라인편집기
- 다항식 클래스 : Polynomial

파이썬 내장 리스트

- 파이썬 리스트 : 동적 Array로 구현됨

- 동적 배열 구조의 메모리 증가 과정 :
    1. 용량을 확장한 새로운 배열 할당
    2. 기존 배열을 새로만든 배열에 복사
    3. 메모리가 부족해 삽입하지 못했던 item 새 배열에 삽입
    4. 기존 배열 해제 및 새 배열 사용

- 파이썬 내장 Array 의 연산 시간복잡도
    
    - append( item ) : 대부분 O(1)  
        -왜 대부분? : append는 최후단에 item을 삽입하는 연산이다, 이를 응용하여 최전단에 item 삽입 시, 모든 items를 한칸씩 뒤로 옮겨야 하기 때문에 n개의 item에 대해 이동을 수행하게 됨(O(n))
    
    - insert( pos, item ) : O(n)
    - pop( pos ) : O(n)