1.4.2 Data Structures Flashcards
What is an array?
A finite set of ordered elements of the same data type.
What is a tuple?
An ordered set of elements of any data type. It is immutable meaning it cannot be changed.
What is a list?
A set of ordered items of any type which can appear more than once. Stored non-contiguously.
What is a linked list?
A dynamic data structure used to hold an ordered sequence. Each item contains an index, a data field, and a pointer to the next index.
What is a graph? How can they be processed?
A set of nodes connected by edges.
Adjacency matrix or adjacency list.
What is an adjacency matrix? What are its advantages?
A table containing all of the possible connections in a graph.
Advantages => Easy to add nodes, quick access times.
What is an adjacency list? What are its advantages?
A list that contains all of the links between nodes.
Advantages => More space efficient for larger graphs.
What is a stack? Examples?
A First In Last Out / Last In First Out data structure.
E.g. Undo operation.
What is a tree?
A connected form of graph. Binary trees have a maximum of 2 children and can be used for binary searches.
What is a queue? Examples?
A First In First Out data structure.
E.g. printers, keyboards.
What is a hash?
A result generated by applying an algorithm to a value.
What is a hash table?
An array used with a hash function, which determines the index of the array to use.
A good hash function should have a low probability of collisions.
