[CS, 자료구조] Array, LinkedList에 대해 알아보자.

🤔 Array란 무엇일까?

가장 기본적인 자료구조인 Array (배열)은 논리적 저장 순서와 물리적 저장 순서가 일치한다. 이는 순차적으로 저장되어 있는 원소들의 순서가 논리적으로 생각했을 때 시작점에서의 상대적인 원소 위치가 일치한다는 뜻이다. 그렇기 때문에 배열은 index 로 접근할 수 있다. 

🧐 Array의 탐색, 삽입, 삭제 시간 복잡도는 어떻게 될까?

즉, 탐색하는 과정에서 random access가 가능하기 때문에, Big O(1) 시간 복잡도를 가진다. 

 

삽입, 삭제 시간 복잡도는 어떻게 될까? 우선, 삽입, 삭제의 대상을 탐색하는 과정이 필요하다. 이 과정은 Big O(1) 시간 복잡도로 탐색이 가능하다. 가령, 삽입을 한다면 삽입할 위치의 값부터 순차적으로 저장되어 있는 원소들을 뒤로 한 칸씩 shift 해주어야 한다. 삭제도 마찬가지로 삭제한 위치부터 순차적으로 저장되어 있는 원소들을 앞으로 한 칸씩 shift 해주어야 한다. 이는 배열의 연속적인 특징을 유지해주기 위해서이다. 결론적으로 Big O(n) 시간 복잡도를 가진다. 

🤔 LinkedList란 무엇일까?

LinkedList (연결리스트)는 이러한 배열의 문제점을 해결하기 위해서 생겨난 자료구조이다. 각각의 원소가 다음 원소가 어떤 원소인지에 대한 포인터를 가지고 있는 자료구조이다.

🧐 LinkedList의 탐색, 삽입, 삭제 시간 복잡도는 어떻게 될까?

우선, 삽입, 삭제 과정을 생각해보자. 삽입하기 위해선 삽입 위치 이전 값의 포인터에 대한 정보와 삽입된 원소에 다음 원소에 대한 포인터 정보를 넣어주면 된다. 또한, 삭제하기 위해서는 삭제할 원소의 이전 원소의 포인터에 삭제할 원소가 가진 포인터 정보만을 전달해주면 된다. 결국, 삽입, 삭제될 원소의 탐색이 완료되었다는 가정하에 Big O(1) 시간 복잡도를 가진다. 

 

하지만, 탐색은 random access가 불가능하기 때문에 첫 원소부터 찾고자 하는 원소까지 일일이 찾아야 한다. 즉, Big O(n) 시간 복잡도를 가진다. 결국, 삽입, 삭제 또한 탐색이 우선적으로 이루어져야 하기 때문에 Big O(n) 시간 복잡도를 가진다고 할 수 있다.

 

LinkedList의 탐색, 삽입, 삭제가 Array에 비해 성능이 같더나 떨어진다. 하지만, LinkedList는 Tree 라는 자료구조에서 유용하게 사용된다.