Interview #01 | Array와 List의 차이

📚 개념 요약

📌 Array

선언할 때 크기와 데이터 타입을 지정해야 한다. 따라서 계속 데이터가 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기에 부적합하다.

또한 중간에 데이터를 삽입하거나 삭제할 때도 매우 비효율적이다. 4번째 index 값에 새로운 값을 넣어야 한다면? 원래값을 뒤로 밀어내고 해당 index에 덮어씌워야 한다. 기본적으로 사이즈를 정해놓은 배열에서는 해결하기엔 부적합한 점이 많다.

대신, 배열을 사용하면 메모리 공간에 연속적으로 나열되어 있기 때문에 index가 존재하기 때문에 위치를 바로 알 수 있어 검색에 편한 장점이 있다.

자바스크립트 배열은 해시 테이블로 구현된 객체이므로 인덱스로 배열 요소에 접근하는 경우, 일반적인 배열보다 성능적인 면에서 느릴 수 밖에 없는 구조적인 단점을 갖는다. 하지만 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 일반적인 배열보다 빠른 성능을 기대할 수 있다.

📌 LinkedList

연결리스트에는 단일, 다중 등 여러가지가 존재한다. 종류가 무엇이든, 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 되어있다. (단일은 뒤에 노드만 가리키고, 다중은 앞뒤 노드를 모두 가리키는 차이)

이런 방식을 활용하면서, 데이터의 중간에 삽입/삭제를 하더라도 전체를 돌지 않아도 이전 값과 다음값이 가르켰던 주소값만 수정하여 연결시켜주면 되기 때문에 빠르게 진행할 수 있다.

이렇게만 보면 가장 좋은 방법 같아 보이지만, “List의 k번째 값을 찾아라”에서는 비효율적이다.

💡 질문

❓ Array와 List의 차이

배열과 리스트 둘 다 많은 양의 데이터를 하나의 변수로 관리하기 위해서 사용되는 자료구조로 저장 측면과 효율 측면에서 차이점이 있습니다.

저장 측면에서 배열은 연속적으로 저장이 되도록 하고, 선언할 때 그 크기가 지정되어야 합니다. 반면에 리스트는 각 노드의 포인터가 다른 노드를 가리키는 방식으로 저장이 되어있기 때문에 크기가 동적입니다.

효율 측면에서 차이점은 배열은 연속적으로 저장되어 있기 때문에 index, 즉 주소값을 offset 기준으로 값에 접근해서 접근속도가 빠르지만 값을 추가/삭제하는 속도는 느립니다. 반면 리스트는 연결되어 있는 노드 1~2개의 포인터 주소만 변경하면 되기 때문에 추가/삭제는 빠르지만 저장 위치가 모두 떨어져 있기 때문에 데이터 접근 속도가 느립니다.