A Level Computer Science Paper 1: 1.4.2 Data Structures

An ordered, finite set of elements of a single type

You can make an array of tuples

0-based
Find a value with arrayname[index]
arrayname[row,column] for 2d

You can have any number of dimensions

An ordered set of values, can have elements of mixed type and it is immutable (elements cannot change)

Composed of a fixed number of fields of different data types

Access a value with the name of the record

They can change size when required

They cannot change size

A logical description of how we view the data and possible operations

-1

function isFull()

if size == maxSize:

return True

else:

return False

end if

end function

function isEmpty()

if size == 0;

return True:

else:

return False

end if

end function

function enQueue()

if size < maxSize:

rear ++

rear = rear MOD maxSize

Q[rear] = item

size ++

else:

print (queue is full)

end if

end function

function deQueue()

if size == 0:

item = null

print (queue is empty)

else:

item = Q[front]

front = (front + 1) MOD maxSize

size --

end if

return item

end function

Items are ordered in a queue first based on their priority and then based on FIFO, items move backward to allow a higher priority item to join.

A data structure where keys are mapped to index values, used where faster searching is needed e.g. police records

When an algorithm generates the same address for different primary keys
Methods include putting the value in the next free location or incrementing how far you skip by

Apply the hash function to the key and first check that position, if not increment by 1 and check each
If the original position is empty or you cycle back the value isn’t in the table

Square the number, extract some portion of the resulting digits (likely the middle), then mod by the size of the table

Divide the item into equal sized pieces (excluding maybe the last piece, sum them and carry out the mod with the size of the table

Take the ASCII of each character, sum them and mod with the size

When a value is deleted, a placeholder is used to represent that a value has not been deleted.

A dynamic data type containing a number of ordered items that can be repeated. The elements are stored non-contiguously on the heap and can be of different types

A dynamic abstract data structure which is implemented as an array and pointers

The data and a pointer to the next node

A start pointer identifies the first element in a list, a nextfree pointer highlights the next free space, the last node has null

A collection of elements that are retrieved on a last-in first-out basis

Top and maxSize

| Top starts at -1

Push them all onto a stack and then pop them off

function isFull()

if (top + 1) == maxSize:

return True

else:

return False

end if

end function

function isEmpty()

if top == -1:

return True

else:

return False

end if

end function

procedure push(newItem)

if (top + 1) == maxSize

print (stack is full)

else:

top ++

stack[top] = newItem

end if

end procedure

function pop()

if top == -1:

print (stack is empty)

item = null

else:

item = stack[top]

top --

end if

return item

end function

A set of vertices connected by edges or arcs

Put the weight of the connecting edge and leave boxes blank instead of writing 0s

• convenient to work with, easy to add edges

| - wastes a lot of memory space if nodes have few edges

A list of nodes pointing to their adjacent nodes

| For weighted it has {node:weight}

A connected, undirected graph with no cycles

The node at the top of the tree with no parents

A node below a parent node in a tree

A node above one or more children

A part of a tree which itself is a tree

A node in a tree with no children

A rooted tree in which each node has a maximum of two children, each node has a left and a right pointer (-1 if there is no child on that side)

Start from the root each time and trace to the left if the value is smaller than the current node and to the right if it is larger

Visit the root then follow the left subtree then the right

Follow the left subtree then visit the root then follow the right

Traverse the left subtree then the right then visit the root node

Just remove the node

The child replaces the deleted parent

Repeatedly add 1 to the value of the node until you find the value of another node, which will replace the deleted node

Mainly used for searching as you often have to rebuild the tree after deletion

Traverses the root then the children of the root left to right then their children left to right

Starts at the bottom left and at each leaf it will move up to the latest decision point and go right where it hasn’t been done before

Name = record

DataType FieldName

DataType FieldName

…

End record

recordName.fieldName

listName.append(value)

listName.index(value)

listName.pop(index)

listName.remove(value)

tupleName = (“value1”, “value2”, …)

| Accessed like an array

Returns the top element if the stack isn’t empty