해당 자료는 유튜브 신찬수 한국외대 교수님 강의를 시청하며 정리했습니다. 🙏🏻
배열(Array) VS 리스트(List)
- 가장 기본적인 순차적인(순서대로) 자료구조
메모리 구조와 동작 방식에서 차이가 있음
const A = [2, 4, 0, 5];배열
배열은 index를 이용해 특정 위치의 값을 상수시간 내에 읽고 쓸 수 있게 해주는 자료구조이다.
리스트
리스트는 각 원소가 따로따로 저장되며, 포인터(주소)를 통해 연결되는 자료구조이다.
2, 4, 0, 5는 객체가 되고, 따로 저장되며, A[0]은 2가 저장된 곳의 주소를 가리키고, A[1]은 4가 저장된 곳의 주소를 가리킨다.
A[2] = A[2] + 1을 수행하면
A[2]가 변경되는 것이 아니라, 그대로 0이 있고 1을 갖고있는 객체가 연결되며,
A[2]가 가리키던 0 객체를 더이상 가리키지 않고, 1을 갖고 있는 객체를 가리키게 된다.
리스트의 이점
- 용량을 자동 조절한다. 공간이 부족하면 더 큰 용량을 할당하여 값을 저장.
- 동적 배열(Dynamic Array) => 처음부터 고정된 크기를 가지지 않는다!
let arr = [];
for (let i = 0; i < 10000; i++) {
arr.push(i); // 크기를 미리 선언하지 않아도 계속 들어감
}
console.log(arr.length); // 10000
list의 연산별 시간복잡도(Big-O)
Python
A.append(), A.pop: O(1) 평균
A.insert(), A.remove(): O(n) w.c
A.index(), A.count(): O(n) w.c
JS
A.push(), A.pop() => O(1)
A.unshift(), A.shift() => O(n)
A.indexOf(),A.filter()... => O(n)
Frontend Developer 😆