1.4 Data types, structures and algorithms

Allows the right operations to be performed on it

Single symbol

Collection of characters

Number which can have a decimal part

2 digit number system

Represented by 1/2^x where x increases towards the right in the binary table

First binary digit

Uses an extra binary digit to add a +ve or -ve sign in front of the binary number

1 as the leading bit (at the start)

0 as the leading bit (at the start)

Makes the most significant bit negative in the binary table

16 digit number system, base 16, uses 0-9 and A-F

4 bits in binary is equivalent to one place of hex

Mantissa and exponent

Number

Power, number of places the floating point is moved

Examples on physics and maths tutor

Larger values are less accurate

Starts 01 for a positive number or 10 for a negative number

Makes numbers as precise as possible in the given number of bits

Shift performed on binary numbers, moves all digits a set number of places to the right/left

Division or multiplication by 2^shift number

Can hold 1 binary digit which is lost due to a shift

Applied to binary by combining with a logic gate

Exclusive OR, both on or both off=0

Logical shifts and mask

Collection of characters and corresponding codes which can be used by computers to represent text

Uses 7/8 bits and can represent 128 characters

Uses fewer bits so each character takes less memory to store

Fewer characters can be represented

Uses a varying number of bits so over a million characters can be represented

Many more characters can be represented

Uses more bits so each character requires more memory to be stored

Specialised format for processing, storing and retrieving data, collection of different kinds of data

Fixed size during run-time

Can change size during run-time

Static, ordered, finite set of elements of a single type, 0-indexed, values stored contiguously

The form of a variable to which a value can be assigned

Like a table, use [y,x]

Like a spreadsheet with many sheets, use [z,y,x] with z as the array number

Like a row in a file, made up of fields - each field can have a different data type

Dynamic data structure, values stored non-contiguously (do not have to be stored next to each other in memory)

Can contain elements of more than one data type

Static ordered set of values, immutable, initialised using normal brackets

Elements cannot be added or removed once the structure has been created

Data stored consecutively together in memory

Dynamic data structure used to hold an ordered sequence of items (nodes)

Items do not have to be stored contiguously, dynamic so it can change size

No direct access to a single piece of data so slow to search, pointers must also be stored

Nodes, contains a data field and a link/pointer field

Holds the address of the next item

Index, data, pointer as well as start pointer and next available location for data

Edit pointers to point to a new item or miss out an existing item

Easy to edit

Node is not removed but simply ignored, which wastes memory

Set of vertices/nodes connected by edges/arcs

Edges can only be traversed in one direction

Edges can be traversed in both directions

Weight (numerical value) attached to each edge

Computers use an adjacency matrix or an adjacency list

Quicker access times than adjacency list

More space efficient for large, sparse networks

LIFO (last in first out) data structure, either static or dynamic

Items can only be added to/removed from the top of the stack

To reverse an action e.g. go back a page in web browsers, undo buttons

Preferred when maximum size of the stack is known in advance, easier to implement and make more efficient use of memory

Uses a pointer that points to the top of the stack, where the next piece of data will be inserted

stackName.function(parameters)

.isEmpty() - must be done before peeking or popping, returns Boolean value and works by checking the value of the top pointer

.push(value)

.peek()

.pop()

.size()

.isFull() - returns Boolean value, works by comparing stack size to top pointer

FIFO (first in first out) data structure

Items are added to the end of the queue and removed from the front of the queue

Printers, keyboards, simulators

Data structure consisting of an array

Items added into the next available space and removed from the front of the queue

Two pointers, one pointing to each end of the queue, where items can be added/removed

Easy to implement

As the queue removes items, there are addresses that cannot be used again, making it ineffective

queueName.function(parameters)

.enQueue(item) - increments back pointer

.deQueue() - increments front pointer

.isEmpty() - works by comparing front and back pointer

.isFull() - works by comparing back pointer and queue size

FIFO, operates similarly to a linear queue

Once back pointer is equal to maximum size of queue, it can loop back to the front and store values there if the space is empty

More space efficient than linear

Harder to implement than linear

Connected form of graph

Top node, has no incoming edges

Item in tree

Connects two nodes

Node with incoming edges

Node with outgoing edges

Subsection of tree consisting of a parent and all the children of that parent

Node with no children

Type of tree where each node has a maximum of two children