This story is a part of — My CS Notebook
Array
- Worst Case: Access: O(1); Search O(n); Insertion O(n); Deletion O(n);- Best Case: Access: O(1); Search O(n); Insertion O(n); Deletion O(n);o Meant to store data (usually of the same type) in consecutive memory locations.o If the United States was an Array, each state (value) would be a member from a memory standpoint because they border of each state (value) would be touching.
Linked List
- Worst Case: Access: O(n); Search O(n); Insertion O(1); Deletion O(1);- Best Case: Access: O(n); Search O(n); Insertion O(1); Deletion O(1);o Linked list is linear data structure that are a collection of objects.o Each Node contains a value attribute and a pointer attribute.o Although often visually describe as a train (where the value is the car and the pointer is the coupler) from a memory perspective the locations of each value are not always allocated in the area.
Linked List Variants
§ Singly Linked List – above definition§ Doubly Linked List – each node contains three attributes (pointer to the preceding, pointer to the proceeding, and data)§ Circular Linked List – end points to beginning
Stack
o Big O: worst case O(1); assumed always true because stack is not meant for transversal.o A stack can be visualized as plates in a cabineto Last in first out. Insertion and deletion happen on the same end.
Queue
o Big O: worst case O(1): assumed always true because stack is not meant for transversal.o Queue is similar to a stack but differs in executiono With a Queue first out is the item least recently adde
Binary Tree
(1) Big O:Worst Case: Access: O(n); Search O(n); Insertion O(1); Deletion O(1);Best Case: Access: O(x); Search O(x); Insertion O(x); Deletion O(x); where x = height or log(n)(2) Binary Tree is a more complex implementation of a linked list and is no linear(3) Each node contains three attribute (data, pointer to left child, pointer to right child)(4) Binary Trees are specific than Binary Search Tree which have specific requirements. A search engine might utilize both to increase efficiency(5) A Classification And Regression Tree (CART Model) uses a binary tree to evaluate conditions(6) MySQL uses a Binary Tree to sort indexes
Binary Search Tree
(1) Big O:- Worst Case: Access: O(n); Search O(n); Insertion O (1); Deletion O(1);- Best Case: Access: O(x); Search O(x); Insertion O(x); Deletion O(x); where x = height or log(n)(2) A Binary Search Tree is a Binary Tree with rules- Left subtree contains lesser values than the root node- Right subtree of contains greater values than the root node- Each subtree must also be a binary search tree(3) The idea of Binary Tree is to increase read efficiency. When an insertion happens, the tree is “read” down to the best fit location. For example, if the first split is < 5 on the left and > than 5 on the right, an entry of 7 would be place on the right leaf. As the tree scales the insertion time increases, however the read time is much less than having to iterate over an array.Search applications and 3D video games
Heap
a. Big O: * O(log(n))b. Tree based data structure
Common Heap Types
Max-Heap:1. Root node must be the greatest value2. All sub trees must follow same patternMin-Heap:1. Root node must be the least value2. All sub tress must follow same pattern
Hash
- Big O: Best O(1); Worst O(n)- Hashed is more efficient than a direct access table, it operates similarly, but instead of using the provide key it reduced the key to a smaller index- At scale can be memory intensive and can cause risk of duplication
Graph
a. Non-linear; non-tree; non-direct access data structureb. The structure is made of two attributes: nodes and edges.c. Edges connect any two nodesd. Graphs have the ability to store complex relationshipse. Often used in anything that is related to networksf. Can transverse in Depth First or Breadth First- Graphs can contain cycle which means traversing might bring a client to the same node more than once. Hear a “visited” Boolean can be utilized at the node level- Breadth is width first, then height- Depth is height first, then width
Matrix
a. Commonly a list of lists in implementationb. Has a width and b height; where b > 1
This story is a part of — My CS Notebook
Enjoy the read?
Leave a clap or comment
Share with friends or on your favorite social platform
