배열과 연결리스트

👉 배열(Array)

---

• 가장 기본적인 자료구조이다.

• 배열은 인덱스가 존재하며, 인덱스는 0부터 시작한다.

• 자바스크립트 배열의 길이는 언제든 늘어나거나 줄어들 수 있고, 연속적이지 않게 저장할 수 있어 밀집성을 보장하지 않는다.

• 컴퓨터의 메인 메모리에서 배열의 공간은 연속적으로 할당된다.

장점: 캐시(cache) 히트 가능성이 높으며, 조회가 빠르다.

단점: 배열의 크기를 미리 지정해야 하는 것이 일반적이므로, 데이터의 추가 및 삭제에 한계가 있다.

ex)

const arr = ["사과","바나나","파인애플","토마토"]

console.log(arr[0]) // "사과"
console.log(arr["length"]) // 4

👉 연결 리스트

---

• 연결리스트는 동적 자료구조라고 불린다.

• 크기를 정할 필요가 없으며, 배열처럼 연속된 메모리 주소를 할당 받지 않는다.

• 노드(Node)라는게 존재하며, 그 노드 안에 데이터가 있고, 다음 데이터를 가리키는 주소를 연결하면서 이어진 형태라고 볼 수 있다.

• 크기를 정해 놓지 않았기 때문에 크기의 제한이 없다.

장점: 데이터 추가 및 삭제가 자유롭다는 장점이 있다.
단점: 특정 번째의 원소를 검색할 때는 앞에서부터 원소를 찾아야하므로, 데이터 검색 속도가 느리다.

🤔 배열과 연결리스트의 차이점

---

⏰ 시간복잡도

---

배열

• index를 가지고 있기 때문에 탐색은 O(1)의 시간복잡도를 가진다.

• 삽입의 경우는 맨 뒤라고 한다면 O(1)의 시간복잡도를 가지지만 맨뒤가 아닌 나머지는 O(n)이다.

연결리스트

• 삽입은 맨 앞일 경우 O(1)의 시간복잡도를 가지지만 맨 앞이 아닌 나머지는 O(n)이다.

• 배열과 반대로 탐색은 O(n)의 시간복잡도를 가진다.

Reference Image
https://letitkang.tistory.com/111