Data Structures Class Notes: Introduction to Arrays and Linked Lists
Course: Fundamentals of Data Structures
Date: August 2025
Instructor: Prof. Michael Lee
Institution: Virtual Institute of Computer Science
---
1. Introduction to Data Structures
Data structures organize and store data efficiently for computation. This set of
notes introduces arrays and linked lists, foundational data structures used in
programming, with examples and applications.
2. Arrays
- Definition: A fixed-size, contiguous block of memory storing elements of the same
type.
- Properties:
- Constant-time access: O(1) for accessing elements by index.
- Fixed size: Cannot resize dynamically.
- Example: Storing exam scores for 50 students.
- Operations:
- Access: scores[3] retrieves the 4th score.
- Update: scores[3] = 95 updates the 4th score.
- Insertion/Deletion: Slow (O(n)) due to shifting elements.
3. Linked Lists
- Definition: A sequence of nodes, each containing data and a reference to the next
node.
- Types:
- Singly Linked List: Each node points to the next.
- Doubly Linked List: Nodes point to both next and previous.
- Properties:
- Dynamic size: Grows/shrinks as needed.
- Slow access: O(n) for accessing elements.
- Example: Managing a playlist of songs.
- Operations:
- Insertion: Add a node (O(1) at head, O(n) elsewhere).
- Deletion: Remove a node (O(1) at head, O(n) elsewhere).
- Traversal: Iterate through nodes.
4. Example Implementation in Python
- Array (using Python list):
```
scores = [85, 90, 78, 92] # Array of exam scores
print(scores[2]) # Output: 78
scores.append(88) # Add score at end
```
- Singly Linked List:
```
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
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")
playlist = LinkedList()
playlist.append("Song A")
playlist.append("Song B")
playlist.display() # Output: Song A -> Song B -> None
```
5. Applications
- Arrays: Used in image processing (pixel grids), databases (fixed-size records).
- Linked Lists: Used in memory management, task scheduling, browser history.
6. Performance Comparison
- Arrays: Fast for random access, slow for insertions/deletions.
- Linked Lists: Fast for insertions/deletions at known positions, slow for
searching.
- Example: Choose arrays for static data (e.g., monthly sales), linked lists for
dynamic data (e.g., real-time event logs).
7. Common Challenges
- Arrays: Memory waste if size is overestimated; resizing requires copying.
- Linked Lists: Memory overhead due to storing pointers; cache inefficiency.
- Solutions: Use dynamic arrays (e.g., Python lists) or optimize linked list
traversal.
8. Study Tips
- Practice implementing arrays and linked lists in Python or C++.
- Solve problems on platforms like LeetCode (e.g., "Reverse a Linked List").
- Visualize data structures using diagrams to understand memory layout.
9. Further Resources
- Read “Introduction to Algorithms” by Cormen et al. for deeper insights.
- Explore online tutorials on GeeksforGeeks or Coursera.
- Join coding communities on X for problem-solving discussions.
---
These notes are ideal for computer science students or programmers learning data
structures. Practice coding and solving problems to master these concepts.
