H446 Section 7 Data Structures

Array

A collection of elements identified by index or key, stored in contiguous memory locations. Arrays allow for efficient data organization and access.

Tuple

An ordered collection of elements, typically of different types, that can be indexed but are immutable.

Record

A collection of fields, typically of different data types, that are grouped together to represent a single entity or object. Records are often used in databases to store related information.

String

A sequence of characters used to represent text data, often enclosed in quotes. Strings are commonly used in programming for manipulating and displaying textual information.

Finite

A set with a limited number of elements, often used in the context of data structures to describe collections that are not infinite.

Ordered

A sequence that has a specific arrangement or arrangement of elements, where the position of each element is significant.

Index

A position or location within a data structure, such as an array or list, used to access or manipulate elements based on their order.

1-D Array

A linear data structure consisting of a collection of elements, each identified by at least one array index or key, allowing for efficient storage and retrieval.

2-D Array

A data structure consisting of a collection of elements arranged in rows and columns, where each element can be accessed using two indices.

Immutable

A data structure that cannot be modified after it is created, meaning its elements cannot be changed, added, or removed.

field

A specific area in a data structure that holds a single piece of data or value, often part of a record or entity.

file

A collection of records or data stored in a structured format on a storage device, which can be accessed and managed by software.

Queue

A linear data structure that follows the First In First Out (FIFO) principle, where elements are added at the rear and removed from the front.

Abstract Data Type

A data type defined purely by its behaviour from the point of view of a user, specifying the operations that can be performed on it without revealing its implementation details e.g. a queue, stack, tree or graph, allowing for abstraction and encapsulation.

FIFO

A method of processing data where the first element added is the first one to be removed, commonly used in queues.

enQueue

The operation of adding an element to the rear of a queue.

deQueue

The operation of removing an element from the front of a queue.

isEmpty

A function that checks whether a queue has no elements, returning true if it is empty and false otherwise.

isFull

A function that checks whether a queue has reached its maximum capacity, returning true if it is full and false otherwise.

Dymanic data structure

A data structure that can grow and shrink in size during program execution, allowing for efficient memory usage.

Static data structure

A data structure that has a fixed size, determined at compile time, and cannot change in size during program execution.

Heap

A portion of memory from which space is automatically allocated or de-allocated as needed.

Overflow

A condition that occurs when more data is written to a data structure than it can hold, leading to data loss or corruption.

Circular queue

A linear data structure that follows the FIFO principle but connects the end of the queue back to the front, allowing for efficient use of space.

Priority Queue

A special type of queue that allows elements to be added based on priority rather than just the order they were added. In a priority queue, elements with higher priority are served before those with lower priority.

List

A collection of ordered elements that can be accessed by their index. Lists can be mutable or immutable, allowing for various operations such as insertion, deletion, and traversal.

Append

To add an element to the end of a list or collection, increasing its size.

Pop

To remove and return the last element from a list or collection, typically reducing its size.

Index

The position of an element within a list, used to access or modify the element directly.

Length

The number of elements in a list or collection, indicating its size.

Remove

To delete an element from a list or collection, which may shift subsequent elements.

Linked list

A linear data structure consisting of nodes, where each node contains data and a reference to the next node in the sequence.

Node

An individual component of a linked list containing data and a reference (or pointer) to the next node in the sequence.

Data Field

A component of a node that holds the actual data value. It can vary in type and size depending on the data structure design.

Link

A reference or pointer in a data structure that connects one node to the next in a sequence, allowing traversal through the linked list.

Null pointer

A special type of pointer that does not reference any valid object or node in a data structure, often used to signify the end of a linked list.

Initialisation

The process of preparing a data structure for use by assigning initial values to its fields or allocating memory for its nodes.

Stack

A data structure that follows the Last In First Out (LIFO) principle, where elements are added and removed from the top.

LIFO

An acronym for "Last In, First Out," describing a type of data structure where the last element added is the first one to be removed, commonly used in stacks.

Call Stack

A special type of stack used by a program to keep track of function calls, storing information such as local variables and return addresses.

Return Address

The memory address in the call stack that indicates where to return control after a function call is completed.

Parameters

The values passed to a function that are used within that function to perform operations. These parameters are essential for providing input to functions. They can be required or optional, and may include various data types.

Stack Frame

Each instance of a function call that contains the function's parameters, local variables, and return address. It is created when a function is invoked and destroyed once the function execution is complete. A call stack is composed of stack frames.

Hashing

The process of transforming input data of any size into a fixed-size value or code, which is typically a hash value. Hashing is commonly used in data structures for indexing and quick data retrieval.

Hashing Algorithm

A method used to generate hash values from input data, ensuring that even small changes in input produce significantly different outputs. These algorithms are crucial for data integrity and efficient data retrieval in hash tables.

Hash table

A collection of items stored in such a way that allows for efficient access using a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Synonym

Where the same hash is produced for different inputs, leading to potential data collisions.

Collision

An event that occurs when two different inputs produce the same hash value in a hashing algorithm, potentially compromising data integrity and retrieval.

Folding method

A hash function technique that divides the input data into segments and combines them to produce a single hash value, often used to minimize collisions.

Rehashing

The process of applying a new hash function to existing data in a hash table to resolve collisions or to improve performance. This is often done when the load factor of the hash table exceeds a certain threshold.

Graph

A data structure consisting of nodes connected by edges, used to represent relationships between pairs of objects.

Vertices

The individual nodes in a graph, representing entities or points of interest that are connected by edges.

Edges

The connections or arcs between vertices in a graph, representing the relationships or links between the nodes.

Undirected graph

A type of graph where the edges have no direction, meaning the connection between vertices is bidirectional.

Directed graph

A type of graph where the edges have a direction, indicating a one-way relationship between vertices.

Weighted

A type of graph where edges have associated weights or costs, often used to represent distances or values in a graph.

Adjacency matrix

A way of representing a graph using a 2D array to indicate whether pairs of vertices are adjacent or not, with rows and columns corresponding to vertices.

Adjacency list

A collection of lists or arrays used to represent a graph, where each list corresponds to a vertex and contains a list of its adjacent vertices.

Depth-first traversal

A graph traversal algorithm that explores as far as possible along each branch before backtracking, often implemented using a stack.

Breadth-first traversal

A graph traversal algorithm that explores all the neighbor vertices at the present depth prior to moving on to vertices at the next depth level, often implemented using a queue.

Applications of graphs

Graphs are used in various fields such as computer networks, social network analysis, pathfinding algorithms, roads between towns, tasks in a project, web pages and links.

Tree

A hierarchical data structure consisting of nodes, where each node has a value and a list of references to child nodes, typically used to represent hierarchical relationships.

Rooted tree

A tree in which one node is designated as the root, and all other nodes are descendants of that root, forming a hierarchical structure.

Root

The topmost node of a tree data structure, from which all other nodes descend. It serves as the starting point for traversing the tree.

Parent

A node in a tree that has one or more child nodes, establishing a direct hierarchical relationship.

Child

A node that is a direct descendant of another node in a tree structure. Each node can have multiple children, contributing to the tree's hierarchical organization.

Leaf

A node in a tree data structure that has no children, representing the end of a path in the hierarchy.

Subtree

A tree consisting of a node and all its descendants, representing a smaller tree structure within a larger tree.

Binary tree

A tree data structure where each node has at most two children, typically referred to as the left and right child.

Binary Search tree

A binary tree in which each node's left subtree contains only nodes with values less than the node's value, and the right subtree only nodes with values greater.

Pre-order traversal

A type of depth-first tree traversal where the nodes are processed in the order of root, left subtree, and then right subtree.

In-order traversal

A method of visiting all the nodes in a binary tree where the nodes are recursively visited in the order of left child, then the node itself, and finally the right child.

Post-order traversal

A type of depth-first tree traversal where the nodes are processed in the order of left subtree, right subtree, and then root.

Reverse Polish Notation

A mathematical notation in which every operator follows all of its operands, allowing for unambiguous expression evaluation without the need for parentheses.