Data Structures and Algorithms: Detailed Material
Dictionaries
Definition: A dictionary is a collection of key-value pairs where each key is unique and maps
to a specific value.
Applications: Used in databases, caching, and indexing.
Example in Python:
```python
# Dictionary example
my_dict = {'name': 'Alice', 'age': 25, 'city': 'New York'}
print(my_dict['name']) # Accessing value
my_dict['age'] = 26 # Updating value
print(my_dict)
```
Abstract Data Types (ADT)
Definition: ADTs define data types by their behavior (operations) rather than their
implementation.
Examples:
1. List ADT: Supports operations like insertion, deletion, traversal, and searching.
2. Stack ADT: Follows LIFO (Last In, First Out).
3. Queue ADT: Follows FIFO (First In, First Out).
List ADT
Definition: A collection of elements arranged in a linear sequence.
Operations: Access by index, insertion, deletion, and searching.
Implementations:
- Array-based: Fixed size, faster access by index.
- Linked List-based: Dynamic size, faster insertion/deletion.
Example in Python:
```python
# List operations in Python
my_list = [10, 20, 30]
my_list.append(40) # Insert
my_list.remove(20) # Delete
print(my_list[1]) # Access by index
```
Stack ADT
Definition: A collection of elements where insertion and deletion happen only at one end
(the top).
Operations:
- `push()`: Add an element.
- `pop()`: Remove the top element.
- `peek()`: View the top element.
Example in Python:
```python
# Stack implementation using list
stack = []
stack.append(10) # Push
stack.append(20)
print(stack.pop()) # Pop
print(stack[-1]) # Peek
```
Queue ADT
Definition: A collection of elements where elements are added at the rear and removed from
the front.
Types:
1. Simple Queue: FIFO.
2. Circular Queue: Connects the rear to the front.
3. Priority Queue: Elements dequeued based on priority.
Example in Python:
```python
from collections import deque
queue = deque()
queue.append(10) # Enqueue
queue.append(20)
print(queue.popleft()) # Dequeue
```
Hash Table Representation
Definition: A data structure that maps keys to values using a hash function.
Efficiency: Average-case time complexity for insertion, deletion, and search is O(1).
Example in Python:
```python
# Hash table using dict
hash_table = {}
hash_table['key1'] = 'value1'
print(hash_table['key1'])
```
Hash Functions
Purpose: Converts a key into an index for efficient storage and retrieval.
Properties:
- Deterministic: Always returns the same hash for a given key.
- Uniform distribution: Avoids clustering.
Example:
```python
# Hash function in Python
def simple_hash(key, table_size):
return key % table_size
print(simple_hash(10, 7))
```
Collision Resolution
Methods to resolve collisions:
1. Separate Chaining:
- Uses linked lists at each index to store multiple keys.
Example in Python:
```python
# Separate chaining using list of lists
hash_table = [[] for _ in range(7)]
def insert(key, value):
index = key % len(hash_table)
hash_table[index].append((key, value))
insert(10, 'value1')
insert(17, 'value2')
print(hash_table)
```
2. Open Addressing:
- Stores all keys in the table itself. Methods include linear probing and double hashing.
Example in Python:
```python
# Linear probing example
hash_table = [None] * 7
def insert(key, value):
index = key % len(hash_table)
while hash_table[index] is not None:
index = (index + 1) % len(hash_table)
hash_table[index] = (key, value)
insert(10, 'value1')
insert(17, 'value2')
print(hash_table)
```
