IB Computer Science HL - Topic 5 - Abstract Data Structures

A function or method which calls itself

Can reduce time complexity and development time and it can add clarity

Complex to implement and memory inefficient as each recursion adds a new call to memory and previous function calls remain open

They are made up of a group of 1D arrays which are data structures themselves

ARR.length

ARR[0].length

rows

LIFO

Push

enqueue

Pop

dequeue

• printer queues 🖨

• music playlists 🎶

• interrupt handling 🤫

• reversing stacks

• modelling physical queues

FIFO

• have a maximum capacity

• rely on pointers to add and ‘remove’ elements.

1. They allow dynamic memory allocation so we don't need to declare their size at initialisation.

2. They don't need contiguous memory locations as they are linked by referencing the address of the next node.

3. Insert and delete operations are not computationally expensive as they don't require element shifting

As each node has a pointer to other nodes, only the pointers need to be changed to add, remove or move a node

a linear collection of self-referential data structures, called nodes, connected by pointers.

• Static structures have a fixed size, dynamic structures have a variable length.

• Static structures have declaration-time size allocation, dynamic have runtime size allocation.

• Static have random access (indexes), dynamic has sequential access (no indexes).

• Static are easier for searching and storing and use less memory.

• Dynamic data structures can be more memory efficient overall as the data structure only uses what’s necessary as size will increase or decrease at runtime

• Dynamic structures have a possibility of overflow or underflow during runtime if allocations are exceeded. This doesnt happen in static structures as memory size is fixed.

simpler to implement, less memory usage

unidirectional, so slower for searching and sorting; randomly stored so direct access isn’t allowed (sequential only)

bidirectional traversal; easier to search in

• uses more memory in comparison to singly linked list

• randomly stored so direct access isn’t allowed (sequential only)

the entire list can be traversed starting at any node.

inserting at the start would be expensive as it requires searching through for the final element; finding the end is hard.

When the list is empty, indicated by head == NULL, the insertion sets both the head and tail to the current node

1. The pointer of the new head node will point to the previous head node;

2. The header pointer will point to the new node.

3. The connection between header node and header pointer is removed

1. Connect tail node to the new node

2. The new node will be connected to null (in singly linked list)

1. The pointer of the previous node will now point to the new node.

2. The new node will now point to the next node.

3. Delete the connection of previous node

Double, Integer, Character, Boolean

Variable

Fixed

• storing recursive calls

• implementing function calls

• returning memory addresses

• translations from one programming language to another

• browser history

• in calculations and evaluations of expressions.

From the back

From the front

It means that all elements need to be stored together. eg. an array

Pointers.

• Each node has a pointer, they don’t need to be placed next to each other.

• To delete and insert nodes, only the pointers need to be changed.

• Enables their dynamic size.

• Uses more memory in comparison to singly linked list

• randomly stored so direct access isn’t allowed (sequential only)

The entire list can be traversed starting at any node.

A node which has children. They will be linked below it.

A child node on the left/right-hand of the parent.

A parent with a child. It can be one or two children.

The root is the original node.

All nodes without children

left

Down

right

a point at which the recursion will stop because the most basic endpoint has been reached, so a simple answer can be given.