Data Structures Flashcards
(15 cards)
arrays definition
a data structure for storing a finite, ordered set of data of the same data type within a single identifier
binary search tree definition
a tree where each node cannot have more than 2 children
the right node and its descendants always have a greater value than the root node (first data item)
breadth first traversal definition
a method of traversing an entire graph by visiting all the neighbours of the first node before repeating the same with each neighbour in the order they were visited
depth first traversal definition
a method of traversing an entire graph by travelling as far as far as possible along one route before backtracking and trying alternative unexplored routes
directed graphs definition
a graph where the order of the vertices are paired in an edge matter
the edges are one way
graphs definition
a data structure consisting of a set of vertices/nodes connected by a set of edges/arcs
hash table definition
a data structure where a hashing algorithm calculates a value to determine where a data item is to be stored
the data item can then be directly accessed by recalculation, without any search
linked lists definition
a data structure that stores an ordered sequence of data where each item is stored with a pointer to the next item
the items are not stored contiguously (in the same order) in memory
lists definition
a data structure that stores a sequence of data values, each with a unique index
queues definition
a first-in-first-out (FIFO) data structure
the first item added/pushed on to the queue is the first to be removed/popped off
records definition
a data structure that stores data in elements called fields, organised based on attributes
stacks definition
a last-in-first-our (LIFO) data structure
the last item added/pushed is the first to be removed/popped off
trees definition
a data structure that uses a set of linked nodes to form a hierarchical structure starting at a root node
each node is a child/sub-node of a parent node
tuples definition
a data structure for storing an immutable (cannot be modified once created), ordered set of data, which can be different data types, within a single identifier
undirected graphs definition
a graph where the order of the vertices paired in an edge does not matter
the edges are bidirectional
