Array (배열)
특징
메모리 상에 데이터가 연속적으로 저장된다
같은 성질을 갖는 항목들의 집합
크기가 고정적이다.
랜덤 접근이 가능하다.
장점
인덱스가 있어 탐색의 경우 시간 복잡도는 O(1)이다.
단점
맨 앞이나 중간에 삽입이나 삭제시 그 뒤(오른쪽)에 있는 값들을 한쪽으로 한칸씩 옮겨야 하기 때문에 시간복잡도는 O(n)이다. (삭제나 삽입시 재배열이 필요하다)
배열 생성시 크기를 정해야하며, 추후에 변경하기 힘들다
배열을 사용할 때
읽기가 빈번하게 일어나는 경우
List (리스트)
특징
메모리 상에 데이터가 비연속적으로 저장된다.
크기가 가변적이다.
장점
메모리 공간을 미리 확보할 필요가 없다.
단점
읽기 시 시간 복잡도는 O(n)이다
리스트를 사용할 때
삽입과 삭제가 빈번하게 일어날 경우
추가적으로 파이썬의 경우 리스트를 동적 배열로 사용할 수 있다.
- 연속한 메모리 위치에 객체(objects)의 주소를 저장한다. (파이썬의 모든 것은 객체다.)
- 같은 종류의 자료뿐만 아니라, 다양한 자료(객체)를 저장할 수 있다. ex) ['a', 1, ('a', 1)]
- 배열처럼 인덱스로 각 객체(자료)에 쉽게 접근할 수 있고, 슬라이싱 가능하다.
배열과 관련하여 튜플과 리스트를 비교해볼 수 있다.
- 리스트(list)
- 동적 배열
- 배열의 크기와 원소를 변경할 수 있다.
- 표기: [ ]
- 튜플(tuple)
- 정적 배열
- 배열의 크기와 원소를 변경할 수 없다.
- 표기: ( )
'Computer Science > 자료구조' 카테고리의 다른 글
[자료구조] 우선순위 큐(Priority Queue) (0) | 2023.05.10 |
---|---|
[자료 구조] 자료 구조 시간 복잡도 (0) | 2023.03.19 |