IB Computer Science HL Paper 1 Topic 5

Recursion

* A method that calls itself
* Involves the use of stacks to store data that will be returned at end
* Can be memory intensive if many recursive calls are made

Characteristics of a stack

* A data structure
* LIFO
* dynamic

Stack access methods

* push()
* pop()
* isEmpty()

Characteristics of a queue

* FIFO
* dynamic

Queue access methods

* enqueue()
* dequeue()
* isEmpty()

Real world examples of queues

* Printer queues
* Computer modelling of real-life queues (like in supermarkets)

Linked lists

* Linear collection of nodes, which are self-referential
* Nodes connected by pointer links

Features of a doubly linked list

* Single head, single tail
* Each node has two pointers - one to next, one to previous

Features of a circular linked list

* Single head
* One pointer for each element
* Last element’s pointer points to head

**Binary trees**

Parent

* A node in a tree that has children (left, right or both)

Root

* The top node in a tree

Subtree

* A parent with children within another parent-child relationship

Dynamic data structures pros and cons

Pros

* Can change size while program is running
* Makes efficient use of memory
* Storage no longer required can be returned to the system for other use

Cons

* Difficult to program
* Can be slow / complex to implement
* A linked list only allows serial (in order) search

Static data structures pros and cons

Pros

* Easy to program
* Easy to check for overflow
* An array allows random access
* Does not change in size while program is running

\
Cons

* Can waste space
* Programmer has to estimate space needed, could be wrong