Component 13 - Key Definitions Flashcards
Arrays (of up to 3 dimensions), records, lists, tuples
Arrays: A data structure which acts like a table. Each “row” is accessed via an indexing system, usually zero based. Arrays are fixed size and hold multiple values of the same data type and cannot hold values of differing types.
Record: A custom data structure which holds values of differing data types. For example a record “person” may contain fields such as “name”, “age”, “height” and so forth. Variables can then be declared as type “person” and the fields accessed through the object.property method
Lists: A dynamic data structure which can grow and shrink with the requirements of the program. Each node in a list holds a piece of data and a pointer to the next piece of data in the list.
Tuples: A strange data type which holds a collection of data, usually ordered and it cannot be changed. Accessed in much the same way as an array
The following structures to store data: linked-list, graph (directed and undirected), stack, queue, tree, binary search tree, hash table
Linked list: a data structure consisting of nodes. Each node is a pair of “data” and “link” entities. The link points to the next node in the list. By manipulating the links we can grow, shrink, re-arrange and otherwise manipulate the data stored within. Dynamic.
Graph: A data structure similar in nature to a linked list in that it consists of connected nodes. However, in a graph each node can be connected to multiple other nodes.
Stack: A FILO (First in, last out) data structure which is used in countless computing applications. Data is either “pushed” on to the stack or “popped” off it. Elements cannot be accessed at random and must be stored and retrieved one at a time. Often used in programming (call stacks), operating systems, interrupts and so forth. Queue: A First in, First Out (FIFO) data structure. Elements in the queue are removed in the order they were added.
Tree: A data structure consisting of nodes. Each node contains data and a number of pointers. The tree is organised in a “root” and “leaf” structure. There is one root node at the top of the tree, this may have zero or more “leaf” nodes coming off it. In turn, those leaf nodes may be connected to layers below. The only difference between a tree and binary tree is that a binary tree node may only have a maximum of two child nodes.
Hash Table: Basically a table of pointers to data. Each row of the table is accessed by hashing the input to discover the row to be accessed.
How to create, traverse, add data to and remove data from the data structures mentioned above. (NB this can be either using arrays and procedural programming or an object-oriented approach).
See lesson
