Array, LinkedList, HashTable, Stack & Queue 시간 복잡도

1. Arrays

- Accessing a value at a given index : O(1)

- Updating a value at a given index : O(1)

- Inserting a value at the beginning : O(n)

- Inserting a value in the middle : O(n)

- Inserting a value at the end : O(1) - dynamic array, O(n) - static array

- Removing a value at the beginning : O(n)

- Removing a value in the middle : O(n)

- Removing a value at the end : O(1)

- Copying the array : O(n)

2. LinkedLists - need additional memory for pointer unlike arrays

when single linked list

- Accessing the head : O(1)

- Accessing the tail : O(n)

- Accessing a middle node : O(n)

- Inserting / Removing the head : O(1)

- Inserting / Removing the tail : O(n) to access, O(1) to execute

- Inserting / Removing a middle node :  O(n) to access, O(1) to execute

- Searching for a value : O(n)

 

when doubly linked list

- Accessing the head : O(1)

- Accessing the tail : O(1)

- Accessing a middle node : O(n)

- Inserting / Removing the head : O(1)

- Inserting / Removing the tail : O(1)

- Inserting / Removing a middle node : O(n) to access, O(1) to execute

- Searching for a value : O(n)

3. HashTable - dynamic array of linkedlist

- Inserting a key/value pair : O(1) on average, O(n) in the worst case

- Removing a key/value pair : O(1) on average, O(n) in the worst case

- Looking up a key : O(1) on average, O(n) in the worst case

4. Stack & Queue

when Stack

- Pushing an element onto the stack : O(1)

- Popping an element off the stack : O(1)

- Peeking at the element on the top of the stack :  O(1)

- Searching for an element in the stack : O(n)

 

Stack is typically implemented with a dynamic array or singly linked list

 

when Queue

- Enqueing an element into the queue : O(1)

- Dequeuing an element out of the queue : O(1)

- Peeking at the element at the front of the queue : O(1)

- Searching for an element in the queue : O(n)

 

A queue is typically implemented with a doubly linked list