IB HL Computer Science
___
Notes
Topic 5 Abstract data structure
5.1.4 two dimensional array
Indexed by two number [x][y]
Also access value with two indexes
5.1.6 Stack
● Last in first out
, ● Pop - remove
● Push - add
● isEmpty - return true if stack is empty
● Use for chronological order and undo
● Can use depth instead of index
5.1.8 Queue
● Enqueue - add an item to the end of the queue
● Dequeue - remove and return the first item from the queue
● First in First out
● Uses for situations where order is required
● Printer queue or ticketing system
5.1.11 Static vs Dynamic
● Static size is constant
● Statis is usually a less effective usage of storage space
● Dynamic size changes with the elements
● Dynamic is associated with while loop
● Static is associated with for loop
● Dynamic uses nodes
,5.1.12 Linked list
● Each element has a node that points to the next element
● The head points to the first element
● In order to access an element, you have to follow the pointers from
the beginning
● The last node contains a null pointer
5.1.13
Changing a linked list is easier than a normal list because only the nodes have to
change
, Singly linked list
There is a node pointing to the next element
Doubly linked list
There is a node pointing to the next element and the previous element
Circular linked list
Last link points back to the first one
Can cause infinite loop
The one on the rightmost is the head.
5.1.14 - 5.1.17 Tree
● Binary and non binary tree
● Binary tree node can’t have more than 2 children
● A null pointer is an empty binary tree
● Root is the first element on top
● Leaf are nodes that have no children
● Subtree are parent and children that are a part of a bigger tree
● There are left child and right child
___
Notes
Topic 5 Abstract data structure
5.1.4 two dimensional array
Indexed by two number [x][y]
Also access value with two indexes
5.1.6 Stack
● Last in first out
, ● Pop - remove
● Push - add
● isEmpty - return true if stack is empty
● Use for chronological order and undo
● Can use depth instead of index
5.1.8 Queue
● Enqueue - add an item to the end of the queue
● Dequeue - remove and return the first item from the queue
● First in First out
● Uses for situations where order is required
● Printer queue or ticketing system
5.1.11 Static vs Dynamic
● Static size is constant
● Statis is usually a less effective usage of storage space
● Dynamic size changes with the elements
● Dynamic is associated with while loop
● Static is associated with for loop
● Dynamic uses nodes
,5.1.12 Linked list
● Each element has a node that points to the next element
● The head points to the first element
● In order to access an element, you have to follow the pointers from
the beginning
● The last node contains a null pointer
5.1.13
Changing a linked list is easier than a normal list because only the nodes have to
change
, Singly linked list
There is a node pointing to the next element
Doubly linked list
There is a node pointing to the next element and the previous element
Circular linked list
Last link points back to the first one
Can cause infinite loop
The one on the rightmost is the head.
5.1.14 - 5.1.17 Tree
● Binary and non binary tree
● Binary tree node can’t have more than 2 children
● A null pointer is an empty binary tree
● Root is the first element on top
● Leaf are nodes that have no children
● Subtree are parent and children that are a part of a bigger tree
● There are left child and right child
