1 of 53

Topic 5 (HL)

Abstract Data Structures

IB Computer Science

The British International School, Istanbul

2 of 53

Static Data Structures

  • Number of elements determined at creation of data structure - cannot be changed later on
  • Can be memory inefficient, because RAM is allocated based on predetermined number of elements, rather than actual elements, leaving possibility of unused memory space
  • Iterated through using FOR loops
  • Examples: Arrays

​

The British International School, Istanbul

3 of 53

Dynamic Data Structures

  • No need to predetermine number of elements, any number of elements can exist in data structure at any time
  • Each element exists at a particular memory address and is referred to as a node.
  • Each node contains a “reference” to the memory address of the next element in the data structure. This reference is called a pointer.
  • Usually more memory efficient than static data structures
  • Iterated through using WHILE loops
  • Examples: Collections

​

The British International School, Istanbul

4 of 53

Static vs. Dynamic

The British International School, Istanbul

5 of 53

2D Arrays

  • An array of arrays
  • array[row][column]
  • Used to display data points with 2 dimensions
  • Used to display grids

The British International School, Istanbul

6 of 53

2D Arrays - Basic Tasks

  • Identify specific positions in 2D arrays
  • Iterate through 2D Arrays
  • Iterate through rows in 2D arrays
  • Iterate through “columns” in 2D Arrays
  • Count values in 2D Arrays

The British International School, Istanbul

7 of 53

The British International School, Istanbul

8 of 53

The British International School, Istanbul

9 of 53

The British International School, Istanbul

10 of 53

The British International School, Istanbul

11 of 53

Recursion

  • Recursion is when a method calls itself until some terminating condition is met, known as the base case.
  • Recursion can be used in situations where the next result of an operation depends on the current result.
  • Some good examples including the Fibonacci sequence or a factorial function
  • Each step until the base case is reached is called a recursive step.
  • All recursive functions can be written iteratively (without calling itself)

​

The British International School, Istanbul

12 of 53

Recursion Examples

The British International School, Istanbul

13 of 53

Recursion - Basic Tasks

  • Calculate the output of a recursive function

The British International School, Istanbul

14 of 53

The British International School, Istanbul

15 of 53

The British International School, Istanbul

16 of 53

Recursion Pros & Cons

The British International School, Istanbul

17 of 53

Part 2 - Table of Contents

  • Recursion Review
  • Stacks
  • Queues
  • Linked Lists

​

  • Part 3: Binary Trees, Extra Practice

The British International School, Istanbul

18 of 53

The British International School, Istanbul

19 of 53

The British International School, Istanbul

20 of 53

The British International School, Istanbul

21 of 53

The British International School, Istanbul

22 of 53

The British International School, Istanbul

23 of 53

The British International School, Istanbul

24 of 53

Stacks

  • Dynamic Data Structure
  • LIFO (Last in First Out) - the last element to be “pushed” (inserted) into the stack is the first to be removed (“popped”)
  • Used to keep track of function calls

The British International School, Istanbul

25 of 53

Stacks - Basic Tasks

  • Add and remove values from a stack
  • Completely empty a stack
  • Transfer from array to stack and vice-versa
  • Count the number of values in a stack

The British International School, Istanbul

26 of 53

The British International School, Istanbul

27 of 53

The British International School, Istanbul

28 of 53

Queues

  • Dynamic Data Structure
  • FIFO (First in First Out) - the first element to be “enqueued” (inserted) is the last to be “dequeued” (removed) like a real-life queue

The British International School, Istanbul

29 of 53

The British International School, Istanbul

30 of 53

The British International School, Istanbul

31 of 53

Queues - Basic Tasks

  • Add and remove values from a queue
  • Completely remove values from a queue
  • Transfer from array to queue and vice-versa
  • Transfer from stack to queue and vice-versa
  • Count the number of values in a queue

The British International School, Istanbul

32 of 53

Linked Lists

  • Head, Pointer, Node, Tail
  • Types of Linked Lists
    • Single Linked
    • Double Linked
    • Circular Linked

The British International School, Istanbul

33 of 53

Linked Lists - Basic Tasks

  • Traverse a linked list
    • Front and back of circular linked list
  • Insert values from a linked list
  • Remove values from a linked list

The British International School, Istanbul

34 of 53

The British International School, Istanbul

35 of 53

The British International School, Istanbul

36 of 53

The British International School, Istanbul

37 of 53

The British International School, Istanbul

38 of 53

The British International School, Istanbul

39 of 53

The British International School, Istanbul

40 of 53

The British International School, Istanbul

41 of 53

The British International School, Istanbul

42 of 53

Binary (Search) Trees - Basic Tasks

  • Build a binary tree from a set of integers or letters
  • Traverse a binary tree using preorder, inorder, and postorder methods
  • Add new values to a binary tree
  • Remove existing values from a binary tree

The British International School, Istanbul

43 of 53

Binary (Search) Trees Pros & Cons

Advantages

Disadvantages

Searching is time efficient - Only half the elements need to be checked

Need to be “balanced”

Elements don’t need to be removed to be checked like stacks or queues

Insertion and deletion are slow due to need to rebalance tree

​

Searching is slower than arrays in cases where the location is known - the tree needs to be traversed regardless

The British International School, Istanbul

44 of 53

The British International School, Istanbul

45 of 53

The British International School, Istanbul

46 of 53

The British International School, Istanbul

47 of 53

The British International School, Istanbul

48 of 53

The British International School, Istanbul

49 of 53

The British International School, Istanbul

50 of 53

The British International School, Istanbul

51 of 53

The British International School, Istanbul

52 of 53

The British International School, Istanbul

53 of 53

The British International School, Istanbul