[CS, 자료구조] Array, LinkedList에 대해 알아보자.
🤔 Array란 무엇일까? 가장 기본적인 자료구조인 Array (배열)은 논리적 저장 순서와 물리적 저장 순서가 일치한다. 이는 순차적으로 저장되어 있는 원소들의 순서가 논리적으로 생각했을 때 시작점에서의 상대적인 원소 위치가 일치한다는 뜻이다. 그렇기 때문에 배열은 index 로 접근할 수 있다. 🧐 Array의 탐색, 삽입, 삭제 시간 복잡도는 어떻게 될까? 즉, 탐색하는 과정에서 random access가 가능하기 때문에, Big O(1) 시간 복잡도를 가진다. 삽입, 삭제 시간 복잡도는 어떻게 될까? 우선, 삽입, 삭제의 대상을 탐색하는 과정이 필요하다. 이 과정은 Big O(1) 시간 복잡도로 탐색이 가능하다. 가령, 삽입을 한다면 삽입할 위치의 값부터 순차적으로 저장되어 있는 원소들을 뒤로 한..