배열과 연결 리스트 모두 데이터를 저장하고 관리하는 자료구조이다.

이 때 배열은 인덱스를 사용하여 요소에 직접적으로 접근하고, 연결 리스트는 각 노드의 주소를 따라가며 접근하는 방식으로 접근한다는 차이점을 가지고 있다.

Array (배열)

특징

배열은 유사한 데이터 유형 요소의 모음으로 구성된 선형 데이터 구조(sequence container)이며 각 요소는 적어도 하나의 인덱스 또는 키로 식별된다.

생성 시 stack에 메모리가 할당되며 할당된 배열의 크기는 선언 시 지정되어야 하고 런타임 중에 크기를 조정할 수 없다. (자바스크립트과 같은 대부분의 스크립트 언어는 배열의 크기를 동적으로 변경할 수 있다.) 연속된 공간에 데이터들이 나열되어 있기 때문에 처음 주소만 알면 다른 위치도 쉽게 알 수 있다는 특징이 있다.

하지만 데이터를 빈번하게 데이터를 추가하거나 삭제할 때는 효율적이지 못하다. 만약 데이터를 중간에 추가하려면 추가하려고 하는 자리를 비우고 뒤에 있는 데이터를 한 칸씩 뒤로 밀어야하는 문제가 생긴다.

따라서 데이터를 추가하거나 삭제할 때 배열은 좋은 선택이 되지 못한다.

시간 복잡도

삽입/삭제

배열의 맨 앞에 삽입/삭제하는 경우 : O(n)
배열의 맨 뒤에 삽입/삭제하는 경우 : O(1)
배열의 중간에 삽입/삭제하는 경우 : O(n)

탐색

O(1)

---

Linked List

특징

리스트 역시 배열과 같이 데이터를 순차적으로 저장하는 선형 데이터 구조(sequence container)이며, 각 노드가 데이터 필드와 목록의 다음 노드에 대한 참조(링크)를 포함하는 노드(요소)로 구성되어있다.

첫번째 노드를 헤드(head), 마지막 노드를 테일(tail)이라고 부르며 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된다.

생성 시 heap에 메모리가 할당된다.

시간 복잡도

삽입, 삭제

리스트의 맨 앞/뒤에 삽입 또는 삭제하는 경우 : O(1)
리스트의 중간에 삽입 또는 삭제하는 경우 : O(n) (탐색하는 시간)

탐색

O(n)

---

배열과 연결 리스트의 차이점

배열 (Array)	연결 리스트 (Linked List)
정적 자료구조	동적 자료구조
메모리 크기가 선언 시점에 정해진다 (javascript 제외)	메모리 크기가 다양하다(node 추가/삭제에 따라 유동적)
연속된 메모리 주소 할당	연속된 메모리 주소를 할당받지 않음.
인덱스(index)	노드(Node) - 데이터, 포인터
접근과 탐색이 편리	추가와 삭제가 편리
빠른 접근 O 많은 데이터 추가/삭제 경우가 적을 때	추가/삭제 O 검색 빈도가 적을 때