[자료구조] 배열(Array)과 리스트(List)

👉 배열(Array)

• 가장 기본적인 자료구조
• 여러 개의 변수를 담는 공간으로 이해 가능
• 배열은 인덱스(index)가 존재, 인덱스는 0부터 시작
• 특정한 인덱스 직접적으로 접근 가능 -> 수행 시간: O(1)
• 자바스크립트의 배열은 기본적으로 동적배열로 정해져있음

장단점

• 캐시 히트 가능성이 높으며, 조회가 빠르다.
• 배열의 크기를 미리 지정해야 하는 것이 일반적이므로, 데이터의 추가 및 삭제에 한계가 있다.

👉 연결 리스트(Linked List)

• 배열과 다르게 크기가 정해져 있지 않고, 리스트의 크기는 동적으로 변경 가능

장단점

• 장점: 포인터를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편
• 단점: 특정 번째의 원소를 검색할 때는 앞에서부터 원소를 찾아야 하므로, 데이터 검색 속도가 느리다.

 

👉 코딩 테스트를 위한 JS의 배열

• JS에서는 배열 기능을 제공한다.
• 일반적인 프로그래밍 언어에서의 배열
• JS배열은 일반 배열처럼 임의의 인덱스 이용 -> 직접적인 접근 가능
• JS배열은 동적 배열 기능 제공, 맨 뒤의 위치에 원소 추가 가능
• 배열 용량이 가득 차면 자동으로 크기 증가
• 내부적으로 포인터를 사용, 연결 리스트의 장점도 갖고있음
• 배열(Array) 혹은 스택(Stack)의 기능이 필요할 때 사용할 수 있음
• 큐(Queue)의 기능을 제공하지는 못함

 

연결 리스트 

• 연결 리스튼느 각 노드가 한 줄로 연결되어 있는 자료구조
• 다양한 자료구조 구현 가능 -> 스택, 큐 등

 

연결 리스트(Linked List) VS 배열(Array)

• 특정 위치의 데이터를 삭제할 때, 일반적인 배열에서는 O(N)만큼의 시간이 소요
• 연결 리스트를 이용하면 단순히 연결만 끊어주면 됨 (원소를 삭제할 필요가 없음)
• 삭제할 위치를 정확히 알고 있는 경우 O(1)의 시간이 소요
• 물리적인 위치를 한 칸씩 옮기지 않아도 삽입 가능

 

 

출처: https://fastcampus.co.kr/dev_online_upjscodingtest

JavaScript 코딩테스트 131개 예제 & CS지식으로 끝내기 | 패스트캠퍼스