Data Structures

data structure

a common format for storing large volumes of related data, which is an implementation of an abstract data type in a particular programming language

abstract data type

a conceptual model of how data can be stored and the operations that can be carried out on the data

array

a finite set of related elements of the same data type, where each element can be individually indexed and accessed based on its position

static data structure

a method of storing data where the amount of data stored, and the memory used to store it, is fixed

dynamic data structure

a method of storing data where the amount of data stored, and the memory used to store it, will vary as the program is being run

advantages of static data structures

• fast accessing because memory location is fixed when the program is written and memory addresses are contiguous

• more predictable to work with

• easier to program because no need to worry about size-checking or memory overflow

advantages of dynamic data structures

• efficient memory usage because they only allocates the memory they actually need, minimising memory wastage

• flexible because they can grow or shrink as needed, accommodating changes in data volume

disadvantages of static data structures

• can waste memory if the number of data items stored is small relative to the size of the structure

• if allocated memory is too small, it can lead to overflow errors

• require more complex operations to insert or delete elements

disadvantages of dynamic data structures

• slower accessing because memory location is allocated at run-time and memory addresses may be fragmented

• require a mechanism to know the size of the current structure

• performance is less predictable

adjacecy list

a data structure that stores a list of nodes with their adjacent nodes

adjacency matrix

a data structure set up as a two-dimensional array or grid that shows whether there is an edge between each pair of nodes

advantages of adjacency lists

• only store the connections that actually exist, making them highly efficient for sparse graphs

• easy to implement

advantages of adjacency matrices

• adjacencies can be identified more quickly as every combination is already stored- forms a look-up table of each node to every other node

• adding or removing edges can be done in constant time

disadvantages of adjacency lists

• adding or removing a vertex can be time-consuming- you need to update all the adjacency lists to reflect the change

• list has to be parsed to identify whether particular adjacencies exist, which increases time taken to process the data

disadvantage of adjacency matrices

• significant amount of memory is wasted storing connections that don't exist in a sparse graph

when is an adjacency list more suitable

• sparse graph

• when edges are rarely changed

• when presence/absence of specific edges does not need to be tested frequently

features of trees

• root node

• no cycles

hash table

a data structure that stores key/value pairs based on an index calculated from an algorithm

hashing algorithm

code that computes an address within a specified range from the key

collision

when a hashing algorithm produces the same index for two or more different keys

clustering

when a hashing algorithm produces indices that are not randomly distributed

load factor

number of keys / number of slots

chaining

a technique for generating a unique index when there is a collision by adding the key/value to a list stored at the same index

rehashing

• when a hash table becomes too full or collisions become too frequent

• new, larger hash table created (typically double the size)

• the existing elements from the old hash table are re-hashed and placed into the new, larger table

representations of vectors

• values stored in a list

• functions

• arrows

convex combination

a way to blend two or more vectors together so that the result stays between them/ within the convex hull

convex hull

a spatial representation of the vector space between two vectors

C = x*A + y*B

• x and y must be greater than or equal to 0

• x + y must equal 1