Topic 5 - Abstract Data Structures

Recursion

Recursion

• a method where the solution to the problem depends on solutions to smaller instances of the same problem

• Use it to result in iteration/looping behavior without actually writing a loop explicitly in our code.

What is required for recursion?

• Every recursion must have a base case or stopping case. Or else it will go on forever.

StackOverflowError

when it makes a note for itself in memory to do something after doing a method. But each time it calls itself as the method and it eventually runs out of space.

Abstract Data Structures

• 2D arrays

• Stacks

• Queues

• Linked lists

• Binary trees

• Recursion

Characteristics of a Stack

• Push then pop

• LIFO

• A stack stores a set of elements in a particular order.

Characteristics of a Queue

• They are all about enqueue and deque.

• Fifo

Arrays vs Queues / Stacks

• Arrays are static data structures - they cannot change size.

• Stacks and queues are dynamic

• You can use an array to behave like a stack or queue if you give it enough elements to allow the stack or queue to function.

Static data structures

• Size/length determined at creation

• Might / might not be good use of memory space

• Associated with FOR loops

Dynamic data structures

• Size/length determined by contents

• Uses nodes/pointers

• Usually a good use of memory space

• Associated with WHILE loops

Head

Contains pointer to data

Data

• Contains the data

Tail

• Contains pointer to next head

How linked lists operate

• A linear collection of self-referential structures called nodes. They are connected by pointer links.

• Is accessed by keeping a pointer to the first node of the list

• The pointer to the first node is called the head

• Subsequent nodes are accessed via a link pointer member that is stored in each node.

Linked List special cases

• A new node to the beginning of a list

• A new node at the end of a list

• A new node in the middle of the list and so it has a predecessor and successor in the list.

Node at the beginning of the list

• When a new node is inserted right before the current head node

• Update the link of a new node to point to the current head node

• Update head link to point to the new node.

Inserting at the end

• New node is inserted right after the current tail node.

• Update the next link of the current tail node to point to the new node

• Update the tail link to point to the new node

Inserting in the middle

• New node is usually inserted between two existing nodes. Head and tail links are not updated in this case.

• Update the link of the previous node to point to the new node

• Update the link of the new node to point to the next node.

Single or linear linked lists

• Single head, single tail

• Each pointer works in only one direction.

Doubly linked lists

• Single head, single tail, first and last element.

• Two pointers for each element. One to the next and one to the previous

Circular linked list

• Single head

• One pointer for each element

• Last element’s pointer points to the head, creating a circle.

How Trees Operate Logically

• A binary tree is made of nodes, where each node contains a left and right pointer and a data element.

• The root pointer points to the topmost node in the tree

• The left and right pointers recursively point to smaller subtrees.

• A null pointer is a binary tree with no elements - basically an empty tree.

• The formal recursive definition: a binary tree is either empty, or is made of a single node, where the left and right pointers, each point to a binary tree.

Preorder Tree Traversal

Start on the left of the circle

Inorder Tree Traversal

Start on the bottom of the circle

Postorder Tree Traversal

Start to the right of the circle

Dynamic data structure

• Data structures that can change size during the execution of a program.

• They grow and shrink as required

• Size is determined by the run time

• Very efficient use of memory space

Compare static and dynamic

Stacks

• Implement function calls (methods)

• Most compiler implement function calls by using a stack

• Provides a technique for eliminating recursion from a program. Instead of calling one function recursively use a stack to simulate the function calls in the same way a compiler would have.

• Also can use recursion instead of a stack.

Queues

• Computing applications - serving requests of a single shared resource

  • Eg printer

• Buffers

  • Playlist on a phone

• Playlist - for a jukebox add songs to the end, play from the front of the list

• Interrupt handling - when programming a real-time system that can be interrupted, you must attend to the interrupts immediately before proceeding with the current activity. If the interrupts should be handled in the same order they arrive then FIFO is the best.

Advantages of Linked List

• You need constant-time insertions or deletions from the list

• You don’t know how many items will be on the list

• You don’t need random access to any elements

• You want to be able to insert items in the middle of the list

Arrays

• Need indexed/random access to elements

• You know the number of elements in the array ahead of time

• You need speed when iterating through all elements in a sequence.

• Memory is a concern. Filled arrays take up less memory than linked list.

  • Each element in the array is just the data

  • Each linked list node needs the data as well as one or more pointers to other elements in the list with it.

Binary Trees

• Binary search tree - used in search applications where data is constantly entering/leaving, such as the map and set objects.

• Heaps - implementing efficient priority-queues which in turn are used for scheduling in many operating systems.

• GGM trees - cryptographic applications to generate a tree of pseudo-random numbers

• Syntax tree - constructed by compilers and implicitly calculators to parse expressions.