자료구조
-
자료구조(Data Structure) 정리취업 활동/면접 준비 2021. 1. 1. 15:49
자료구조 - Array 와 Linked List Array는 index로 해당 원소에 접근할 수 있고, 찾고자 하는 원소의 index 값을 알고 있으면, O(1)에 해당 원소로 접근할 수 있습니다. 즉, Random access가 가능하다는 장점이 있습니다. 하지만, 삽입과 삭제의 경우에는 배열의 연속적인 특징을 위해 shift를 해야 하기 때문에 비용이 발생하며, 최악의 경우 O(n)의 시간 복잡도를 가집니다. Linked List는 이러한 문제를 해결할 수 있습니다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지를 기억하고 있습니다. 따라서 삽입, 삭제 연산을 O(1)만에 해결할 수 있습니다. 그러나 index 값으로 접근을 할 수 없기 때문에 탐색 과정에서 최악의 경우 O(n)의 시간 복잡도를 가..