Ai-CompTech

AI Computing

Computer Science Fundamentals

Data Structures: Arrays and Linked Lists

Master fundamental linear data structures and their operations

Intermediate 60 min read 0 examples 0 quiz questionsID: 6962f8f9
Lesson Content

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

code
class 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.

code
class 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.

code
class 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

code
def insert_at_beginning(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node

2. Delete a Node

code
def 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

code
def 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

  1. Reverse an array in-place
  2. Find duplicate elements in array
  3. Reverse a linked list
  4. Detect cycle in linked list
  5. Find middle element of linked list
  6. Merge two sorted arrays
  7. Remove duplicates from linked list