Introduction

In Computer Science, data structures and algorithms are fundamental concepts used in organizing and manipulating data efficiently. Data structures refer to the way data is organized, stored, and accessed in a computer system, while algorithms are step-by-step procedures for solving problems using these data structures.

Arrays

• Definition: An array is a collection of elements stored in contiguous memory locations and accessed using an index.
• Example: Consider an array $A = [5, 8, 3, 2, 7]$. Accessing the element at index 2 would yield 3.

Linked Lists

• Definition: A linked list is a data structure consisting of nodes where each node contains a data field and a reference to the next node.
• Example: A singly linked list: $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$, where each node points to the next one.

Stacks

• Definition: A stack is a data structure that follows the Last-In-First-Out (LIFO) principle, where elements are added and removed from the top.
• Example: Pushing elements 1, 2, and 3 onto a stack, then popping elements would result in 3, 2, 1.

Queues

• Definition: A queue is a data structure that follows the First-In-First-Out (FIFO) principle, where elements are added at the rear and removed from the front.
• Example: Enqueuing elements 1, 2, and 3 into a queue, then dequeuing elements would result in 1, 2, 3.

Trees

• Definition: A tree is a hierarchical data structure consisting of nodes connected by edges, with a root node at the top.
• Example: An example of a binary tree with nodes and edges linking them.

Common Mistakes

• Mixing up array and linked list operations.
• Forgetting to check if a stack or queue is empty before popping or dequeuing.
• Incorrectly implementing tree traversal algorithms.

Key Points

• Understanding data structures helps in efficient data storage and retrieval.
• Algorithms are essential for solving computational problems effectively.
• Practicing implementation of data structures and algorithms is crucial for mastery.

Practice Questions

1. Explain the difference between arrays and linked lists.

   Answer: Arrays store elements in contiguous memory locations and are accessed using indices, while linked lists store elements in nodes with references to the next node.

2. Implement a stack using an array in Python.

   Answer:

   class Stack:
       def __init__(self):
           self.stack = []
   
       def push(self, item):
           self.stack.append(item)
   
       def pop(self):
           if not self.is_empty():
               return self.stack.pop()
           return None
   
       def is_empty(self):
           return len(self.stack) == 0
   

3. Describe the process of tree traversal using the inorder method.

   Answer: In inorder traversal, we first visit the left subtree, then the root node, and finally the right subtree.

4. Compare the time complexity of accessing elements in an array versus a linked list.

   Answer: Accessing elements in an array is done in constant time $O(1)$, while in a linked list, it is done in linear time $O(n)$.

5. Explain the concept of a queue and provide an application where a queue would be useful.

   Answer: A queue is a linear data structure where elements are added at the rear and removed from the front. An application where a queue is useful is in CPU scheduling where processes are lined up and executed in a FIFO manner.

6. Write a function in C++ to reverse a linked list.

   Answer:

   Node* reverseLinkedList(Node* head) {
       Node* prev = nullptr;
       Node* curr = head;
       Node* next = nullptr;
   
       while (curr != nullptr) {
           next = curr->next;
           curr->next = prev;
           prev = curr;
           curr = next;
       }
   
       return prev;
   }
   

7. Discuss the importance of trees in data structures and provide an example of a real-world application where trees are used.

8. Implement a queue using two stacks in Java.

   Answer:

   class QueueUsingStacks {
       Stack<Integer> stack1 = new Stack<>();
       Stack<Integer> stack2 = new Stack<>();
   
       public void enqueue(int item) {
           stack1.push(item);
       }
   
       public int dequeue() {
           if (stack2.isEmpty()) {
               while (!stack1.isEmpty()) {
                   stack2.push(stack1.pop());
               }
           }
           return stack2.pop();
       }
   }
   

These revision notes cover the key concepts of data structures and algorithms, essential for Grade 12 students preparing for their Computer Science exams under the Kenyan CBC curriculum. Practice the provided questions to solidify your understanding of the topic.