Array & LinkedList

Array (배열)

Array는 특정 크기만큼 연속된 메모리 공간에 데이터를 저장하는 자료구조이다. Array는 선언될 때 크기가 같이 선언이 되어야한다. 또한, 컴파일 과정에서 메모리가 stack영역에 할당되는 정적 메모리 할당이다. 이러하여 Array는 데이터 조회 시 동적 메모리 할당보다 속도가 빠르다.

LinkedList (연결 리스트)

LinkedList는 각각의 데이터가 메모리 공간 상에 고유한 노드로 존재한다. 그리고 이 노드는 자신의 앞에 있는 데이터와 뒤에 있는 데이터에 대한 주소를 기억하고 있다. 이러한 이유 때문에 List의 크기는 선언을 미리 안해두어도 된다. 런타임 환경에서 메모리가 heap 영역에 할당되는 동적 메모리 할당이다. 이러하여 LinkedList 데이터 추가 및 삭제 시 정적 메모리 할당보다 속도가 빠르다.

Array vs LinkedList

1. 메모리 할당
   Array : 선언 될 때, 컴파일 과정에서 Stack 영역 할당
   LinkedList : 새로운 node(데이터)가 추가 될때, 런타임 환경에서 heap 영역 할당
2. 크기
   Array : 선언 될 때 지정
   LinkedList : node 들이 추가될 때 runtime 시점에서 크기가 커질 수 있음.
3. 데이터 조회
   Array : element 들을 index 를 통해 직접적으로 접근 (시간 복잡도 : O(1))
   LinkedList : element 에 접근할 때, 처음 부터 순차적으로 접근하면서 찾아야 함 (시간 복잡도 : O(N))
4. 데이터 추가 및 삭제
   Array : 인덱스로 접근 후 삽입 및 삭제 O(1) + 전체 배열 요소를 1씩 Shift O(N).
   LinkedList : 삽입하려는 위치 접근 후 삽입 및 삭제 O(N). 만약, 맨 앞과 뒤에 삽입 및 삭제한다면 O(1).