[자료구조] Array 와 ArrayList

[자료구조] Array 와 ArrayList

• Array

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

 - 인덱스 값을 알고 있다면 Big-O(1)에 해당 원소로 접근 가능

 - random access(비순차적 접근)가 가능

 

 [단점]

 - 삭제 시, 연속적 특징이 깨진다.

 - 삭제한 원소보다 큰 인덱스 갖는 원소들을 shift 해줘야 하는 비용 발생 = 시간복잡도 O(n)

 - Array 자료구조의 삭제 기능에 대한 time complexity --> worst case : O(n)

 - 삽입 시에도 첫번째에 원소를 추가하고 싶다면 1씩 shift해줘야 한다. --> O(n)

• Linked list

 - 위의 단점을 해결하기 위한 대안책

 - 자기 자신 다음에 올 원소만 기억

 - 이 부분만 바꿔주면 삽입과 삭제를 O(n)에 가능

 - tree 구조의 근간

 

 [단점] 

 - 원하는 위치를 탐색할 때 첫 번째 원소부터 다 확인해야만 한다.

 - 논리적 저장 순서와 물리적 저장 순서 일치하지 않기 때문.

 - 어떤 원소를 추가 및 삭제할 때 탐색으로 인한 O(n)의 시간 발생

 - 결국 search에도 O(n)의 시간, 삽입/삭제에서도 O(n)의 시간 갖는다.

• 그렇다면 Sorting 시 어떤 것을?

 - 어떤 Sorting 알고리즘을 선택했느냐에 따라 다르다.

 [예시] 

  - Merge Sort의 경우 Linked List가 유리 : 배열을 하나 더 쓰게 되는 것을 막는다.

  - Quick Sort의 경우 Array가 유리

 

 

[참조] https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure