1. Introduction to Data Structures and Algorithms Flashcards
data structure
A data structure is a way of organizing, storing, and performing operations on data.
record
A record is the data structure that stores subitems, often called fields, with a name associated with each subitem.
array
An array is a data structure that stores an ordered list of items, where each item is directly accessible by a positional index.
linked list
A linked list is a data structure that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node.
binary tree
A binary tree is a data structure in which each node stores data and has up to two children, known as a left child and a right child.
hash table
A hash table is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array.
max-heap
A max-heap is a tree that maintains the simple property that a node’s key is greater than or equal to the node’s childrens’ keys.
min-heap
A min-heap is a tree that maintains the simple property that a node’s key is less than or equal to the node’s childrens’ keys.
graph
A graph is a data structure for representing connections among items, and consists of vertices connected by edges.
vertex
A vertex represents an item in a graph.
edge
An edge represents a connection between two vertices in a graph.
algorithm
An algorithm describes a sequence of steps to solve a computational problem or perform a calculation.
computational problem
A computational problem specifies an input, a question about the input that can be answered using a computer, and the desired output.
NP-complete
NP-complete problems are a set of problems for which no known efficient algorithm exists.
abstract data type / ADT
An abstract data type (ADT) is a data type described by predefined user operations, such as ‘insert data at rear,’ without indicating how each operation is implemented.
list
A list is an ADT for holding ordered data.
dynamic array
A dynamic array is an ADT for holding ordered data and allowing indexed access.
stack
A stack is an ADT in which items are only inserted on or removed from the top of a stack.
queue
A queue is an ADT in which items are inserted at the end of the queue and removed from the front of the queue.
deque
A deque (pronounced ‘deck’ and short for double-ended queue) is an ADT in which items can be inserted and removed at both the front and back.
bag
A bag is an ADT for storing items in which the order does not matter and duplicate items are allowed.
set
A set is an ADT for a collection of distinct items.
priority queue
A priority queue is a queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority.
dictionary
A dictionary is an ADT that associates (or maps) keys with values.
