[자료구조] Arrays vs LinkedList

Array 배열

- 논리적 저장순서와 물리적 저장순서가 일치

- 특정 자료형들이 메모리 공간 상에서 연속적으로 이루어져 있음

- Immutable ( 변경 불가능 )

: 객체가 생성된 이후 그 상태를 변경할 수 없는 디자인 패턴

- 인덱스로 원소에 접근함

: Random Access -> O(1)의 시간 복잡도로 원소에 접근이 가능함

: 삭제 또는 삽입 과정에서는 해당 원소에 접근하고 Shift를 해서 O(n)

: 데이터가 많은 경우 비효율적

- 메모리 공간 활용이 제약적

 

LinkedList

- 논리적 저장순서와 물리적 저장 순서가 다르다

: 데이터 검색 시 처음 노드부터 순환 O(n)

- 메모리 공간상에 노드들이 흩어져 존재함, 각각의 노드가 자신의 다음 노드의 위치를 알고 있음

: 사용자는 제일 첫 번째 노드의 위치만 알고 있음

- 삽입, 삭제 시 원소를 찾고 추가적으로 작업 완료하는데 O(n)

: 검색, 삼입, 삭제 과정 모두 O(n)

 

데이터 삽입 속도

- Array 배열

: 추가적인 Shift때문에 데이터가 많은 경우 비효율적

- LinkedList

: 중간 삽입의 경우 O(n), 양 끝에 삽입하는 경우 O(1)

: 배열보다 빠른 성능을 갖고 있음

 

메모리 할당

- Array

: 메모리에는 선언하자 마자 Compile tim에 할당됨

: 정적 메모리 할당

- LinkedList

: 메모리는 새로운 Node가 추가될 때 Runtime에 할당

: 동적 메모리 할당

 

삽입과 삭제가 빈번하게 일어날땐 LinkedList를 사용, 데이터 접근하는 것이 빈번하다면 Array를 사용!

 

참고 : https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Data%20Structure/%5BData%20Structure%5D%20Array%20vs%20LinkedList.md