IB Computer Science HL - Topic 5 - Abstract Data Structures

Resources: https://github.com/graded-cs-resources/IB-Computer-Science-Notes/tree/main/paper1 https://pbaumgarten.com/ib-compsci/unit-5-data-structures.pdf

What is recursion

A function or method which calls itself

Advantages of recursion

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

Disadvantages of recursion

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

Why are 2D arrays abstract data structures

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

How is the number of rows in array found

ARR.length

How is the number of columns in an array found

ARR\[0\].length

In index writing in arrays, which comes first, rows or collumns ?

rows

What policy are stacks based on

LIFO

What is the stack insert method ?

Push

What is the queue insert method ?

enqueue

What is the stack removal operation

Pop

What is the queue removal operation

dequeue

What are the applications of queues? (5 implementations)

• printer queues 🖨

• music playlists 🎶

• interrupt handling 🤫

• reversing stacks

• modelling physical queues

What policy are queues based on ?

FIFO

What are the two features of the static implementation of stacks and queues ?

• have a maximum capacity

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

Why are dynamic data structures needed ?

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

How do dynamic data structures enable a dynamic variable size

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

What is a linked list

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

Name differences between a static data structure and dynamic data structure

• 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.

Advantages of a singly linked list

simpler to implement, less memory usage

Disadvantages of singly linked list

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

Advantages of a doubly linked list

bidirectional traversal; easier to search in

Disadvantages of doubly linked list

• uses more memory in comparison to singly linked list

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

Advantages of circular linked lists

the entire list can be traversed starting at any node.

Disadvantages of circular linked list ↻

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

How do you insert a node into an empty list

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

How do you insert a node into the beginning of a list

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

How do you insert a node in to the end of a list

1. Connect tail node to the new node

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

How do you insert a node in to the middle of a 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

Give examples of primitive data types

Double, Integer, Character, Boolean

Dynamic data types have length/ size as a \________

Variable

Static data types have a \_____ length/size

Fixed

Applications of stacks

• storing recursive calls

• implementing function calls

• returning memory addresses

• translations from one programming language to another

• browser history

• in calculations and evaluations of expressions.

Where are elements in a queue enqueued

From the back

Where are elements in a queue dequeued

From the front

What does contiguous memory locations refer to? Give an example of a data structure which uses it

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

What are the features of a dynamic data structure?

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.

Disadvantages of a doubly linked list

• Uses more memory in comparison to singly linked list

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

Advantages of circular linked list

The entire list can be traversed starting at any node.

What is a parent in a binary tree

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

What is a left/right child in a binary tree

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

What is a subtree in a binary tree

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

What is a root in a binary tree

The root is the original node.

What are leaves in a binary tree

All nodes without children

Which way do pre-order traversal flags point

left

Which way do in order traversal flags point

Down

Which way do post order traversal flags point

right

what is the base case

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