Data structures Flashcards
Array
“A set of data items of the same type grouped together using a single identifier. Each of the data items is addressed by the variable name and a subscript.”
Records
“A data structure which consists of a collection of elements, typically in fixed number and sequence and typically indexed by names. The elements of records may also be called fields.”
“The record type is a data type that describes such values and variables. Most modern computer languages allow the programmer to define new record types. The definition includes specifying the data type of each field and an identifier by which it can be accessed.”
Lists
“An abstract data type that represents a sequence of values, where the same value may occur more than once. The name list is also used to cover several concrete data structures that can be used to implement abstract lists especially linked lists.”
Tuple
“Another name for a record”
Linkedlist
“A list where each item contains the data together with a pointer to the next item. There may be an additional pointer to the previous item. This means the items can be accessed in order even if they are not stored in order; they do not have to be stored in adjacent memory locations.”
Directed Graph
“In a directed graph, the order of the vertices in the pairs in the edge set matters.”
Undirected Graph
“In an undirected graph, the order of the vertices in the pairs in the Edge set doesn’t matter.”
Stack
“A stack is a dynamic data structure of the form Last In First Out (LIFO).”
Queue
“A queue is a dynamic data structure of the form First In First Out (FIFO).”
Tree
“A tree is a non-linear dynamic data structure where data items can be thought of as occurring at different levels. There are links between items at one level and their descendants at the next. Each data item has data that relates in some way to its unique parent node. The data items are usually called nodes with the links known as branches. The top level nodes is called the root node.”
Binary Search Tree
“A data structure very similar to a tree with the following additional restrictions. Each node can have only 0, 1 or 2 leaf nodes. All left nodes and all of its descendants have smaller values that the root node, while all right nodes and all of its descendants have larger values than the root node.”
Hash Table
“A data structure where the calculated value is used to mark the position in the table where the data item should be stored, enabling it to be accessed directly, rather than forcing a sequential search.”
