Data Structure

What is Data Structure?

• A method that stores and manage data to easily access and utilize
• It is important to understand the advantages and limitations of the data structure and choosing the most efficient one for each condition.
• Even though each languages offers different aspects of the data structure, as long as we understand the concept, we can flexibly use them

Categories of Data Structure

• Primitive Data Structure
  Basic data type in programming
• Non-Primitive Data Structure
  A data structure that stores data efficiently depending on its purpose
  - Linear Data Structure
  Relationship of stored data between before and after is 1:1
  (ex. List, Stack, Queue)
  - Non-Linear Data Stucture
  Relationship between data elements is 1:n or n:m
  (ex. Graphs, Trees)

✔️Array(List)

Array in Javascript, List in Python
List is generally used in python. However, array and list in python is absolutely different. Both are functionally almost identical but array is more useful in memory efficiency aspect. What's easier to use? List!

Feature of Array

• Data elements are saved in order
• Mostly used when connected data elements need to be arranged in order
• Element is inserted at the end
• Mutable
• Same values can be inserted multiple times
• Multi-dimensional Array (ex. 2D Array)

Inner Structure of the Array

• Each element has its own given index number
• Index starts with 0, but the last element gets a negative index, -1.

Why does the array store data in order?

• Physically stored in order!!
• Data has its order
  1) Index starts with 0
  2) Accessing certain elements with index number
  3) Slicing from nth index to mth index

Weaknesses

1. Removing or Adding Elements

• Assume we remove a certain element in between
  
• Since each memory has to be connected in order, elements placed after the removed element should move one space forward.
• It means removing elements in the array must be slower than other type of data structures.
• Even though this code might be written in a single line, its operation gets more expensive in memory.
• Same for putting a new element in between. Elements that come after the added element have to move one space back.
• Therefore, array is not suitable for data that are frequently added or removed.

2. Array Resizing

• Since array is filled up with data in order, it allocates the certain amount of memory when it creates, which is called pre-allocation.
• If the amount of elements gets exceed the pre-allocated amount of memory, the array needs to be resized, which is to allocate more memories.
• Array resizing is relatively expensive operation.
  ex) If running out of space in 100 memories and needs to add 100 more
  🤷‍♀️Create 200 amount of memories -> copy the original 100 memories -> next data will be added starting at the index 101
• Therefore, array is not suitable for data with unexpectable size.

When to use?

• Storing data in order
  ex) Stock price >>> order beats value
• Multi-dimensional Array
• To access a certain element for real quick!
• If data size does not change rapidly
• If elements are not frequently removed or added

✔️Tuple

What is Tuple?

• Storing data in order
• Immutable
• Usually for a small amount of data
• To return more than one value in function

>>> my_tuple = (1,"2",3.0)
>>> my_tuple
(1, '2', 3.0)
>>> for i in my_tuple:
...     print(i)
...
1
2
3.0
>>> my_tuple[0]
1
>>> my_tuple[1]
'2'
>>> my_tuple[2]
3.0
>>> my_tuple[0] = 9
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>>

Why Tuple?

• To return more than one value in function
  ex) Tuple vs. Class/Object

// Tuple
[(1,2), (2,4)] // Tuple in Array(List)

// Create Table if not using Tuple
class cord:
	def __init__(self, x, y):
		self.x = x
		self.y = y

Weaknesses

• Data types are not obvious but has to assume
  by skimming through the context of the function
• To get over this weakness, Named Tuple can be used in Python

When to use?

• It takes up smaller space compared to the array
  ex) coordinates

coordinations = [
    (1, 2),
    (3, 4),
    (5, 6)
]