# DSA Week 2 : Understanding Essential Data Structures: Types, Uses, and Performance
Data structures can be broadly categorized into two types: linear and non-linear data structures. Each type has its own characteristics, advantages, and use cases. Here's an overview of both:
### Linear Data Structures
In linear data structures, the elements are arranged in a sequential order, and each element is connected to its previous and next element. Linear data structures are easy to implement because of their simple organization. They are widely used for basic operations like traversal, insertion, and deletion.
**Examples of Linear Data Structures:**
1. **Array**:
* A collection of elements stored in contiguous memory locations.
* Fixed size.
* Allows random access to elements.
* Example: `[1, 2, 3, 4, 5]`
![](https://miro.medium.com/v2/resize:fit:927/1*DxlJoSM_VaoeHQEaPnFT5g.png align="center")
**Python Example**:
```python
arr = [1, 2, 3, 4, 5]
print(arr[2]) # Output: 3
```
2. **Linked List**:
* A collection of nodes where each node contains a data part and a reference to the next node.
* Can be singly linked, doubly linked, or circular.
* Dynamic size.
* Example: `1 -> 2 -> 3 -> 4 -> 5`
3. ![](https://media.geeksforgeeks.org/wp-content/uploads/20220712172013/Singlelinkedlist.png align="right")
4. **Python Example**:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
last = self.head
while last.next:
last = last.next
last.next = new_node
def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list() # Output: 1 -> 2 -> 3 -> None
```
5. **Stack**:
* Follows Last In First Out (LIFO) principle.
* Supports operations like push (add an element), pop (remove the top element), and peek (get the top element).
* Example: Stack of plates.
![](https://media.geeksforgeeks.org/wp-content/uploads/geek-stack-1.png align="center")
**Python Example**:
```python
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop()) # Output: 3
```
6. **Queue**:
* Follows First In First Out (FIFO) principle.
* Supports operations like enqueue (add an element to the end), dequeue (remove an element from the front).
* Example: Line of people.
![](https://media.geeksforgeeks.org/wp-content/uploads/20220816162225/Queue.png align="center")
**Python Example**:
```python
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue.popleft()) # Output: 1
```
## 5 . Hash map (non-linear data structure .)
A hash map, also known as a hash table, is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. Here are some key points about hash maps:
1. **Hash Function**: This is a function that converts keys into array indices. It typically maps large keys to smaller values, like converting strings or numbers into an index in an array.
2. **Collision Handling**: Since multiple keys can hash to the same index (collision), hash maps use various strategies to handle collisions, such as chaining (where each bucket is a linked list of entries) or open addressing (where collisions are resolved by probing).
3. **Efficiency**: Hash maps provide efficient average-case time complexity for lookups, inserts, and deletes, typically O(1) under ideal conditions. However, worst-case scenarios can degrade to O(n) due to collisions or poor hash functions.
4. **Usage**: Hash maps are widely used in programming for tasks like implementing associative arrays, database indexing, caching, and in various algorithms for fast data access.
5. **Implementation**: Implementing a hash map involves designing a good hash function, choosing a collision resolution strategy, and managing load factors (the ratio of entries to buckets) to maintain efficiency.
![](https://www.boardinfinity.com/blog/content/images/2023/03/HashMap-in-Python.png align="center")
In languages like Python, Java, and many others, hash maps are often provided as standard library collections (e.g., Python's `dict`, Java's `HashMap`), making them convenient and efficient for everyday use.
```python
# Creating a hash map (dictionary)
hash_map = {}
# Adding key-value pairs to the hash map
hash_map['apple'] = 10
hash_map['banana'] = 20
hash_map['cherry'] = 30
# Accessing values using keys
print("Value of 'apple':", hash_map['apple'])
print("Value of 'banana':", hash_map['banana'])
# Updating a value
hash_map['banana'] = 25
print("Updated value of 'banana':", hash_map['banana'])
# Deleting a key-value pair
del hash_map['cherry']
print("After deleting 'cherry':", hash_map)
# Checking if a key exists
if 'apple' in hash_map:
print("'apple' is present in the hash map")
# Iterating through keys and values
print("Iterating through keys and values:")
for key, value in hash_map.items():
print(key, "->", value)
```
💡
yay we completed the basic data structure
## use case of the this data structure
* **Arrays**:
* Efficient storage and retrieval of a collection of elements.
* Suitable for scenarios where elements are accessed by index.
* Used in implementing lists, matrices, and vectors.
* **Linked Lists**:
* Dynamic insertion and deletion of elements without shifting elements.
* Ideal for applications requiring frequent insertions and deletions.
* Used in implementing stacks, queues, and adjacency lists for graphs.
* **Stacks**:
* Last In, First Out (LIFO) data structure.
* Used in function call management (recursion), expression evaluation (postfix notation), and undo mechanisms.
* **Queues**:
* First In, First Out (FIFO) data structure.
* Useful in job scheduling, breadth-first search algorithms, and buffering of messages.
* **Hash Maps (Dictionaries)**:
* Efficient key-value pair storage and retrieval.
* Used in implementing associative arrays, database indexing, and caching mechanisms.
💡
Note : actual every data stucture solve some problem . the problem is actual efficiently use our memory . i will further upload articel on how data structure work behind it .