what is a linked list
linear collection of self referential structures (nodes) connected by pointer links
- accessed by keeping a pointer to first node of list; called “head”
how to delete a node from binary search tree (3 cases)
- a leaf
- set parent to null - node w/ one child
- make parent skip over deleted node - node w/ two children
- go once left, then as far right as possible, then replace deleted node w/ this node
applications of stacks
- undo mechanism
- recently visited wesbties (history)
- check for balanced parentheses
- evaluate expressions
what is difference between non-binary and binary tree
non-binary: can have any # of children
binary: only can have 2 children (left & right)
operations for queues
enqueue()
dequeue()
variants of queues
- circular: end connected to beginning; after last task finished, first task starts
- priority: task w/ higher priority executes first
- double ended queue: can insert/delete from both front and back
what are the types of tree traversal and how do each of them work?
- preorder
- flag attatched to left side
- traverses each path completely before moving to next path - inorder
- flag attatched to bottom side
- traverses left to right - postorder
- flag attatched to right side
- traverses children first
operations for stacks
push()
pop()
isEmpty()
size()
what is a binary tree
either empty (null pointer), or is made of a single node, where left & right pointers each point recursively to a smaler binary subtree
how do stacks work
last-in-first-out (LIFO)
3 types of linked lists?
- single
- 1 head, 1 tail
- each pointer in 1 direction only - doubly
- 1 head, 1 tail
- 2 pointer: one to next node, one to previous node - circular
- 1 head
- 1 pointer for each element
- last elemtent points to head
what do you use inorder, preorder, and postorder traversal of binary trees for?
- inorder: sorted data (ascending)
- preorder: recreating tree in exact order
- postorder: deleting items starting from leaves
what is the max # nodes at a given level of binary tree
2^(level-1)
eg. max # nodes at level 2 = 2^1 = 2 nodes
what is a binary search tree
- every node in left subtree is less than or equal to its parent node
- vice versa for right
- when tree traversed inorder: values of nodes will be in ascending order
how to insert an item into a binary search tree
if value less than
go left
else
go right
applications of queues
- tasks scheduled (eg. printing)
- data transfers
- traffic signals (?)
what are infix, prefix, postfix
- infix: binary operators between operands
- prefix: binary operators before operands
- postfix: binary operators after operands
how do queues work
first-in-first-out (FIFO)
features of an abstract data type
Its (behaviour) is defined by its operations [1] and the data that the operations are carried
out on [1];
An ADT is a complex data type;
Each ADTs has standardised methods/operations / a specific set of methods/operations
(such as addToEnd. Push etc.);
Implementation details are hidden from the user;
Users only need to know how to use the operations/methods;
Allow ADTs can be allocated memory dynamically;
dyanmic vs. static abstract data types?
static - fixed size (eg. array)
dynamic - can change size (eg. array list)
pros & cons of dynamic adt
pros:
- only uses space needed at any time
- makes efficient use of memory (in general)
cons:
- difficult to program
- can be slow to implement searches
- linked list only allows serial search
pros & cons of static adt
pros:
- easy to program
- easy to check overflow
- array allows random access
- deleting item does not affect index of other items
cons:
- can waste space
when to use stacks?
- function calls (methods)
- replace recursion
when to use queues?
- computing applications: serving requests (eg. printing)
- playlists
- interrupt handling
