Array
A data structure that stores an ordered list of items, with each item is directly accessible by a positional index.
Linked List
A data structure that stores ordered list of items in nodes, where each node
...
Array
A data structure that stores an ordered list of items, with each item is directly accessible by a positional index.
Linked List
A data structure that stores ordered list of items in nodes, where each node stores data and has a pointer to the next node.
Bianary Search Tree
A data structure in which each node stores data and has up to two children, known as a left child and a right child.
Hash Table
A data structure that stores unordered items by mapping (or hashing) each item to a location in an array (or vector).
Hashing
mapping each item to a location in an array (in a hash table).
Chaining
handles hash table collisions by using a list for each bucket, where each list may store multiple items that map to the same bucket.
Hash key
value used to map an index
bucket
each array element in a hash table
ie A 100 elements hash table has 100 buckets
modulo hash function
computes a bucket index from the items key.
It will map (num_keys / num_buckets) keys to each bucket.
ie... keys range 0 to 49 will have 5 keys per bucket.
50 / 10 = 5
hash table searching
Hash tables support fast search, insert, and remove.
Requires on average O(1)
Linear search requires O(N)
modulo operator %
common has function uses this. which computes the integer remainder when dividing two numbers.
Ex: For a 20 element hash table, a hash function of key % 20 will map keys to bucket indices 0 to 19.
Max-Heap
A binary tree that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys. (Actually, a max-heap may be any tree, but is commonly a binary tree).
*a max-heap's root always has the maximum key in the entire tree.
Heap storage
Heaps are typically stored using arrays. Given a tree representation of a heap, the heap's array form is produced by traversing the tree's levels from left to right and top to bottom. The root node is always the entry at index 0 in the array, the root's left child is the entry at index 1, the root's right child is the entry at index 2, and so on.
Max-heap insert
An insert into a max-heap starts by inserting the node in the tree's last level, and then swapping the node with its parent until no max-heap property violation occurs.
The upward movement of a node in a max-heap is sometime called percolating.
Complexity O(logN)
Max-heap remove
Always a removal of the root, and is done by replacing the root with the last level's last node, and swapping that node with its greatest child until no max-heap property violation occurs.
Complexity O(logN)
Percolating
The upward movement of a node in a max-heap
Min-Heap
Similar to a max-heap, but a node's key is less than or equal to its children's keys.
Heap - Parent and child indices
Because heaps are not implemented with node structures and parent/child pointers, traversing from a node to parent or child nodes requires referring to nodes by index. The table below shows parent and child index formulas for a heap.
ie
1) parent index for node at index 12? 5
*** ((12-1) // 2) = 5 or 12 //2 -1 = 5
2) child indices for a node at index 6? 13 & 14
** 2 6 + 1 = 13 and 2 * 6 + 2 = 14
**Double# and add 1, double# and add 2
Node index Parent Index Child Indices
0 N/A 1, 2
1 0 3, 4
2 0 5, 6
3 1 7, 8
4 1 9, 10
5 2 11, 12
Heap - parent_index
parent_index = (node_index - 1) // 2
or node_index // 2 - 1
Heap - left_child_index
left_child_index = 2 * node_index + 1
Heap - right_child_index
right_child_index = 2 * node_index + 2
Implementing priority queues with heaps.
Both functions return the value in the root, but the Pop function removes the value and the Peek function does not. Pop is worst-case O(logN) and Peek is worst-case O(1).
Push and pop operate have runtime O(logN). All other operations (Peek, IsEmpty, GetLength) happen in constant time O(1).
Array based list
A list ADT implemented using an array. An array-based list supports the common list ADT operations, such as append, prepend, insert after, remove, and search.
Linked list vs Array
If a program requires fast insertion of new data, a linked list is a better choice than an array.
Abstract Data Type (ADT)
A data type described by predefined user operations, such as "insert data at rear," without indicating how each operation is implemented.
List
An ADT for holding ordered data. Dups ok
Sequence type: A mutable container with ordered elements.
Underlying data structures: Array, linked list
Array in Java
generic class that supports different data types. declared as follows, where T is the data type.
Tuple
Sequence type: An immutable container with ordered elements.
Stack
An ADT in which items are only inserted on or removed from the top of a stack.
*Last-in First-Out
Underlying data structures: Linked list
Push(stack, x), pop(stack), peek(stack), IsEmpty(stack), GetLength(stack)
*Pop & peek should not be used on a empty stack.
Stack operations
Example starting with stack: 99, 77 (top is 99).
Push(stack, x)
Inserts x on top of stack
Push(stack, 44). Stack: 44, 99, 77
Pop(stack)
Returns and removes item at top of stack
Pop(stack) returns: 99. Stack: 77
Peek(stack)
Returns but does not remove item at top of stack
Peek(stack) returns 99. Stack still: 99, 77
IsEmpty(stack)
Returns true if stack has no items
IsEmpty(stack) returns false.
GetLength(stack)
Returns the number of items in the stack
GetLength(stack) returns 2.
Implementing a stack in python (Linear data structure)
Can be implemented in Python using a class with a single LinkedList data member.
The class has two methods, push() and pop().
push() adds a node to the top of the stack's list by calling LinkedList's prepend() method.
*New elements are place on the top of the stack, not at the bottom of the stack.
pop() removes the head of the stack's list by calling the LinkedList's remove_after() method and then returns the removed node.
Implementing a queue in python (Linear data structure)
Can also be implemented in Python using a class with a single LinkedList data member and class methods push() and pop().
push() adds a node to the end of the queue's list by calling LinkedList's append() method.
*New elements are added to the end of a queue.
The pop() method removed the queue's head node and is identical to Stack's pop() method.
Queue
An ADT in which items are inserted at the end of the queue and removed from the front of the queue.
*first-in first-out ADT.
Underlying data structures: Linked list, Array, Vector
The Queue class' push() method uses the LinkedList append() method to insert elements in a queue.
Both the Stack and Queue pop() methods operate exactly the same by removing the head element and returning the removed element.
Linked List
A linear data structure, much like an array, that consists of nodes, where each node contains data as well as a link to the next node, but that does not use contiguous memory.
Head and tail node
The LinkedList class implements the list data structure and contains two data members, head and tail, which are assigned to nodes once the list is populated. Initially the list has no nodes, so both data members are initially assigned with None.
If the node has no next node, the next data member is assigned with None, the Python term signifying the absence of a value.
Doubly-linked lists
In a previous section, the LinkedList class was defined, making use of the Node class. The Node class defined previously can be extended from the singly-linked list version to include a reference variable called prev that refers to the previous node in the list. When a new node is first constructed, the prev variable is assigned with None.
Creating a doubly-linked node or a doubly-linked list is still the same as creating a singly-linked node and a singly-linked list.
A linked list's head node does not have a previous node, thus the prev data member has a value of None.
Deque
Short for double-ended queue- an ADT in which items can be inserted and removed at both the front and back.
Underlying data structures: Linked list
Bag
An ADT for storing items in which the order does not matter and duplicate items are allowed.
Underlying data structures: Linked list, Array
Set
An ADT for a collection of distinct items. (no dups!)
Underlying data structures: Binary search tree, Hash table
Priority queue
A queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority. Dups ok
Underlying data structures: Heap
*In addition to push and pop, a priority queue usually supports peeking and length querying. A peek operation returns the highest priority item, without removing the item from the front of the queue.
Pop returns front or head item which is top priority item
Dictionary (Map)
A dictionary is an ADT that associates (or maps) keys with values.
Underlying data structures: Binary search tree, Hash table
Dictionary key characteristic
They are unique and immutable.
Dictionary method
D1[key].remove(value)
dict.items()
returns a view object that yields (key, value) tuples.
dict.keys()
returns a view object that yields dictionary keys.
dict.values()
returns a view object that yields dictionary values.
Dict for loop
A for loop over a dict retrieves each key in the dict.
ie.. for key in dictionary:
dict operations
my_dict[key]
Indexing operation - retrieves the value associated with key.
john_grade = my_dict['John']
my_dict[key] = value
Adds an entry if the entry does not exist, else modifies the existing entry.
my_dict['John'] = 'B+'
del my_dict[key]
Deletes the key entry from a dict.
del my_dict['John']
key in my_dict
Tests for existence of key in my_dict
if 'John' in my_dict: # ...
dict methods
my_dict.clear()
Removes all items from the dictionary
my_dict = {'Bob': 1, 'Jane': 42}
my_dict.clear()
print(my_dict)
{}
my_dict.get(key, default)
Reads the value of the key entry from the dict. If the key does not exist in the dict, then returns default.
my_dict = {'Bob': 1, 'Jane': 42}
print(my_dict.get('Jane', 'N/A'))
print(my_dict.get('Chad', 'N/A'))
42
N/A
my_dict1.update(my_dict2)
Merges dictionary my_dict with another dictionary my_dict2. Existing entries in my_dict1 are overwritten if the same keys exist in my_dict2.
my_dict = {'Bob': 1, 'Jane': 42}
my_dict.update({'John': 50})
print(my_dict)
{'Bob': 1, 'Jane': 42, 'John': 50}
my_dict.pop(key, default)
Removes and returns the key value from the dictionary. If key does not exist, then default is returned.
my_dict = {'Bob': 1, 'Jane': 42}
val = my_dict.pop('Bob')
print(my_dict)
{'Jane': 42}
Underlying data structures: Binary search tree, Hash table
Set, Dictionary(Map)
Underlying data structures: Heap
Priority queue
Underlying data structures: Linked list, Array
Bag, Queue, List
Underlying data structures: Linked list
Deque, Stack
Common operations for ADT List
Append, Prepend, InsertAfter, Print, PrintReverse, Sort, Remove, Search, IsEmpty, GetLength
Common operations for ADT Queue, Stack, Deque
Push, Pop, Peak, IsEmpty, GetLength
Float
Data type is a single-precision 32-bit IEEE 754 floating point. Use a float (instead of double) if you need to save memory in large arrays of floating point numbers.
Double
A data type is a double-precision 64-bit IEEE 754 floating point. For decimal values, this data type is generally the default choice.
Byte
Data type is an 8-bit signed two's complement integer. The byte data type is useful for saving memory in large arrays.
Range(5)
0 1 2 3 4
Every integer from 0 to 4
Assignment vs comparison
= vs ==
garbage collection
It reclaims memory from data structures implemented using linked allocations. Python is a managed language, meaning objects are deallocated automatically by the Python runtime, and not by the programmer's code. When an object is no longer referenced by any variables, the object becomes a candidate for deallocation.
Python's garbage collector will deallocate objects with a reference count of 0. However, the time between an object's reference count becoming 0 and that object being deallocated may differ across different Python runtime implementations.
Reference Count
An integer counter that represents how many variables reference an object. When an object's reference count is 0, that object is no longer referenced.
Memory allocation
The process of an application requesting and being granted memory.
Memory used by a Python application must be granted to the application by the operating system. When an application requests a specific amount of memory from the operating system, the operating system can then choose to grant or deny the request.
Python does this automatically
Binary search
is an algorithm that searches a SORTED LIST for a key by first comparing the key to the middle element in the list and recursively searching half of the remaining list so long as the key is not found.
constructor
The __init__ method, commonly known as a constructor, is responsible for setting up the initial state of the new instance.
[Show More]
.png)
