a. 배열(array)
데이터를 연속적인 메모리 공간에 저장
주소를 통해 매우 빠르게 접근
배열의 시작 주소, 저장된 값의 종류, 인덱스 세가지 정보로 원하는 값의 주소를 계산 가능.
읽기와 쓰기 연산에 O(1)시간이 걸림
고정된 길이를 가지며, 읽기와 쓰기만 지원하는 경우가 많다.
b. 리스트 (파이썬)
c의 배열에는 실제 데이터가 저장된 형식이지만,
python의 리스트에는 데이터가 저장된 주소가 저장된다.
항상 객체의 주소만 저장하기 때문에 셀의 크기를 8바이트(혹은 4바이트)로 고정.
모든 셀의 크기가 같기 때문에 index에 의해 O(1)시간 접근이 가능
읽기/쓰기 외에 여러 연산들 지원
| a.append(val) | 맨 뒤에 val 삽입 |
| a.pop(i) | a[i]값을 지운 후 리턴 pop()은 가장 오른쪽 값 지움 |
| a.insert(i, val) | a[i]=value연산(원래 값들은 한 칸씩 이동) |
| a.remove(val) | val을 찾아 제거 |
| a.index(val) | val이 처음 등장하는 index 리턴 |
| a.count(val) | val이 몇 번 등장하는지 리턴 |
| a[i:j] | a[i]...a[j-1]까지 복사해 새 리스트로 반환 |
리스트는 동적배열(파이썬)
append나 insert로 메모리가 부족해지면, 더 큰 메모리를 할당받아 새로운 리스트에 이전 리스트의 값을 모두 이동한다.
반면 pop이나 remove로 메모리가 너무 널널해지면, 더 작은 메모리에 이전 리스트를 할당한다.
따라서 사용자가 배열의 크기를 신경쓰지 않아도 된다.