[Data Structures] Array & Linked List

Array

Features

• 선형 자료구조이다.
• 메모리상에 연속적으로 저장된다.
• 배열의 크기는 생성 후 변경할 수 없다. 동적 배열의 경우 가능하나 메모리 할당을 새로 받아 복사하는 과정을 거쳐야 해서 많은 비용이 소모된다.
• compile time에 할당된다.

Element access

index를 통한 random access를 지원하여 $O(1)$이 소요된다.

Insertion & Deletion

배열의 중간에 삽입 및 삭제 시 연속된 구조를 유지하기 위해 데이터를 shift 해야 하므로 $O(n)$이 소요된다.
배열의 끝에 삽입 및 삭제 시 $O(1)$이 소요된다.

Linked List

Features

• 선형 자료구조이다.
• 메모리상에 흩어져 저장된다.
• 여러 개의 노드들이 순차적으로 연결되어 있는 구조를 가지고 있으며 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다. 따라서 Array보다 메모리를 더 사용한다.
• run time에 할당된다.

Element access

특정 데이터 조회 시 random access가 불가능하여 처음 노드부터 순회하며 sequential access를하기 때문에 $O(n)$이 소요된다.

Insertion & Deletion

처음과 마지막 노드의 삽입 및 삭제는 $O(1)$이 소요된다.
중간 노드의 삽입 및 삭제는 순차적 탐색을 해야 하므로 $O(n)$이 소요된다.

Array vs. Linked List

	Array	Linked List
장점	데이터 조회가 빠르다	데이터 삽입 및 삭제가 빠르다
단점	데이터 삽입 및 삭제가 상대적으로 오래 걸린다	데이터 조회가 상대적으로 오래 걸린다

이러한 장단점으로 배열은 데이터 조회가 잦을 때, 링크드 리스트는 삽입과 삭제가 잦을 때 사용하는 것이 좋다.