Please enable JavaScript.
Coggle requires JavaScript to display documents.
Data Structure - Coggle Diagram
Data Structure
Linear
Array
overview
operations
delete
O(n)
look-up
by index
O(1)
by value
O(n)
insert
O(n)
can get full
move to new array
stored sequentially in mem
in java
fixed size
can't be changed
static
full
copy to new array
O(n)
dynamic array
Vector
grow 100% if full
synchronized
single thread can access
ArrayList
grow 50%
building an array
new Array(size)
insert(value)
removeAt(index)
print()
indexOf(value)
LinkedList
what
group of nodes
node
next node
value
operations
look up
O(n)
insert
head
O(1)
tail
O(1)
middle
O(n)
delete
head
O(1)
middle
O(n/2)
tail
O(n)
reverse
O(n)
types
Doubly
Singly
Curcular
music playler
start over
in java
LinkedList
toArray()
DoublyLinkedList
Stack
what
apps
undo feature
syntax checking
evaluate expressions
navigation
forward
back
metaphor
stack of books
LIFO
operations (all O(1))
push
pop
peek
isEmpty
how
implementation
wrapper
array
linkedlist
inverview
reverse string
balanced expression
implement
Queue
what
apps
web server
printer
OS
FIFO
process in order
consumers
resources
how
operations (O(1))
enqueue
dequeue
isEmpty
peek
isFull
in Java
Queue is Interface
implementations
ArrayDeque
double ended
LinkedList
operations
enqueue
add
offer
dequeue
remove
poll
peek
peek
element
interview
reverse a queue
implement
array
circular array
linkedlist
stack
priority queue
implementations
array
shift array to right
start from right
heap
sorted by priority
HashTable
what
apps
spell checkers
dictionaries
compilers
function & var look-up
code editors
fast look-up
how
hash func
deterministic
same input same output
variations
HashMap
java
Object
js
Dictionary
python
C#
operations (O(1))
insert
look-up
delete
in java
Map Interface
operations
remove
get
containsKey
containsValue
put
foreach
entrySet
keySet
implementations
HashMap
key - value
Set Interface
HashSet
how
hash func
implement
collision
chaining
linkedlist
open addressing
linear probing
next slot
cons
will get full
long cluster
quad probing
Non-Linear
Tree
Graph
String in Java
StringBuffer
when
a lot string manipulations
methods
append()
toString()
why
string is immutable
operations are costly
loop each char
for
can't foreach
toCharArray() first
Big O
measure performance
if input grows large
scale
O(1)
O(200)
O(n)
O(100 + n)
O(m + n)
O(n^2)
2 loops
O(n^2 + n)
O(n^3)
O(log n)
reduce half work every step
O(2^n)
exponential
space complexity