Data Structures Flashcards
Flash Cards 1. Overview 2. Pros and Cons - why this one over the another? 3. Big O - what is it optimized for? - operation (insertion, deletion etc), - big o notation (worst case), - explanation (why is it this big o) 4. What problems can it solve - Where could I potentially see this in the wild - leet code problems will be good for this 5. Code w/ Big O and code comment - define paramaters and return of a method/function - comment code
Linked List
Overview
A Linked List is a data structure consisting of nodes which in themselves usually have 2 properties: a value and a next pointer. The next pointer points to the next node in the list. The last node in the leist points to null
The list itself usually has 2 properties: the head and the size.
head 5 => 19 => 3 => 90 => 1 => null
Stack (Linked List)
Overview
A Stack is a data structure with LIFO behavior (LAST IN FIRST OUT) A Linked List is a better implementation since insert and deletion are O(1) time complexity
The stack itself usually has 2 main properties: the first and size.
head 5 => 19 => 3 => 90 => 1 => null
Linked List
Big O of Insertion, Deletion, Access and Search w/ Explanation
Insertion [ O(1) ]
:: Because of the next pointer in this structure, the act of inserting a new node is constant. No matter the size of the input, we only need to temporarily store the node located at the insertion point ($rest), make the node previous to the insertion point to the new node and point the new node to the stored $rest of the list.
Deletion: [ O(1) ]
:: Similar reason to insertion
Search: [ O(n) ]
:: Worst case, we need to iterate over the entire list to verify a node exists in it.
Access: [ O(n) ]
:: Worst case, we need to iterate over the entire list to verify a node exists and return it.
insertion and deletion refer to the act of inserting rather than the iterative process to find the insertion point prior to insertion
Stack (Linked List)
Big O of Insertion, Deletion, Access and Search w/ Explanation
Insertion [ O(1) ]
:: Add to the end of the list.
Deletion: [ O(1) ]
:: Remove from the end of the list.
Search: [ O(n) ]
:: n/a
Access: [ O(n) ]
:: n/a
Linked List
What problems can a linked list solve. Give 2 example problems
Essentially any problem where we want to utilize the O(1) efficiencies of the insertion and deletion methods
Ex:
Stack (Linked List)
What problems can a linked list Implementation of a stack solve
- Essentially any problem where we want to utilize the O(1) efficiencies of the insertion and deletion methods.
- Used in function invocation order
- Used for undo / redo functionality
- Last in, first out functionality
- Ex: valid parenthesis
be more specific here later. ex: add specific
Write it, Code it, or Think it
Linked List
Insertion method
- What does the method do
- What’s the BigO
- What are the params and return values
- What are the code steps
/**
* Adds a new node to the end of this linked list.
* O(1) insertion
* @param {number} val - value of the new node
* @returns {number} - returns the size of this linked list
*/
add(val){
const newNode = new Node(val, null);
if(!this.head){
this.head = newNode
}else{
let curr = this.head;
while(curr.next){
curr = curr.next
}
curr.next = newNode
}
this.size += 1
return this.size
}Write it, Code it, or Think it
Stack (Linked List)
deletion method
- What does the method do
- What’s the BigO
- What are the params and return values
- What are the code steps
/**
* Removes the last added node
* O(1) removal
* @returns {Node}
*/
pop(){
if(!this.first) return null;
const removedNode = this.first;
if(this.size === 1) {
this.first = null;
}else{
const rest = this.first.next;
this.first = rest
}
this.size -= 1
removedNode.next = null
return removedNode
}Write it, Code it, or Think it
Stack (Linked List)
Insertion method
- What does the method do
- What’s the BigO
- What are the params and return values
- What are the code steps
/**
* Adds a node
* O(1) insertion
* @param {*} val - value of the new node
* @returns {number}
*/
push(val){
const newNode = new Node(val);
if(!this.first){
this.first = newNode;
}else{
const rest = this.first;
this.first = newNode
newNode.next = rest
}
this.size += 1;
return this.size
}Write it, Code it, or Think it
Linked List
deletion method
- What does the method do
- What’s the BigO
- What are the params and return values
- What are the code steps
/**
* Deletes a node from the list at a specific index
* O(1) deletion
* @param {number} index index of node to be deleted.
* @returns {number} removed node value
*/
delete(index){
let removedNode;
index = index < 0 ? this.size + index : index
if(!this.head) return null;
if(index >= this.size || index < 0) return null;
if(index === 0){
removedNode = this.head
this.head = this.head.next
return removedNode.val;
}
let prev = null;
let curr = this.head;
let i = 0;
while(i !== index){
prev = curr;
curr = curr.next
i+=1
}
removedNode = curr;
const rest = curr.next
prev.next = rest
this.size -= 1
return removedNode.val
}Write it, Code it, or Think it
Linked List
reverse method
- What does the method do
- What’s the BigO
- What are the params and return values
- What are the code steps
/**
* Reverses the sequence of nodes in a linked list
* @returns {LinkedList} the reversed linked list
*/
reverse(){
if(!this.head) return null
let prev = null;
let curr = this.head;
while(curr){
const next = curr.next
curr.next = prev
prev = curr
curr = next
}
this.head = prev // set this.head to the reversed list
return this.head
}Linked List
Overview
A Linked List is a data structure consisting of nodes which in themselves usually have 2 properties: a value and a next pointer. The next pointer points to the next node in the list. The last node in the leist points to null
The list itself usually has 2 properties: the head and the size.
head 5 => 19 => 3 => 90 => 1 => null
