배열 vs 리스트

파이썬의 list와 자바스크립트의 array가 이름만 다를 뿐 같은 개념일 줄 알았는데 자료구조 공부를 시작하면서 두 개가 다르다는 것을 알게 되었다.

다음 두 링크를 통해서 시각적으로 수월히 이해가 가능하다.
https://www.youtube.com/watch?v=q41J1npj86M
https://www.youtube.com/watch?v=DzGnME1jIwY

배열(Array)

가장 기본적인 자료구조이다. index를 통해 곧바로 배열에 저장된 원소로 접근할 수 있다. 따라서 접근의 시간 복잡도는 O(1)이 된다. 허나 원하는 값을 찾고자 하면 원소들 모두를 돌아야 될 수 있으므로 탐색은 O(N)이다.

원하는 원소를 삽입하고자 할 때는 원소들이 뒤로 밀려나게(shift) 된다. 접근은 빠르게 할 수 있지만 원소들이 뒤로 밀려나게 되므로 삽입의 경우 시간 복잡도는 O(N)이 된다.

새로운 원소가 삽입되었을 때 공간이 부족할 경우는 기존의 모든 원소들 모두와 새로운 원소를 가진 새로운 배열을 생성하여 반환한다. 1번 생성된 배열의 크기는 늘어나거나 줄어들 수 없기 때문이다.

삭제도 마찬가지이다. 원하는 요소를 삭제하고 앞으로 shift가 일어나 O(N)이 된다.

접근: O(1)

탐색: O(N)

삽입: O(N)

삭제: O(N)

리스트(list)

linked list를 기준으로 리스트를 조사했다.

linked list는 Head -> Node -> Node -> ... -> Node -> Tail로 연결된 구조이다.

원하는 노드나 원하는 값을 찾고자할 때는 Head부터 찾아 들어가야 되기 때문에 O(N)이 될 수 있다. 하지만 만약 Head나 Tail을 삽입하거나 삭제하는 것이라면 O(1)이 된다. 따로 shift가 일어나지 않고 그 Node가 다른 Node를 향하게 하면 되기 때문이다.

하지만 원하는 곳이나 원하는 Node를 삽입하고 삭제하려 하면 결국엔 찾아 들어가야 될기 때문에 O(N)이 된다.

Node를 삭제하고 나서 남은 데이터는 자바스크립트의 경우 GC(Garbage Collecting)된다.

접근: O(N)

탐색: O(N)

삽입: O(1) ~ O(N)

삭제: O(1) O(N)

결론

두 자료구조만 놓고 봤을 경우,

데이터 양은 많으나 삽입/삭제가 거의 없고, 데이터 접근이 빈번할 경우 배열이 유리하다.

반면 데이터 양은 적고 삽입/삭제가 빈번히 일어난다면 리스트가 유리하다.

linked list는 유튜브 재생목록, 멜론 플레이어처럼 처음부터 다음 컨텐츠까지 차례차례 진행이 가능한 곳에 사용되고 있다. 우리가 좋아요를 누르고 나중에 볼 동영상 등으로 컨텐츠를 저장하면 유튜브 재생목록이나 멜론 플레이어는 기존에 쌓여있던 컨텐츠의 뒤에 차곡차곡 컨텐츠를 저장한다. linked list에서 add to tail 방식이라고 볼 수 있겠다.

참고 링크
https://one-zero.tistory.com/entry/%EB%B0%B0%EC%97%B4%EA%B3%BC-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8-Array-LinkedList
https://codingstudyroom.tistory.com/24
https://www.youtube.com/watch?v=q41J1npj86M