분류 전체보기

1. Arrays vs Linked List

Array Array는, 인덱스와 인덱스에 대응하는 데이터들도 이루어진 자료구조이다. 따라서 인덱스로 해당 원소에 접근할 수 있다. 따라서 해당 원소의 인덱스 값을 알고 있으면 O(1)에 접근 할 수 있다. 즉, Random Access가 가능하다는 장점이 있다. 하지만, 삭제 또는 삽입의 과정에서 해당 원소에 접근해 작업을 완료한 후 (O(1)의 시간복잡도 발생) 추가적인 작업이 필요하다. 삭제의 경우, 삭제한 원소를 기준으로 더 큰 인덱스를 가지고 있는 원소들을 오른쪽으로 이동시켜야 하므로 최악의 경우 O(n)의 시간복잡도가 발생한다. 삽입의 경우, 삽입한 원소를 기준으로 더 큰 인덱스를 가지고 있는 원소들을 오른쪽으로 이동시켜야 하므로 최악의 경우 O(n)의 시간복잡도가 발생한다. Linked Li..