선형 자료구조의 배열과 연결 리스트 비교.
<aside> 💡 자바스크립트의 배열과 다른 점 자바스크립트의 배열은 인덱스를 키로 갖고, length 프로퍼티를 가지고 있는 일반적인 배열을 흉내 낸 특수한 객체이다.
자바스크립트의 배열은 메모리 공간의 크기가 다르고, 연속적으로 이어져 있지 않는 희소 배열이다. 자료구조에서 말하는 배열은 같은 데이터 타입과 동일한 크기의 메모리 공간이 연속적으로 나열된 자료구조(밀집 배열)를 말한다.
</aside>
데이터 타입과 크기가 정해져 있고, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.
인덱스가 있어 랜덤(직접) 접근이 가능하다.
데이터의 크기는 정해져 있기 때문에 생성 후 변경할 수 없다.
각 노드의 데이터가 포인터로 연결되어 있는 선형 자료구조.
인덱스가 존재하지 않아 랜덤 접근이 불가능하다.
노드: 데이터와 포인터로 구성
head 노드: 맨 앞에 있는 노드
포인터: 메모리 주소를 가리키는 변수, 다른 노드의 위치 정보
단일 연결 리스트: 각 노드에 자료 공간과 next 포인터 한 개만 가진다.
이중 연결 리스트: 포인터 공간이 두 개 있고 next, prev 포인터를 가진다.
원형 연결 리스트: 단일 연결 리스트에서 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.