Array와 LinkedList의 차이

Array

논리적 저장순서와 물리적 저장 순서가 일치한다.
인덱스로 해당 원소에 접근이 가능하다.
인덱스만 알고 있다면 시간 복잡도 O(1)만에 해당 원소로 접근할 수 있다.
(Random Access가 가능)
배열의 원소를 삭제할 경우 삭제한 원소보다 큰 인덱스를 가진 원소들을 옮겨줘야(Shift) 하기 때문에 시간 복잡도 O(n)이 걸린다.
삽입의 경우, 새로운 원소를 추가하고 모든 원소들의 인덱스를 1씩 Shift 해줘야 하므로 시간 복잡도 O(n)이 걸린다.
제한적인 크기를 갖는다.

LinkedList

자료의 주소 값으로 노드를 이용해 서로 연결되어 있는 구조를 갖는다.
삽입과 삭제의 경우 LinkedList가 Array보다 (경우에따라)속도가 빠르다.
원하는 값을 찾기 위해서 최소 한 번은 리스트를 순회하여야 하므로 O(n)의 시간 복잡도를 갖는다.
트리의 근간이 되는 자료구조이다.

비교:

array는 선언할때 크기가 고정적이고 순차적이다. 인덱스만 안다면 접근이 가능하고 비교적 접근속도가 빠르다. 삽입/삭제시 기존 데이터들의 위치를 뒤로 혹은 앞으로 이동시켜 비효율적이다.

linkedlist는 데이터를 삽입할때마다 증가해서 동적이고 랜덤으로 배치된다. 하나하나 위치를 따라가서 접근해야해서 배열에비해 속도가 느리다. 삽입/삭제시 메모리를 할당/해제할 필요가 없어 효율적이다.