Studied by 4 people
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.
2D arrays
Stacks
Queues
Linked lists
Binary trees
Recursion
Push then pop
LIFO
A stack stores a set of elements in a particular order.
They are all about enqueue and deque.
Fifo
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.
Size/length determined at creation
Might / might not be good use of memory space
Associated with FOR loops
Size/length determined by contents
Uses nodes/pointers
Usually a good use of memory space
Associated with WHILE loops
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.
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.
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.
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
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 head, single tail
Each pointer works in only one direction.
Single head, single tail, first and last element.
Two pointers for each element. One to the next and one to the previous
Single head
One pointer for each element
Last element’s pointer points to the head, creating a circle.
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.
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
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.
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.
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
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 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.
