배열

배열은 프로그래밍에서 기본적으로 제공해주는 자료구조이다.
배열을 선언했다면 운영체제는 메모리에서 숫자가 들어갈 수 있는 빈 공간을 찾아서 순서대로 값들을 할당해줍니다. 할당하지 않은 부분은 의미없는 쓰레기 값이 저장된다.

그리고 운영체제는 배열의 시작 주소만 기억한다. 프로그래머가 배열의 세번째 원소에 접근하고 싶다면 arr[2] 이런식으로 접근한다. 운영체제는 이런 메모리 공간들을 다 기억하기 때문에 길이 상관없이 한 번에 가져온다. 배열은 읽기/쓰기 등 참조에서 좋은 성능을 보여준다.

배열의 성능은 좋지만 데이터의 삽입, 삭제 성능은 그리 좋지 않다.
자바스크립트 배열은 상황에 따라서 연속적, 불연속적으로 메모리를 할당하지만 대부분은 불연속적으로 할당한다.

특징

• 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다.
• 메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 째문에, index를 통한 접근이 용이하다.
• 배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없다.
• 인덱스를 통한 빠른 접근이 가능하지만, 삽입/삭제가 오래 걸리고, 배열 중간에 있는 데이터가 삭제되면 공간 낭비가 발생한다.
• 크기 예측이 힘들기 때문에 메모리 낭비가 발생할 수 있다.
• 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때 사용한다.

연결 리스트

배열의 단점을 해결하기 위해서, 저장하려는 데이터들을 메모리 공간에 분산 할당하고 이 데이터들을 서로 연결해준다. 이것은 노드라는 것을 만들어서 수행한다. 노드의 구조는 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나를 말한다.

필요한 노드를 만들어 연결하는데 이런 구조로 연결 리스트라고 부른다.

특징

• 연결 리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 head, 마지막 노드를 tail이라고 한다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
• 배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
• 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.
• Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.
• 삽입과 삭제가 용이하지만, 임의 접근이 불가능하여, 처음부터 탐색을 진행해야 한다.
• 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때 사용한다.