## Data Structures Review

Data Structures Interview Questions

## Linear Data Structures – Lists

Array, Linked List (Single, Double, Circular), Stack, Queue

## Hierarchical – Trees

Binary Tree, Binary Search Tree (BST), B-Tree, Red-Black Tree

## How Data Structures are used

Storage structures (arrays, linked structures, hash tables)

process-oriented data structures (stacks, queues, priority queues, iterators), and descriptive data structures (collections, sets, linear lists, binary trees, etc.)

## Complex Structures

Priority Queues

Hash Tables

## Graph

“Nearly all graph problems will somehow use a grid or network in the problem, but sometimes these will be well disguised. Secondly, if you are required to find a path of any sort, it is usually a graph problem as well. Some common keywords associated with graph problems are: vertices, nodes, edges, connections, connectivity, paths, cycles and direction.” -TopCoder

“They can range in difficulty from finding a path on a 2D grid from a start location to an end location, to something as hard as finding the maximum amount of water that you can route through a set of pipes, each of which has a maximum capacity (also known as the maximum-flow minimum-cut problem)” -TopCoder

“An example of one of the simplest types of graphs is a singly linked list!” -TopCoder

A tree only allows a node to have children, and there cannot be any loops in the tree, with a more general graph we can represent many different situations.

TopCoder – Introduction to Graphs and Their Data Structures

## Matrix

A multi-dimensional array.

Uses:

– To represent class hierarchy using Boolean square matrix

– For data encryption and decryption

– To represent traffic flow and plumbing in a network

– To implement graph theory of node representation

An adjacency matrix is often used in the representation of graphs as an alternative to adjacency lists

## Data Structures Performance

Chart from http://bigocheatsheet.com/

Data Structure | Time Complexity | Space Complexity | |||||||
---|---|---|---|---|---|---|---|---|---|

Average | Worst | Worst | |||||||

Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||

Array | `Θ(1)` |
`Θ(n)` |
`Θ(n)` |
`Θ(n)` |
`O(1)` |
`O(n)` |
`O(n)` |
`O(n)` |
`O(n)` |

Stack | `Θ(n)` |
`Θ(n)` |
`Θ(1)` |
`Θ(1)` |
`O(n)` |
`O(n)` |
`O(1)` |
`O(1)` |
`O(n)` |

Queue | `Θ(n)` |
`Θ(n)` |
`Θ(1)` |
`Θ(1)` |
`O(n)` |
`O(n)` |
`O(1)` |
`O(1)` |
`O(n)` |

Singly-Linked List | `Θ(n)` |
`Θ(n)` |
`Θ(1)` |
`Θ(1)` |
`O(n)` |
`O(n)` |
`O(1)` |
`O(1)` |
`O(n)` |

Doubly-Linked List | `Θ(n)` |
`Θ(n)` |
`Θ(1)` |
`Θ(1)` |
`O(n)` |
`O(n)` |
`O(1)` |
`O(1)` |
`O(n)` |

Skip List | `Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`O(n)` |
`O(n)` |
`O(n)` |
`O(n)` |
`O(n log(n))` |

Hash Table | `N/A` |
`Θ(1)` |
`Θ(1)` |
`Θ(1)` |
`N/A` |
`O(n)` |
`O(n)` |
`O(n)` |
`O(n)` |

Binary Search Tree | `Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`O(n)` |
`O(n)` |
`O(n)` |
`O(n)` |
`O(n)` |

Cartesian Tree | `N/A` |
`Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`N/A` |
`O(n)` |
`O(n)` |
`O(n)` |
`O(n)` |

B-Tree | `Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(n)` |

Red-Black Tree | `Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(n)` |

Splay Tree | `N/A` |
`Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`N/A` |
`O(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(n)` |

AVL Tree | `Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(n)` |

KD Tree | `Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`Θ(log(n))` |
`O(n)` |
`O(n)` |
`O(n)` |
`O(n)` |
`O(n)` |