Data Structure
Topics
- List
- Set
- Map
- Stack
- Queue
Why do we learn Data structure?
- to store data and process data efficiently.
List
Can store single data type of many object
Two Types of Lists
- Array List
- Linked List
Array List
List that uses Array as internal function.
var array = new int[10];
Pros
O(1)
- To get
- To access
Cons
O(n)
-
Insersation
-
Deletion -> has to shift values
-
Search
Lincked List
List that uses "Node" as internal function
Pros
O(n)*O(1)
-
Insertion
-
Deletion
-
Append
Cons
O(n)
- Get
- Search
Two Types of Lincked Lists
Singly Lincked List
- Head
Doubly Lincked List
-Head
-Tail
Set
- Orderless
- no duplicates
What cases we can use?
Ex) Types of car, cakes...
Map
- Orderless
Dictionary in pyton
Key-Value Set
cakePriceMap = {"CheesesCake": 190, "ChocolateCake": 220, "PlainCake": "120", "StroberryCake": 250}
cakePriceMap.get("CheesesCake") returns 190
CalculateMemoryPosition("CheesesCake") -> Memory Position
Runtime
cakeList = ["CheesesCake", "ChocolateCake", "PlainCake", "StroberryCake"] priceList = [190, 220, 250, 320]
List Search -> O(n)
Map Search -> O(1)
Search -> O(1) Insertion -> O(1) Deletion -> O(1) Access -> O(1)
Cons
- Lower storage efficiency
- Collision
- Lower runtime
- 75 %
- depends on Quolity of Hash function
- Orderless
HashMap
Uses Hash function to calculate memory position
Stack
FILO
LIFO
積み重ねる
Queue
FIFO