Topic 5: IB Computer Science Abstract Data Structure

Topic 5

Abstract Data Structures

Thinking recursive

A thought pattern pertaining to recursion

Recursion

The process of a method calling itself in order to solve a problem.

Itteration

the repetition of a process

base case

The condition under which a recursive function returns without calling itself, thereby ending the recursive calls.

recursive case

a condition of the input data where the data will be handled by call(s) to the same program.

Advantages of using recursion

Elegance

Efficiency

2 dimensional array

a data structure that contain rows and columns of data. Each element position requires an index specifying the row and an index specifying the column

jaggered array

A 2D array with non constant inner array lengths

stack

a collection of items in which the last item added to the collection is the first one to be removed

null

the final 'element' of any stack

.push()

Method to add an item to a stack

.pop()

method removes and returns the last object from a stack

.isEmpty()

Method to determine if a collection is empty

Queue

A collection of data with a first in first out nature

.enqueue()

Queue Operation: add an element to the rear.

.dequeue()

Queue Operation: remove an element from the front.

Linked lists

a collection of nodes arranged so that each node contains a link to the next node in the sequence

singly linked list

a data structure in which each list element contains a pointer to the next list element

doubly linked list

a linked list in which each element has both forward and backward pointers.

Circular Linked List

A list in which every node has a successor; the "last" element is succeeded by the "first" element

Binary tree

A data structure that consists of nodes, with one root node at the base of the tree, and two nodes (left child and right child) extending from the root, and from each child node.

Root node

node at the top of a tree

Leaf node

A tree node that has no children

branch node

Any internal node of a tree (Not a leaf or root node)

subtree

A tree that is part of another tree.

Edge

Connection between nodes

null

All leaf nodes of a tree point to :

Visiting

The process of looking at a node

Traversal

the process of accessing each item in a tree one at a time

preorder traversal

root, left subtree, right subtree

inorder traversal

left subtree, root, right subtree

postorder traversal

left subtree, right subtree, root

static

a data structure with a constant size is said to be:

dynamic

a data structure with a variable size is said to be: