Enhance Your Learning with Data Structures Flash Cards for quick learning
A data structure that stores a fixed-size sequential collection of elements of the same type.
A data structure that consists of a sequence of nodes, where each node contains a reference to the next node in the sequence.
A data structure that follows the Last-In-First-Out (LIFO) principle, where the last element added is the first one to be removed.
A data structure that follows the First-In-First-Out (FIFO) principle, where the first element added is the first one to be removed.
A hierarchical data structure that consists of nodes connected by edges, with a single node called the root.
A non-linear data structure that consists of a finite set of vertices (nodes) and a set of edges connecting these vertices.
A data structure that implements an associative array abstract data type, where keys are mapped to values using a hash function.
A complete binary tree data structure that satisfies the heap property, where the value of each node is greater than or equal to the values of its children.
Algorithms that arrange elements in a specific order, such as ascending or descending, based on comparison or non-comparison operations.
Algorithms that locate specific elements within a data structure, such as finding the position of a target value or determining if it exists.
A dynamic array implementation that allows for the efficient addition and removal of elements at the end of the array.
A linked list where each node contains references to both the previous and next nodes in the sequence.
A linked list where the last node points back to the first node, creating a circular structure.
Common operations on a stack include push (add an element), pop (remove the top element), and peek (retrieve the top element without removing it).
Common operations on a queue include enqueue (add an element to the rear), dequeue (remove the front element), and peek (retrieve the front element without removing it).
A tree data structure where each node has at most two children, referred to as the left child and the right child.
A binary tree where the value of each node is greater than all values in its left subtree and less than all values in its right subtree.
The process of visiting all the vertices of a graph in a specific order, such as depth-first search (DFS) or breadth-first search (BFS).
A function that takes an input (or key) and returns a fixed-size value (or hash code) that represents the input.
The process of handling situations where two or more keys map to the same index in a hash table, such as using separate chaining or open addressing.
A heap where the value of each node is less than or equal to the values of its children, ensuring the minimum value is always at the root.
A heap where the value of each node is greater than or equal to the values of its children, ensuring the maximum value is always at the root.
A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
A simple sorting algorithm that divides the input list into a sorted and an unsorted region, repeatedly finding the minimum element from the unsorted region and swapping it with the first element of the unsorted region.
A simple sorting algorithm that builds the final sorted array one item at a time, inserting each item into its correct position within the sorted portion of the array.
A divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves into a single sorted array.
A divide-and-conquer sorting algorithm that selects a pivot element, partitions the array around the pivot, and recursively sorts the sub-arrays on either side of the pivot.
A simple searching algorithm that sequentially checks each element of a list until a match is found or the end of the list is reached.
An efficient searching algorithm that works on sorted arrays by repeatedly dividing the search interval in half until the target element is found or determined to be absent.
A graph traversal algorithm that explores all the vertices of a graph in breadth-first order, visiting all the neighbors of a vertex before moving to the next level.
A graph traversal algorithm that explores all the vertices of a graph in depth-first order, visiting as far as possible along each branch before backtracking.
Common operations on an array include accessing elements by index, inserting elements at a specific position, and removing elements from a specific position.
Common operations on a linked list include inserting a node at the beginning or end, deleting a node, and searching for a specific value.
Stacks are used in applications such as expression evaluation, function call management, and backtracking algorithms.
Queues are used in applications such as scheduling processes, handling requests, and breadth-first search algorithms.
The process of visiting all the nodes of a tree in a specific order, such as pre-order, in-order, or post-order traversal.
Graphs can be represented using adjacency matrix or adjacency list data structures, each with its own advantages and disadvantages.
Collision handling techniques include separate chaining (using linked lists) or open addressing (using linear probing, quadratic probing, or double hashing).
Common operations on a heap include inserting an element, deleting the minimum or maximum element, and extracting the minimum or maximum element without deleting it.
Sorting algorithms have different time and space complexities, such as O(n^2) for bubble sort and O(n log n) for merge sort or quick sort.
Searching algorithms have different time complexities, such as O(n) for linear search and O(log n) for binary search on a sorted array.
Common operations on an array list include adding an element, removing an element, and accessing an element by index.
Common operations on a doubly linked list include inserting a node, deleting a node, and reversing the list.
Common operations on a circular linked list include inserting a node, deleting a node, and traversing the list in a circular manner.
Binary trees can be traversed in pre-order, in-order, post-order, or level-order (breadth-first) traversal.
Common operations on a binary search tree include insertion, deletion, and searching for a specific value.
Graphs can be traversed using depth-first search (DFS) or breadth-first search (BFS) algorithms to visit all the vertices.
The load factor of a hash table is the ratio of the number of elements stored to the size of the hash table, affecting its performance and efficiency.
The process of converting an array into a heap, rearranging its elements to satisfy the heap property.
Stable sorting algorithms preserve the relative order of equal elements, while unstable sorting algorithms may change the order of equal elements.
Binary search trees can be traversed in-order, pre-order, or post-order to visit all the nodes in a specific order.
Graphs can be represented using adjacency matrix, adjacency list, or edge list data structures, depending on the specific requirements.
When the load factor of a hash table exceeds a certain threshold, it needs to be resized to maintain a balanced distribution of elements.
A comparison-based sorting algorithm that uses a binary heap data structure to sort elements in ascending or descending order.
The time complexity of common operations on a binary search tree depends on the height of the tree, which can range from O(log n) to O(n) in the worst case.
Cycle detection algorithms can determine whether a graph contains cycles, which are loops in the graph that can cause infinite traversal.
The time complexity of collision resolution techniques in a hash table depends on the specific technique used, such as O(1) for separate chaining or O(n) for linear probing.
The time complexity of common operations on a heap depends on the height of the heap, which can range from O(log n) to O(n) in the worst case.
A sorting algorithm is stable if it preserves the relative order of equal elements, ensuring that elements with the same key appear in the same order in the sorted output as they did in the input.
A balanced binary search tree has a height that is logarithmic in the number of elements, ensuring efficient search, insertion, and deletion operations.
Topological sorting is the process of arranging the vertices of a directed acyclic graph (DAG) in a linear order that respects the partial order of the edges.
The load factor threshold of a hash table determines when it needs to be resized to maintain a balanced distribution of elements, typically around 0.75.
The time complexity of the heapify operation, which converts an array into a heap, is O(n) in the worst case.
A minimum spanning tree (MST) of a connected, undirected graph is a tree that spans all the vertices with the minimum possible total edge weight.
Collision resolution techniques in a hash table include separate chaining, linear probing, quadratic probing, and double hashing, each with its own advantages and disadvantages.
The time complexity of heap sort, a comparison-based sorting algorithm, is O(n log n) in the worst case.
The shortest path problem is the task of finding the shortest path between two vertices in a weighted graph, where the path length is the sum of the weights of its edges.
Rehashing is the process of resizing a hash table and reinserting all the elements to maintain a balanced distribution when the load factor exceeds a certain threshold.
The maximum flow problem is the task of finding the maximum amount of flow that can be sent from a source vertex to a sink vertex in a flow network.
Heaps are used in applications such as priority queues, event-driven simulations, and graph algorithms like Dijkstra's algorithm.
Most sorting algorithms are comparison-based, meaning they determine the order of elements by comparing them using a specific comparison operator.
Algorithms for finding the minimum spanning tree of a graph include Prim's algorithm and Kruskal's algorithm, each with its own approach and time complexity.
When the load factor of a hash table exceeds a certain threshold, it needs to be resized to maintain a balanced distribution of elements, typically by doubling its size.
Algorithms for finding the shortest path in a graph include Dijkstra's algorithm, Bellman-Ford algorithm, and Floyd-Warshall algorithm, each with its own approach and time complexity.
The time complexity of collision resolution techniques in a hash table depends on the specific technique used, such as O(1) for separate chaining or O(n) for linear probing.
Heap sort is an unstable sorting algorithm, meaning it may change the relative order of equal elements during the sorting process.
Algorithms for finding the maximum flow in a flow network include Ford-Fulkerson algorithm, Edmonds-Karp algorithm, and Dinic's algorithm, each with its own approach and time complexity.
An in-place sorting algorithm is one that does not require any additional memory beyond the input array, sorting the elements within the array itself.
A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other set.
The time complexity of resizing a hash table and rehashing all the elements to maintain a balanced distribution is O(n), where n is the number of elements in the hash table.
Algorithms for topological sorting of a directed acyclic graph (DAG) include depth-first search (DFS) and Kahn's algorithm, each with its own approach and time complexity.
An Eulerian path is a path in a graph that visits every edge exactly once, while an Eulerian cycle is an Eulerian path that starts and ends at the same vertex.
The time complexity of rehashing a hash table, which involves resizing the table and reinserting all the elements, is O(n), where n is the number of elements in the hash table.
Strongly connected components (SCCs) of a directed graph are subgraphs in which there is a directed path between any two vertices.
A minimum cut of a graph is a cut (partition) of the vertices into two disjoint sets such that the sum of the weights of the edges crossing the cut is minimized.
A planar graph is a graph that can be drawn on a plane without any edges crossing, while a non-planar graph cannot be drawn without edge crossings.
A Hamiltonian cycle is a cycle in a graph that visits every vertex exactly once, while a Hamiltonian path visits every vertex but may not form a cycle.
Graph coloring is the assignment of labels (colors) to the vertices of a graph such that no two adjacent vertices have the same color.
The travelling salesman problem (TSP) is the task of finding the shortest possible route that visits each city in a given list exactly once and returns to the starting city.
The time complexity of finding the minimum spanning tree of a graph depends on the specific algorithm used, such as O(E log V) for Prim's algorithm or Kruskal's algorithm.
The time complexity of finding the shortest path in a graph depends on the specific algorithm used, such as O(E + V log V) for Dijkstra's algorithm or O(VE) for Bellman-Ford algorithm.
The time complexity of finding the maximum flow in a flow network depends on the specific algorithm used, such as O(EV^2) for Ford-Fulkerson algorithm or O(V^2E) for Edmonds-Karp algorithm.
The time complexity of topological sorting of a directed acyclic graph (DAG) depends on the specific algorithm used, such as O(V + E) for depth-first search (DFS) or O(V + E) for Kahn's algorithm.
The time complexity of finding an Eulerian path or cycle in a graph depends on the specific algorithm used, such as O(E) for Fleury's algorithm or Hierholzer's algorithm.
The time complexity of finding strongly connected components (SCCs) in a directed graph depends on the specific algorithm used, such as O(V + E) for Tarjan's algorithm or Kosaraju's algorithm.
The time complexity of finding a minimum cut of a graph depends on the specific algorithm used, such as O(V^3) for Stoer-Wagner algorithm or O(V^2E) for Karger's algorithm.
The time complexity of testing the planarity of a graph depends on the specific algorithm used, such as O(V + E) for Boyer-Myrvold algorithm or O(V^3) for Hopcroft-Tarjan algorithm.
The time complexity of finding a Hamiltonian cycle or path in a graph depends on the specific algorithm used, such as O(2^N * N^2) for backtracking or O(N!) for brute force.
The time complexity of graph coloring depends on the specific algorithm used, such as O(N^2) for greedy coloring or O(2^N) for backtracking.
The time complexity of solving the travelling salesman problem (TSP) depends on the specific algorithm used, such as O(N^2 * 2^N) for dynamic programming or O(N!) for brute force.