Read More

## Linked List and Binary Search

### Searching on a linked list

The reason why the linked list cannot achieve an O(log n) is in terms of search is because of how it is built. A linked list by definition is made up of linked nodes that are scattered throughout the memory. This means that these nodes are not contagiously arranged therefore they cannot be accessed through "index" or "subscripts" like an array. Therefore when we search, we have to go through one link through another to go find a target node. There's no way that we can jump directly to the node or skip some other nodes to shorten the search.## A candidate modification in linked lists

Nodes are not duplicated but only references therefore if we have "N" nodes then the space it will take is N too. However, if we need to take account that a "pointer" takes space in memory then we can compute it as N^{2}and this is because for every N there is a pointer to all other Ns. The asymptotic of inserting a node would be O(2n). It takes O(n) to first find the location in the list after which it will take another O(n) again to make the node point to other nodes that appear after and before it.

**Binary Search on a Modified List**One of the requirements of a binary search is that data should be sorted. So right now we have a node that has a previous node and a next node. It will have also have a list of pointers that points to all other previous nodes and another list of pointers that points to the nodes after it. The mainline list should be sorted in ascending order and the list of pointers is also sorted. The pseudocode is as follows:

- Set the current node as the head node.
- If the current node's data is the value we're looking for then stop, we're done.
- If the value we’re looking for is greater than the current nodes’ data.
- Get the middle node of the list of pointers after it.
- Set the middle node as the current node.
- Repeat step 2.

- Otherwise, if the value we're looking for is lesser than the current node's data.
- Get the middle node of the list of pointers before it.
- Set the middle node as the current node.
- Repeat step 2.