Data-Structures

Let’s consider a Linked List that we’ve seen so far for the problem of storing and retrieving information. In particular, let’s implement a set using an ordered linked list as the underlying data structure. Here’s how that would look like: From the get-go we can see that searching and inserting would be slow for this implementation. Say we want to check if node E exists in the list or not. We’ll start searching at the begining of the list, perform a check to see if a node matches the key we’re searching for, and if not, move on to the next node in the list. This will lead to O(N) time complexity for search, which is definitely not good. ...

Disjoint sets are used to solve a problem called dynamic connectivity. This data structure has two operations: connect(x, y): connects x and y isConnected(x, y): returns true if x and y are connected. Connections don’t need to be direct (transitive) Note: The ideas and content (including images) in this post come from Josh Hug’s excellent lectures from UC Berkeley’s CS61B. Introduction Let’s consider an example. We start with a set of 7 integers from 0 to 6 connected as follows: ...