📖Array

동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 고정된 크기의 선형 자료구조

• element : 배열을 구성하는 각각의 값
• index : 배열에서의 위치를 가리키는 숫자

📎정적 배열

연관된 데이터를 메모리 상 연속적이고 순차적으로 미리 할당된 크기만큼 저장하는 배열

• 밑에서 서술할 특징, 장•단점은 다 정적 배열 기준

📎동적 배열

미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면 늘려, 데이터를 추가/저장할 수 있는 배열

• 기존 Array의 한계를 극복하고자 고안
  • 파이썬 : list
  • 자바 : ArrayList
  • C++ : std::vector

Growth Factor

메모리를 재할당하는 비율

• 파이썬 : 초반 2배, 전체적으로는 1.125배
• C++의 std::vector, 루비 : 더블링(2배)
• 자바의 ArrayList : 1.5배

📖특징

• 연속적인 메모리 공간에 순차적으로 데이터 저장
• 선언할 때 크기를 정하면 크기 고정
• 배열의 주소를 살펴보면, 한 칸마다 배열의 자료형의 크기를 가짐

📖장점

• 빠른 접근 : 인덱스를 이용한 접근이 가능하기 때문에 검색이 빠름
• 메모리 공간의 효율성 : 연속된 메모리 공간에 요소를 저장하므로, 메모리 공간을 효율적으로 사용 가능

📖단점

• 삽입•삭제의 어려움 : 메모리가 순차적으로 이어져 있기 때문에 삽입•삭제 시 해당 위치 이후의 요소들을 모두 이동 필수
• 크기 제한 : 생성할 때 크기를 정하고 크기 변경 불가능 → ArrayList와 같은 동적 배열 사용

📖사용

• 순차적인 데이터 저장할 때
• 다차원 데이터를 다룰 때
• 데이터의 크기가 변경되지 않을 때
• 데이터가 단순하고 빠른 검색이 필요할 때

📖시간복잡도

연산	시간복잡도
접근	O(1)
삽입	O(n)
삭제	O(n)
탐색	O(n)

📖Array & Linked List