Array(배열) vs Linked List (연결리스트) 비교

배열이란? (링크)

Linked List란? (링크)

---

자료구조를 공부할 때 꼭 내가 쓰는 언어를 생각하다 보니까

배열을 자꾸 자바스크립트 배열로 생각하려고 하니까 헷갈렸다.

자바스크립트는 일반적인 배열의 정의에서 벗어나기 때문이다.

Ex. 길이가 고정 되어있지 않음 등

 

자료구조로서 배열과 연결리스트를 비교해보자.

 

1) 메모리 (제목을 뭐라고 지어야할지...)

실제 메모리상에서 배열은 "연결된" 하나의 블록으로 저장되고,

연결리스트는 독립적으로 저장하되 다음 노드의 위치를 참조한다.

 

아주 큰 데이터를 저장하려고 하면

메모리에 그 큰 데이터를 하나의 연결된 블록으로 저장할 수 없을 수도 있다.

 

결국 이렇게 메모리를 사용하기 때문에

배열은 처음부터 정해진 크기를 갖는 것이다.

 

만약 배열을 사용하다가 메모리가 부족하면 이런 과정을 거칠 수 밖에 없다.

1. 크기가 더 큰 새로운 배열을 만든다.
2. 기존 배열을 새로 만든 배열로 옮긴다.

 

 

 

	배열	연결리스트
공통점	자료구조
memory usage(requirement)
데이터 접근	index로 O(1)	O(N)
데이터 삽입
데이터 삭제
memory usage(requirement)	fixed size

똑같은 O(N)인데 왜 연결리스트가 더 빠르다고 하는 거지??

배열은 삽입/삭제 후에 다른 데이터를 옮겨야하니까 복사하는 과정이 있는데..

 

 

 

자료구조를 결정할 때

데이터 사이즈, 어떤 동작을 많이 하는지 고려해서 결정

 

삽입/삭제가 빈번히 일어나면 연결 리스트가 좋고, (근데 경우에 따라 다르다고 함)

데이터에 접근하는 것이 빈번히 일어나면 배열이 좋다.

 

 

---

자바스크립트의 배열이 실제로는 배열이 아니다???

 

JavaScript에서의 배열은 Hash Map이다.

---

참조:

Data Structures: Arrays vs Linked Lists (YouTube) 영어인데 쉽고 친절한 설명

 

 

https://woovictory.github.io/2018/12/27/DataStructure-Diff-of-Array-LinkedList/

 

https://evan-moon.github.io/2019/06/15/diving-into-js-array/