1.4.2 Data structures - Nathan

An array is a data structure that holds a number of elements of the same data type

Array indexes start at ‘0’. (at least, in most programming languages such as Python) ADDITIONAL EXPLANATION: So in the following array: [“toast”, “eggs”, “ketchup”] The ‘0th’ element is “toast”, the ‘1st’ element is “eggs” and the ‘2nd’ element is “ketchup”

The contents of arrays are stored contiguously in memory (meaning one after another). This means that the position of each element of the array can be computer from the array’s base address.

The contents of an array are mutable - so they can be changed while the program is running

One dimensional array: an array containing data types such as integers, strings, etc Two dimensional array: an array containing arrays: e.g: my2dArray = [[1, 65, 3, 2], [62, 7, 1, 6], [6, 3, 76, 2]] Where the first element of this array is, [1, 65, 3, 2]

A record is a data structure containing a fixed number of variables, called fields. Each field has an identifier (a name) and a data type. Each field can have a different data type. PSEUDOCODE EXAMPLE: PlayerRecord = RECORD player_number: Integer first_name: String last_name: String date_of_birth: Date position: String injured: Boolean ENDRECORD

A list is an abstract data type. It describes a linear collection of data items in an order.

create - create a new list add - add a new element to the list delete - delete an element from the list traverse - visit the elements in the list one at a time

A tuple is an ordered sequence of of immutable elements (meaning the elements can’t be changed while the program is running).

No, the elements of a tuple can all be different data types - e.g a mix of integers and strings

A linked list is a dynamic data structure - where each node points to the next one, forming a sequence with a start and end.

Because a linked list is dynamic, it’s size can be changed at runtime.

Nodes in a linked list contain the data relating to the element, and a pointer to the next node.

A graph is an abstract data type that can be used to represent complex, non-linear relationships between objects. They can be undirected, or directed (contain arrows).

A stack is an abstract data type that holds an ordered, linear sequence of items. It is LIFO (last-in-first-out), similar to a stack of plates.

Push() - add element to top of stack Pop() - remove element from top of stack Peek() - return copy of element on top of stack (without removing it) is_empty() - check whether the stack is empty is_full() - check whether stack is at maximum capacity (if stored in a static (fixed-size) structure)

One application of a stack is maintaining an ‘undo’ list

A queue is an abstract data type that holds an ordered, linear sequence of items. It is FIFO (first-in-first-out), similar to a queue of people at a cafe.

enqueue(data) - add element to queue dequeue() - return an element from front of queue & remove it is_empty() - check whether the stack is empty is_full() - check whether stack is at maximum capacity (if the size of the queue is constrained)

Queues can be used for queuing up print tasks, or for simulations (e.g traffic or shopping simulations)

A tree is a type of graph that’s undirected, and doesn’t contain cycles

A binary tree is a tree where each node has at most 2 children

• Syntax trees in compilers • Used to represent boolean expressions to simplify them

A hash table is a type of data structure in which information is stored in an easy-to-retrieve and efficient manner, using key-value pairs