Here, I practice all the things I learn from the PHP 7 Data Structures And Algorithms book I'm reading.
I also picked up some videos and great articles too. See below for links.
- PHP Linked List
- Searching, O(n): Having to traverse every element to find search item.
- Insertion, O(1) - O(n): Inserting at the head (start) takes constant time but insertion anywhere else requires some amount of traversal.
- Deletion, O(1) - O(n): Same as insertion, removing the first node takes a constant time while removal from any other position requires some traversal.
- Traversal, O(n): Have to look at every node.
- Space Complexity, O(n): New nodes take up more memory.
- PHP Stack
- PHP Binary Search Tree
- Searching, O(log n) - O(n): Depending on how balanced the Tree is. In a perfectly balanced Tree, searching is same as in an array using binary search as every level deeper reduces the options by half. But in the most unbalanced tree, it's identical to a LinkedList and you'd have to traverse every item.
- Insertion, O(log n) - O(n): Same as searching. The shape of the tree affects the operation.
- Deletion, O(log n) - O(n): This depends on first finding the node to remove, so it is as fast as you can search.
- Traversal, O(n): Looks at every node.
- Space Complexity, O(n): New nodes take up more memory.
- AVL Tree: A self-balancing Binary Search Tree. Operations are O(log n) as it's always best case scenario.
- Red-Black Tree: Another self-balancing Tree. Operations are O(log n) as it's always best case scenario even though it's not always perfectly balanced.
- PHP Hash Table aka HashMap.
- Insertion, O(1): Using unique hashes avoid collisions and gives constant insertions.
- Searching, O(1): Constant time lookup due to unique hashes again.
- Deletion, O(1): Constant time lookup and removal.
- Traversal (Listing all items), O(n): Listing all items involves actually traversing every item.
- Worst Case Scenario: When hashes are not unique, collisions occur and a LinkedList might be employed. This leads to O(n) time for all operations.
- Space Complexity, O(n): New key-value pairs use new memory space.
- PHP Trie
- Insertion, O(n): Where
nis the length of the string to be inserted. You have to either insertncharacters or traversencharacters on every insertion. - Searching, O(n):
nis as stated above. You have to traverse every character to confirm validity of the word. - Deletion, O(n):
nis as stated above. You have to traverse every character to get the word, and might have to delete every character too.
- Insertion, O(n): Where
- PHP Binary Max Heap