[자료구조] 배열 (Array)

본 포스트는 필자가 학습하고 작성한 글이기 때문에 틀린 내용이 있을 수 있습니다.

 

배열 (Array)

https://chanyeong.com/blog/post/49

배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다.

 

종류

• 1차원 배열 : 가장 기본적인 형태의 배열로, 연속된 메모리 공간에 동일한 타입의 원소들을 저장한다.
• 다차원 배열 : 1차원 배열의 집합을 원소로 갖는 배열.

핵심 요소

• 원소 (Element) : 배열에 저장되는 각 항목을 의미
• 인덱스 (Index) : 각 원소의 위치를 나타내는 번호로, 0부터 시작

장점

• 인덱스를 통해 바로 원소에 접근 가능
• 연속된 메모리 공간에 데이터를 저장하기 때문에 메모리 사용이 효율적

단점

• 배열의 크기는 미리 정해져 있어, 크기를 변경하기가 어렵다.
• 중간에 데이터를 삽입하거나 삭제할 때, 데이터를 이동해야하므로 비효율적

주요 연산

• 접근 : 배열의 특정 인덱스에 있는 원소에 접근
• 삽입 : 배열의 특정 위치에 원소를 삽입
• 삭제 : 배열의 특정 위칭의 원소를 삭제

시간 복잡도

• 접근 : O(1)
• 삽입 : (배열의 끝에서) O(1), (배열의 시작에서) O(n)
• 삭제 : (배열의 끝에서) O(1), (배열의 시작에서) O(n)

공간 복잡도

• O(n)

---

Python의 List

Python의 list는 배열과 유사한 특징을 가지지만, 내부적으로는 동적 배열(dynamic array)로 구현되어 있다.

• Python의 list는 크기가 동적으로 조절된다. 내부적으로 더 큰 메모리 영역을 할당받고 기존의 원소들을 새로운 영역으로 복사하기 때문.
• Python의 list는 여러 가지 타입의 원소를 저장할 수 있다. 이는 Python이 동적 타입 언어 이기 때문. list 안에는 실제 데이터 대신 객체에 대한 참조를 저장하므로 객체의 타입이 다르더라도 저장할 수 있다.