Data Structure topics

LogLog (Probabilistic Data Structure for Cardinality)

LogLog is a Probabilistic Data Structure that uses the idea of hashing to compute Cardinality of a given set.

MinHash (Probabilistic Data Structure for Similarity)

MinHash was originally an algorithm to quickly estimate the jaccard similarity between two sets but can be designed as a probabilistic data structure that quickly estimates how similar two sets are.

Data Structures

Probabilistic Data Structures

This is a general overview of probabilistic data structures (with examples of data structures over 5 different categories).

Data Structures

Count Min Sketch

A count min sketch data structure is a probabilistic data structure (a data structure that provides an approximate solution) that keeps track of frequency.

Data Structures

Radix Tree [Compact version of Trie]

radix tree is a compact version of a trie. It takes advantage of this and will store multiple characters / string of text in an edge instead to reduce the number of extra edges and nodes needed.

Data Structures

Two Stack Model / Split Buffer for Text Editors

In two stack model, one stack will represent all the contents left of the cursor while the other stack will represent all the contents right of the cursor. Similar is the idea behind Split buffer.

Data Structures

Data Structures used in Text Editors

A text editor uses a wide range of data structures to implement different features like search, replacing text and much more. These include char buffer, gap buffer, two stack model, doubly linked list and much more.

Algorithms

Reverse a doubly linked list in C++

In this article, we are going to see how to reverse a doubly linked list by reversing the links of each node (without swapping values of nodes) and have implemented the solution using C++.

Algorithms

To check if the linked list is a circular linked list (2 methods)

We will be seeing two efficient methods to determine whether the given linked list is a circular linked list or not. With this, we solve the problem in linear time.

Algorithms

Cycle Detection Algorithms

A cycle in a data structure as we have already seen is a condition with no end. A few popular cycle detection algorithms are Floyd's cycle detection algorithm and Brent’s Cycle Detection Algorithm.

Data Structures

Finding the length of a loop in linked list

In this article, we will look at the method of finding the length of a loop in a linked list. For that you should be able to understand Floyd's loop detection algorithm.

Data Structures

Detect a loop in a linked list (3 methods)

A Loop in a linked list is a condition when a Linked list does not have any end. We have explored different ways to detect loop in a linked list like by marking visited nodes, using hashmap and Floyd's cycle finding algorithm.

Data Structures

Different Self Balancing Binary Trees

A self-balancing binary tree is any tree that automatically keeps its height small in the face of arbitrary insertions and deletions on the tree. We have explored different types like 2 3 tree, Red Black tree, AVL Tree, B Tree, AA Tree, Scapegoat Tree, Splay Tree, Treap and Weight Balanced Tree.

Data Structures

Introduction to 2-3 Trees

A 2-3 Tree is a tree data structure where every node with children has either two children and one data element or three children and two data elements. A node with 2 children is called a 2-NODE and a node with 3 children is called a 3-NODE.

Software Engineering

Implementing a Binary Search Tree (BST) in C++

In this article, we have explained the idea of implementing Binary Search Tree (BST) from scratch in C++ including all basic operations like insertion, deletion and traversal.

Data Structures

Sort a stack using another stack

In this article, we have explored an algorithm to sort a stack using another stack that is by using stack operations like push and pop only. The time complexity of this approach is O(N^2) and space complexity is O(N).

Algorithms

Hashed Array Tree: Efficient representation of Array

Hashed Array Tree is an improvement over Dynamic Arrays where there can be a large amount of unused allocated memory at a time. This can be visualized as a 2 dimensional array and has been developed by Robert Sedgewick, Erik Demaine and others.

Algorithms

Reverse alternate groups of K nodes in a Singly Linked List

We are given a pointer to the head of a singly Linked List and you have to write a function to reverse the elements of the given singly Linked List in alternate groups of K nodes. Once the operation is performed, pointer to the head of the Linked List must be returned from the function.

Data Structures

Introduction to AA trees

AA trees were introduced by Arne Andersson in 1993 and hence the name AA. They are a type of balanced binary search trees. It was developed as a simpler alternative to Red Black trees.

Data Structures

Implementing Binary tree in C++

In this article, we have explored how to implement Binary Tree Data Structure in C++ including all different operations like traversing, inserting and deleting. We have used Object Oriented Programming (OOP) concepts.

Algorithms

Reverse a linked list using 2 pointers technique using XOR operator

You must have come across reversing a linked list using 3 pointers technique which is the most common approach to do it. But do you know how to reverse a linked list with just 2 pointers? This article will teach you just that! Let's dive into it.

Data Structures

Circular Linked List

Circular Linked list is a complex form of a linked list data structure as within a circular linked list the last node points to the first node of the list. We have covered it in detail with all operations and implementation in Java.

Data Structures

Applications of Queue

We have covered all applications of queue. Some of the algorithms were it is used are CPU Scheduling (First-Come-First-Serve), Breadth First Search Traversal, Level Order Traversal of a tree, Edmonds Karp Algorithm, Dinic's Algorithm and Fibonacci Heap. We have explored some of the problems as well.

Data Structures

Types of Queue and their implementations

Queue is a FIFO (first in first out) data structure. The different types of queues are linear queue, circular queue, priority queue and deque. We have explored the types along with implementations.

Data Structures

Dynamic Stack

Dynamic Stack, just like Dynamic Array, is a stack data structure whose the length or capacity (maximum number of elements that can be stored) increases or decreases in real time based on the operations (like insertion or deletion) performed on it.