Data Structures - Unit 3: Arrays & Linked Lists
1. Arrays
- Definition: Collection of elements of same type stored at contiguous memory locations.
- Types: 1D Array, 2D Array, Multi-Dimensional Array
Advantages:
- Easy to access elements using index
- Efficient memory usage
Disadvantages:
- Fixed size
- Insertion & deletion costly (except at end)
Example (Python):
# 1D Array Example
arr = [10, 20, 30, 40, 50]
print(arr[2]) # Output: 30
# 2D Array Example
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(matrix[1][2]) # Output: 6
Operations:
- Traversal, Insertion, Deletion, Searching, Updating
2. Linked Lists
- Definition: Linear data structure where elements (nodes) are connected using pointers.
- Types: Singly Linked List, Doubly Linked List, Circular Linked List
Node Structure (Python):
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
Singly Linked List Example:
# Creating nodes
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
# Linking nodes
[Link] = node2
[Link] = node3
# Traversal
current = node1
while current:
print([Link], end=' -> ')
current = [Link]
# Output: 10 -> 20 -> 30 ->
Advantages:
- Dynamic size
- Easy insertion & deletion
Disadvantages:
- Extra memory for pointers
- Sequential access, slower than arrays
Examples & Exercises:
1. Implement a function to insert a node at the beginning of a linked list.
2. Implement a Python function to delete an element from an array.
3. Write a Python program to find the sum of elements in a 2D array.