선형 자료구조 (Linear Data structure) - 배열

선형 자료구조

: 데이터 요소가 순차적(Sequential)으로 배열되는 자료구조, 단일 레벨로 구성되어 한 번에 탐색 가능하고 구현하기 쉬움.

: 배열, 스택, 큐, 연결 리스트 등이 해당됨.

 

배열

: 값 또는 변수 엘리먼트의 집합으로 구성된 구조. 하나 이상의 인덱스 또는 키로 식별됨.

: 고정된 크기 만큼의 연속된 메모리 할당

: 자료구조 중 메모리 공간 기반의 연속 방식의 가장 기본이 되는 자료형

  - 자료구조는 크게 메모리 공간 기반의 연속 방식(contiguous) / 포인터 기반의 연결 방식(link)으로 나뉜다.

  - 포인터 기반의 연결 방식의 기본 -> 연결 리스트

: 어느 위치에나 O(1)에 조회 가능

 

동적 배열

: 실제 데이터의 전체 크기를 가느맣기 힘들 때 크기를 지정하지 않고 자동으로 리사이징

: 파이썬의 리스트가 동적 배열 자료형에 해당

: 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면 늘려주고 모두 복사하는 원리.

   - 더블링: 대개 2배씩 늘려주어 더블링이라고 칭함. 모든 언어가 항상 그런 것은 아님.

: 배열과 동일하게 O(1)에 조회 가능하지만, 더블링이 필요할 때 O(n)의 비용이 필요. (최악의 경우)

: 그러나 분할 상환 분석에 다른 입력 시간은 여전히 O(1).