Array와 LinkedList의 차이

배열(Array)

: 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조 -> 인덱스를 통해 접근이 용이

  배열의 크기는 생성 시에 결정하며 변경이 불가하다.

 

장점

메모리 상에 연속적으로 저장되어 있어 index만 알면 Random Access 가능

(* Random Access : 자료의 주소를 알고 있다면 모든 자료에 대해 동일한 시간에 접근이 가능한 방식)

 

단점

삽입, 삭제 시 삽입이나 삭제를 하려는 위치 이후의 데이터 값을 모두 한칸씩 이동시켜야 하므로 비효율적

배열의 크기를 변경할 수 없음

 

시간복잡도

탐색 : O(1)  (index를 아는 경우)

삽입/삭제 : O(n)

 

LinkedList

: 노드들이 순차적으로 연결된 형태를 띄고 있으며 첫 노드는 head, 마지막 노드는 tail이라 한다.

배열과 다르게 메모리에 연속적으로 저장되어 있지 않고 각 노드들이 자신의 데이터와 다음 노드에 대한 정보를 가지고 있다.

 

장점

필요할 때 크기를 변경할 수 있어 메모리 관리에 효율적.

삽입/삭제가 빠르다(배열처럼 데이터들을 옮기지 않아도 됨)

 

단점

탐색 시에 무조건 첫번째 노드부터 순차적으로 탐색해야 한다.

 

시간 복잡도

탐색 : O(n)

삽입/삭제 : O(1)  - 하지만 삽입/삭제 위치를 찾기위해 데이터들을 탐색하는 시간이 필요하므로 O(n)

 

 

용도

배열 : 데이터에 빠른 접근이 요구되거나 삽입/삭제가 잦지 않을 때

linked list : 삽입/삭제가 잦고 탐색 빈도가 적을 때