1.4.2 Data Structures

An ordered finite set of elements of a single data type. A 1D array is an linear array always zero indexed A 2D array can be like a table or spreadsheet you go up and down the toes then across the columns to find a given position A 3D array can be a visualised as multiple 2D arrays example : print(array[x,y,z]) where x = the array number , y = row , z= column

A row in a file, made up of values from fields the variable must be declared

A data structure consisting of ordered items where items can occur more than once. They can contain multiple data types.

Similar to 1D array in his they can be access, however values stored non contagiously meaning they don’t need to be next to eachother In memory

IsEmpty() Append(value) Remove(value) Search(value) Length() Index(value) Insert(pos,value) Pop() Pop(pos)

An ordered set of values of any types. It’s immutable which means cannot be changed elements can’t be added or removed once it’s created. Attempting to add or remove will cause an error

Last in first out (LIFO) data structure. Used as a undo / reverse action

Static or dynamic If max size required is known in advance use static as it’s easier to implement and make more efficient use of memory.

Using a pointer which check top of the stack where next piece of data will be inserted

IsEmpty() Push(value) - adds a new value to end of list need to check list is not full Peek() - returns top value make sure stack isn’t empty Pop() same as peek but removed value Size() IsFull()

First in first out (FIFO) data structure

Printers linear queue consisting of an array

Items added to the next available Space starting from the front. Items are removed from the front. Used two pointers one at front and one at back.

As items are removed address cannot be reused in efficient use of space

Circular queues. When the rear pointer = max size of the array it can be looped around to the front of the array uses space more efficiently but harder to implement Only works if front of queue is empty

EnQueue() - Adds new item to end of queue. Incriminating back pointer by one DeQueue() - removes item from front of the queue incrementing front pointer by one IsEmpty () IsFull()

Dynamic data structure uses to hold an ordered Sequence. Don’t have to be in contiguous data location. Each item is a node containing data field along side a link or pointer

Table with index data and pointer Data field contains value of actual data Pointer field contains the address of the next item in the list

The start or the first item in the list and also next free stores the index of the next available pos

1) add the new value to end of linked list and update “next free “ pointer 2) pointer field of previous last value is updated to point to the new value 3) the pointer field of the new value is updated

Update the pointer so previous pointer is not pointing to empty node

Values can be easily added or removed by editing pointer

1) nodes is not truly removed from list but just ignored this is a waste of memory 2) as items stored in sequence cannot be individually access like an array 3) more space then an array as needs to store pointers asw

A set of vertices connected edges / arcs Directed - can only be traveled in one direction Undirected Weighted - cost attached to each edge Can be used to find the shortest path and are easy way to understand complex data