[DataStructure] Array vs LinkedList

Array 와 LinkedList 간의 개념 비교를 카테고리 별로 하고자 한다.

1. 메모리 저장

- 1) Array

  - 연속성을 유지하기 위해 물리적 메모리 상에서 순차적으로 저장

- 2) LinkedList

  - 물리적인 메모리 상에서는 비연속적으로 저장이 되지만

     Linked List 를 구성하는 각각의 Node가 다음 Node의 Address를 가리킴으로써 논리적인 연속성을 가진 자료구조

  - Node 라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address를 저장함

  - 물리적 메모리 상에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 비교적 자유로운 대신,

     Next Address를 추가적으로 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 커짐

  - 데이터가 추가되는 시점에서 메모리를 할당하기 때문에 메모리를 좀 더 효율적으로 사용 가능

 

2. 메모리 할당

- 1) Array

  - 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당

  - Stack 영역에 할당

- 2) LinkedList

  - 런타임 환경에서 메모리가 할당되는 동적 메모리 할당

  - Heap 영역에 할당

 

3. 데이터 접근, 조회

- 1) Array

  - Random Access 가 가능하므로 시간 복잡도가 O(1) 이 소요 

- 2) LinkedList

  - 순차적으로 접근할 수 밖에 없기 때문에 시간 복잡도가 O(n) 이 소요

 

4. 데이터 삽입, 삭제

- 1) Array

  - 데이터 삽입 또는 삭제 시 시간 복잡도가 O(n) 소요

    - 해당 인덱스의 뒤에 있는 모든 원소들은 Shift 를 해야 하기 때문

- 2) LinkedList

  - Array 보다 데이터 삽입 또는 삭제 시 간단, 시간 복잡도가 O(1) 로 짧게 소요

    - 물리적으로 옮길 필요 없이 Next Address 가 가리키는 주소 값만 변경하면 되기 때문

 

5. 출처

- https://www.inflearn.com/course/%EA%B0%9C%EB%B0%9C%EC%9E%90-%EC%A0%84%EA%B3%B5%EB%A9%B4%EC%A0%91-cs-%EC%99%84%EC%A0%84%EC%A0%95%EB%B3%B5 

- https://kimmeh1.tistory.com/473