4.2 Fundamentals of Data Structures Flashcards
Difference between binary and text files
All files can be categorized into one of two file formats — binary or text. The two file types may look the same on the surface, but they encode data differently. While both binary and text files contain data stored as a series of bits (binary values of 1s and 0s), the bits in text files represent characters, while the bits in binary files represent custom data.
Abstract Data Type
An abstract data type is a data structure whose properties are specified independently of any particular programming language. ADTs have not only properties/values, but also have functions and procedures to interface
with.
- Queue
- Stack
- Graph
- Tree
- Hash table
- Dictionary
- Vector
Static vs Dynamic Data Structures
In static data structures the size of the structure is fixed. The content of the data structure can be modified but only without changing the memory space allocated to it. An example of static data structure is an array.
In dynamic data structures the size of the structure in not fixed and can be modified during the operations performed on it. Dynamic data structures are designed to facilitate change of data structures in the run time. An example of a Dynamic Data Structure is a Linked List.
Static data structures provide easier access to elements compared to dynamic data structures. However, unlike static data structures, dynamic data structures are flexible and can adjust dynamically to accommodate the changing
needs for the amount of memory required at run time.
Linear Queues
A queue is a first-in first-out (FIFO) abstract data type. Uses for queues involve
anything where events must happen in the order that they were called/added.
Examples of common queue uses in an operating software include keyboard
buffers and print queues.
Circular Queues
Unlike linear queues, circular queues allow for memory to be re-used in a more
efficient manner when dequeue events have taken place.
Benefits
* They reuse memory space, meaning they won’t overwrite data or run out of
memory (within limits)
Drawbacks
* Involve storing pointers as well as data, taking up more space than linear queues
* Limited by the amount of data available in the array
Priority Queues
A real-world example of this would be an Accident and Emergency Department waiting room. Someone who had broken an arm would be a lower priority to someone who is having a stroke.
What is a stack?
A stack is a container of objects that are inserted and removed according to the
last-in first-out (LIFO) principle.
Uses of a stack
- Return values for recursive procedures
- The syntax check on a computer for matching braces.
- ‘Undo’ mechanisms in software.
Graph Definition
A Graph is a diagram consisting of end points, called vertices that are joined by lines, called edges.
A labelled graph is a graph in which the vertices are labelled (i.e. consist of a number or word).
A weighted graph consists of edges which have a value (usually a number)
A directed graph consists of vertices that are joined by directed edges (edges that only travel in a single direction).
A graph is said to contain a cycle where a vertex has an edge which connects to itself.
The degree of a vertex is the number of end segments of edges that “stick out of” the vertex.
The neighbours of a vertex is the count of all connected vertices to the stated vertex.
Uses of Graphs
Telephone, electric power, gas pipeline, and air transport systems can all be represented by graphs
What is a tree
A tree is a connected, undirected graph with no cycles. Trees often have a root; however, they do not have to have one.
Data is added to the tree in the order it is encountered.
Binary tree
A binary tree is a rooted tree in which each node has at most two children. A common application of a binary tree is as a binary search tree. Binary trees a dynamic data structure and allows for efficient sorting, searching and retrieval of data.
Hashing algorithms
Hashing algorithms take a large range of values (such as all possible strings or all possible files) and map them onto a
smaller set of fixed sized values (such as a 128-bit number).
Sometimes these may be called digests or simply a hash.
Hashing is the process of applying a hashing algorithm to a hashing key to create a hash value.
* Hashing Algorithm (Example: SHA-256)
* Hashing Key: The data item to hash
* Hashing Value: The output from the hashing algorithm.
Hash tables
A hash table is a data structure that creates a mapping between keys and values. A Hash table combines the benefits
of an array with the benefits of a linked list by using a hash function. The hash function will always output the same
value for any given key.
Collisions in hash tables
A collision occurs when two key values compute the same hash.
There are two ways to resolve a collision. Closed Hashing which uses the next available location and Open Hashing
which uses the linked list method of resolving the collision.
Closed Hashing is simple to implement but can result in a problem of clustering, which increases the chance of
further collisions. Ideally a hash function should be created that minimises collisions but that is not always possible.
Open hashing works slightly better, as it means when a collision happens, the collided items are simply added to a
linked list and the value returned by a key becomes a pointer to the first item in a linked list containing all the values
which would be stored at that key location.
