선형 자료구조의 배열과 연결 리스트 비교.
자바스크립트의 배열과 다른 점
자바스크립트의 배열은 인덱스를 키로 갖고, length 프로퍼티를 가지고 있는 일반적인 배열을 흉내 낸 특수한 객체이다.
자바스크립트의 배열은 메모리 공간의 크기가 다르고, 연속적으로 이어져 있지 않는 희소 배열이다.
자료구조에서 말하는 배열은 같은 데이터 타입과 동일한 크기의 메모리 공간이 연속적으로 나열된 자료구조(밀집 배열)를 말한다.
Array (배열)
데이터 타입과 크기가 정해져 있고, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.
인덱스가 있어 랜덤(직접) 접근이 가능하다.
데이터의 크기는 정해져 있기 때문에 생성 후 변경할 수 없다.
Linked List (연결 리스트)
각 노드의 데이터가 포인터로 연결되어 있는 선형 자료구조.
인덱스가 존재하지 않아 랜덤 접근이 불가능하다.
노드: 데이터와 포인터로 구성
head 노드: 맨 앞에 있는 노드
포인터: 메모리 주소를 가리키는 변수, 다른 노드의 위치 정보
단일 연결 리스트: 각 노드에 자료 공간과 next 포인터 한 개만 가진다.
이중 연결 리스트: 포인터 공간이 두 개 있고 next, prev 포인터를 가진다.
원형 연결 리스트: 단일 연결 리스트에서 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.
자바스크립트에서 Linked List 구현
배열과 연결 리스트 비교
접근
배열은 랜덤 접근이 가능하지만 연결 리스트는 불가능하기 때문에 어떤 요소에 접근하기 위해서는 반드시 첫 번째 요소부터 접근해야 한다.
따라서 접근을 할 때, 배열은 배열의 크기와 상관 없이 동일한 시간이 걸리지만, 연결 리스트는 배열의 크기에 따라 커지게 된다.
삽입/삭제
배열은 마지막 요소면 삽입, 삭제 만으로 끝나지만 마지막 요소가 아니라면 해당 요소 뒤의 요소들을 한 칸씩 옮겨야 한다.
연결 리스트는 첫 번째 요소라면 다음 요소만 연결해 주면 끝나지만 그 이후의 요소라면 순차적으로 탐색하는 시간이 걸린다.
메모리
연결 리스트는 데이터 외에도 포인터를 저장할 공간이 필요하기 때문에 더 많은 메모리가 필요하다.
시간 복잡도: 문제를 해결하는데 걸리는 시간과 입력 함수 관계를 나타내는 척도. 주로 빅-오 표기법을 사용해 나타낸다.
빅 오(Big O) 표기법: 계수와 낮은 차수의 항을 제외시키는 방법.
ex) 입력의 크기가 n일 때 걸리는 시간이 인 경우 로 표기
접근 | 첫 요소 삽입/삭제 | 중간 요소 삽입/삭제 | 마지막 요소 삽입/삭제 | |
Linked List | O(n) | O(1) | O(n) / search time + O(1) | O(n) |
Array | O(1) | O(n) | O(n) | O(1) |
일반적으로 접근이 잦은 작업이라면 Array, 삽입/삭제가 많은 작업이라면 Linked List를 사용하는 것이 좋다.
정리
Q. 연결 리스트와 배열의 차이점은?
Linked List | Array | |
접근 | 순차적으로 접근하기 때문에 느림 | 임의로 접근 가능하기 때문에 빠름 |
삽입/삭제 | 요소를 찾아서 연결만 바꿔주면 되기 때문에 빠름 | 삽입/삭제 위치 이후 요소들을 한 칸씩 이동해야하기 때문에 느림 |
메모리 | 연속적으로 배치되지 않기 때문에 포인터 공간과 데이터 공간을 모두 사용해야 하므로 비효율적 | 연속적으로 배치되므로 효율적 |
Reference
