In the vast world of computer science and programming, data structures form the backbone of efficient algorithms and well-designed software. While most developers are familiar with common data structures like arrays, linked lists, and binary trees, there are several lesser-known yet powerful data structures that often go overlooked. In this comprehensive guide, we’ll explore these underappreciated gems and discuss why they deserve a place in your programming toolkit.
1. Bloom Filters
Bloom filters are probabilistic data structures used to test whether an element is a member of a set. They’re incredibly space-efficient and offer constant-time add and lookup operations.
How Bloom Filters Work
A Bloom filter consists of a bit array of m bits, initially all set to 0, and k different hash functions. To add an element, feed it to each of the k hash functions to get k array positions. Set the bits at all these positions to 1.
To query for an element, feed it to each of the k hash functions to get k array positions. If any of the bits at these positions is 0, the element is definitely not in the set. If all are 1, then either the element is in the set, or the bits have been set to 1 during the insertion of other elements.
Use Cases
- Spell checkers
- Cache filtering
- Network routers
- Cryptocurrency wallets
Code Example
import mmh3
import math
import array
class BloomFilter:
def __init__(self, size, hash_count):
self.size = size
self.hash_count = hash_count
self.bit_array = array.array('b', [0] * size)
def add(self, item):
for seed in range(self.hash_count):
index = mmh3.hash(item, seed) % self.size
self.bit_array[index] = 1
def check(self, item):
for seed in range(self.hash_count):
index = mmh3.hash(item, seed) % self.size
if self.bit_array[index] == 0:
return False
return True
# Usage
bf = BloomFilter(1000000, 5)
bf.add("hello")
print(bf.check("hello")) # True
print(bf.check("world")) # False2. Skip Lists
Skip lists are a probabilistic alternative to balanced trees. They allow for fast search, insertion, and deletion of elements, with an expected time complexity of O(log n) for these operations.
How Skip Lists Work
A skip list is essentially a series of linked lists stacked on top of each other. The bottom layer contains all elements, and each higher layer acts as an “express lane” for the lists below, allowing for faster traversal.
Use Cases
- Implementing sorted sets in Redis
- File systems
- In-memory databases
Code Example
import random
class Node:
def __init__(self, key, level):
self.key = key
self.forward = [None] * (level + 1)
class SkipList:
def __init__(self, max_level, p):
self.max_level = max_level
self.p = p
self.header = Node(-1, max_level)
self.level = 0
def random_level(self):
lvl = 0
while random.random() < self.p and lvl < self.max_level:
lvl += 1
return lvl
def insert(self, key):
update = [None] * (self.max_level + 1)
current = self.header
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].key < key:
current = current.forward[i]
update[i] = current
level = self.random_level()
if level > self.level:
for i in range(self.level + 1, level + 1):
update[i] = self.header
self.level = level
new_node = Node(key, level)
for i in range(level + 1):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
def search(self, key):
current = self.header
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].key < key:
current = current.forward[i]
current = current.forward[0]
if current and current.key == key:
return current.key
return None
# Usage
sl = SkipList(4, 0.5)
sl.insert(3)
sl.insert(6)
sl.insert(7)
sl.insert(9)
print(sl.search(6)) # 6
print(sl.search(5)) # None3. Trie (Prefix Tree)
A trie, also called a prefix tree, is an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings.
How Tries Work
Each node in the trie represents a common prefix of some keys. All the descendants of a node have a common prefix of the string associated with that node. The root is associated with the empty string.
Use Cases
- Autocomplete and predictive text
- Spell checkers
- IP routing tables
- Solving word games
Code Example
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# Usage
trie = Trie()
trie.insert("apple")
print(trie.search("apple")) # True
print(trie.search("app")) # False
print(trie.starts_with("app")) # True4. Fenwick Tree (Binary Indexed Tree)
A Fenwick tree, also known as a binary indexed tree, is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.
How Fenwick Trees Work
Fenwick trees represent an array of numbers as a tree, where each node stores the sum of a range of elements. The structure of the tree allows for efficient updates and queries in O(log n) time.
Use Cases
- Calculating cumulative frequency
- Range sum queries
- Computational geometry
Code Example
class FenwickTree:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def update(self, i, delta):
while i <= self.size:
self.tree[i] += delta
i += i & (-i)
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i)
return s
def range_sum(self, i, j):
return self.sum(j) - self.sum(i - 1)
# Usage
ft = FenwickTree(10)
ft.update(1, 3)
ft.update(2, 2)
ft.update(3, 5)
print(ft.range_sum(1, 3)) # 105. Segment Tree
A segment tree is a tree data structure used for storing information about intervals, or segments. It allows for efficient querying of cumulative data for a range of array positions, as well as efficient updating of array values.
How Segment Trees Work
The segment tree divides an array into a number of segments and stores them in a tree structure. Each node of the tree represents a segment of the array, with leaf nodes representing individual elements and internal nodes representing larger segments.
Use Cases
- Range minimum/maximum queries
- Range sum queries
- Lazy propagation
Code Example
class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self.build(arr, 0, 0, self.n - 1)
def build(self, arr, node, start, end):
if start == end:
self.tree[node] = arr[start]
else:
mid = (start + end) // 2
self.build(arr, 2 * node + 1, start, mid)
self.build(arr, 2 * node + 2, mid + 1, end)
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
def update(self, index, value):
self._update(0, 0, self.n - 1, index, value)
def _update(self, node, start, end, index, value):
if start == end:
self.tree[node] = value
else:
mid = (start + end) // 2
if start <= index <= mid:
self._update(2 * node + 1, start, mid, index, value)
else:
self._update(2 * node + 2, mid + 1, end, index, value)
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
def query(self, left, right):
return self._query(0, 0, self.n - 1, left, right)
def _query(self, node, start, end, left, right):
if right < start or end < left:
return 0
if left <= start and end <= right:
return self.tree[node]
mid = (start + end) // 2
return (self._query(2 * node + 1, start, mid, left, right) +
self._query(2 * node + 2, mid + 1, end, left, right))
# Usage
arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)
print(st.query(1, 3)) # 15
st.update(2, 6)
print(st.query(1, 3)) # 166. Disjoint Set (Union-Find)
A disjoint-set data structure, also known as a union-find data structure, keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
How Disjoint Sets Work
The data structure provides near-constant-time operations to add new sets, merge existing sets, and determine whether elements are in the same set. It does this by using techniques like “union by rank” and “path compression” to keep the tree balanced and flatten the structure during finds.
Use Cases
- Kruskal’s algorithm for minimum spanning trees
- Finding connected components in graphs
- Image processing
- Network connectivity
Code Example
class DisjointSet:
def __init__(self, vertices):
self.parent = {v: v for v in vertices}
self.rank = {v: 0 for v in vertices}
def find(self, item):
if self.parent[item] != item:
self.parent[item] = self.find(self.parent[item])
return self.parent[item]
def union(self, x, y):
xroot = self.find(x)
yroot = self.find(y)
if self.rank[xroot] < self.rank[yroot]:
self.parent[xroot] = yroot
elif self.rank[xroot] > self.rank[yroot]:
self.parent[yroot] = xroot
else:
self.parent[yroot] = xroot
self.rank[xroot] += 1
# Usage
vertices = ["A", "B", "C", "D", "E"]
ds = DisjointSet(vertices)
ds.union("A", "B")
ds.union("C", "D")
print(ds.find("A") == ds.find("B")) # True
print(ds.find("A") == ds.find("C")) # False7. Van Emde Boas Tree
The van Emde Boas tree (vEB tree) is a tree data structure which implements an associative array with m-bit integer keys. It supports operations such as insert, delete, and find-next in O(log log M) time, where M is the maximum value of a key.
How Van Emde Boas Trees Work
The vEB tree recursively divides the range of possible keys into clusters. Each node in the tree represents a range of integers and contains information about which clusters in its range contain elements.
Use Cases
- IP routing tables
- Priority queues with integer keys
- Implementing other data structures like segment trees
Code Example
import math
class VEBTree:
def __init__(self, universe_size):
self.universe_size = universe_size
self.min = None
self.max = None
if universe_size <= 2:
self.summary = None
self.cluster = None
else:
self.summary = VEBTree(int(math.sqrt(universe_size)))
self.cluster = [VEBTree(int(math.sqrt(universe_size))) for _ in range(int(math.sqrt(universe_size)))]
def high(self, x):
return x // int(math.sqrt(self.universe_size))
def low(self, x):
return x % int(math.sqrt(self.universe_size))
def index(self, x, y):
return x * int(math.sqrt(self.universe_size)) + y
def insert(self, x):
if self.min is None:
self.min = self.max = x
return
if x < self.min:
x, self.min = self.min, x
if self.universe_size > 2:
if self.cluster[self.high(x)].min is None:
self.summary.insert(self.high(x))
self.cluster[self.high(x)].min = self.cluster[self.high(x)].max = self.low(x)
else:
self.cluster[self.high(x)].insert(self.low(x))
if x > self.max:
self.max = x
def member(self, x):
if x == self.min or x == self.max:
return True
elif self.universe_size == 2:
return False
else:
return self.cluster[self.high(x)].member(self.low(x))
def successor(self, x):
if self.min is not None and x < self.min:
return self.min
if self.universe_size == 2:
if x == 0 and self.max == 1:
return 1
else:
return None
if self.cluster[self.high(x)].max is not None and self.low(x) < self.cluster[self.high(x)].max:
offset = self.cluster[self.high(x)].successor(self.low(x))
return self.index(self.high(x), offset)
succ_cluster = self.summary.successor(self.high(x))
if succ_cluster is None:
return None
offset = self.cluster[succ_cluster].min
return self.index(succ_cluster, offset)
# Usage
veb = VEBTree(16)
veb.insert(2)
veb.insert(3)
veb.insert(4)
veb.insert(5)
veb.insert(7)
veb.insert(14)
print(veb.member(4)) # True
print(veb.member(6)) # False
print(veb.successor(5)) # 7
print(veb.successor(14)) # NoneConclusion
While these data structures may not be as commonly used as arrays or hash tables, they offer powerful solutions to specific problems. Understanding these overlooked data structures can significantly enhance your problem-solving skills and algorithm design capabilities.
As you continue your journey in computer science and programming, remember that the right data structure can make all the difference in the efficiency and elegance of your solutions. Don’t shy away from exploring these lesser-known structures – they might just be the key to solving your next challenging problem.
Keep practicing, experimenting, and expanding your knowledge. The world of data structures is vast and fascinating, with each structure offering unique advantages for specific scenarios. By mastering these overlooked data structures, you’ll be better equipped to tackle a wide range of programming challenges and optimize your code for various applications.