Array & Linked List

정의

Array: 메모리가 연속적으로 할당되어 index 로 빠르게 접근이 가능한 구조
Linked List: 메모리가 연속적으로 할당되지 않고 하나의 노드가 다음 노드의 메모리 주소를 참조하는 동적인 선형 데이터 구조

장단점

Array

장점
- index가 존재해 배열 값의 index를 알면 바로 참조가 가능
단점
- Array는 메모리 공간에 미리 할당할 크기를 정해두고 생성함으로 데이터가 계속 늘어나는 상황에서 비효율
- Array 중간에 데이터 삽입 및 삭제 연산 비효율
  - 예) Size가 6인 Array에서 4번째 값 삭제 연산 시 4번째 값을 삭제한 후 이후에 값들을 앞으로 당겨야 한다.

Linked List

장점
- Array처럼 크기를 미리 지정하지 않아도 된다.
- 데이터가 늘어나는 상황에서 효율적
- 중간에서 데이터의 삽입 및 삭제 연산이 비교적 효율적
  - 예) Size가 6인 Linked List에서 4번째 값 삭제 연산 시 4번재 노드를 삭제 후 3번째 노드가 5번째 노드의 주소를 참조하게만 하면 된다.
단점
- k번째 값을 찾아라 연산 시 Array에 비해 비효율적이다.
  - Link List를 이루는 노드들은 메모리 주소가 재각각 다르다. 그러므로 첫번째 노드부터 다 참조를 해야만 k번재 노드의 값을 찾을 수 있다.
- 각 노드는 값 이외에 주소를 포함해야 하기 때문에 메모리 크기 관점에서 비효율

비교

Array와 Linked List 구조의 핵심적인 차이점은 메모리의 할당 방식이다.

Array의 경우 메모리 주소가 연속적으로 할당되어 있다.
Linked List의 경우 하나의 노드가 다음 노드의 메모리주소를 참조하는 동적인 형태로 연결되어 있기 때문에 메모리가 연속적으로 할당되어 있지 않다.

이러한 차이점 때문에 Array 특정 인덱스에 접근하는 시간은 O(1) 이지만 Linked List 는 O(n) 이다.