
AI Computing
Data Structures: Arrays and Linked Lists
Data structures organize data for efficient access, modification, and storage.
Why Data Structures Matter
Performance: Right structure = faster programs Scalability: Handle millions of records efficiently Problem Solving: Each structure solves specific problems Interviews: Core topic in technical interviews
Arrays
Definition
A collection of elements stored at contiguous memory locations, accessed by index.
Characteristics
- Fixed size (in most languages like C, Java)
- Fast access: O(1) - direct index lookup
- Same data type: All elements must be homogeneous
- Memory efficient: No extra pointers needed
Operations & Time Complexity
| Operation | Time Complexity | Explanation | |-----------|----------------|-------------| | Access | O(1) | Direct index calculation | | Search | O(n) | Check each element | | Insert (end) | O(1) | If space available | | Insert (middle) | O(n) | Shift elements | | Delete | O(n) | Shift elements |
Python Examples
code# Create array arr = [10, 20, 30, 40, 50] # Access element print(arr[2]) # Output: 30 (3rd element) # Modify element arr[1] = 25 # [10, 25, 30, 40, 50] # Length print(len(arr)) # 5 # Append (add to end) arr.append(60) # [10, 25, 30, 40, 50, 60] # Insert at position arr.insert(2, 27) # [10, 25, 27, 30, 40, 50, 60] # Remove element arr.remove(27) # [10, 25, 30, 40, 50, 60] # Search if 30 in arr: print("Found!") # Iterate for num in arr: print(num)
Multi-Dimensional Arrays
code# 2D Array (Matrix) matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] print(matrix[1][2]) # 6 (row 1, col 2) # 3D Array cube = [[[1, 2], [3, 4]], [[5, 6], [7, 8]]]
Advantages
✅ Fast random access ✅ Memory efficient ✅ Simple to use ✅ Cache friendly (contiguous memory)
Disadvantages
❌ Fixed size ❌ Expensive insertion/deletion ❌ Memory wastage if not full
Linked Lists
Definition
A linear data structure where elements (nodes) are connected via pointers/references.
Node Structure
codeclass Node: def __init__(self, data): self.data = data # Value self.next = None # Pointer to next node
Types of Linked Lists
1. Singly Linked List
Each node points to the next node only.
codeclass SinglyLinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if not self.head: self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node def display(self): current = self.head while current: print(current.data, end=" -> ") current = current.next print("None")
2. Doubly Linked List
Nodes have pointers to both next and previous nodes.
codeclass DoublyNode: def __init__(self, data): self.data = data self.next = None self.prev = None # Pointer to previous
3. Circular Linked List
Last node points back to first node.
Common Operations
1. Insert at Beginning
codedef insert_at_beginning(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node
2. Delete a Node
codedef delete_node(self, key): current = self.head # If head needs to be deleted if current and current.data == key: self.head = current.next return # Search for the node prev = None while current and current.data != key: prev = current current = current.next # If key not found if not current: return # Unlink the node prev.next = current.next
3. Search
codedef search(self, key): current = self.head position = 0 while current: if current.data == key: return position current = current.next position += 1 return -1 # Not found
Time Complexity
| Operation | Time | Why | |-----------|------|-----| | Access | O(n) | Must traverse from head | | Search | O(n) | Check each node | | Insert (beginning) | O(1) | Just update head | | Insert (end) | O(n) | Traverse to end | | Delete | O(n) | Find node first |
Advantages
✅ Dynamic size ✅ Efficient insertion/deletion ✅ No memory waste ✅ Can implement stacks/queues
Disadvantages
❌ No random access ❌ Extra memory for pointers ❌ Not cache friendly ❌ Reverse traversal hard (singly)
Array vs Linked List
| Feature | Array | Linked List | |---------|-------|-------------| | Memory | Contiguous | Scattered | | Size | Fixed | Dynamic | | Access | O(1) | O(n) | | Insert/Delete | O(n) | O(1) | | Memory Usage | Less | More (pointers) | | Use Case | Known size, frequent access | Unknown size, frequent insert/delete |
Real-World Applications
Arrays
- Image storage (pixels)
- Game boards (chess, tic-tac-toe)
- Database tables
- Matrices in math/physics
- Buffers in memory
Linked Lists
- Music/video playlists
- Browser history (back/forward)
- Undo functionality
- Hash table chaining
- Operating system task scheduling
Practice Problems
- Reverse an array in-place
- Find duplicate elements in array
- Reverse a linked list
- Detect cycle in linked list
- Find middle element of linked list
- Merge two sorted arrays
- Remove duplicates from linked list