Introduction

Data structures are essential concepts in computer science that allow us to organize and manipulate data efficiently. In this topic, we will explore various data structures that are commonly used in programming to store and manage data.

Arrays

An array is a data structure that stores a collection of elements of the same data type in contiguous memory locations. Each element in an array is accessed by its index.

Key Terms:

• Element: Each individual data value stored in the array.
• Index: A unique number used to access a specific element in the array.

Example:

Consider an array $A$ with elements $[5, 8, 3, 2, 7]$. To access the third element in the array, we use the index 2 (indices start from 0), so $A[2] = 3$.

Linked Lists

A linked list is a data structure consisting of nodes where each node contains data and a reference (link) to the next node in the sequence.

Key Terms:

• Node: Represents a single element in the linked list.
• Pointer: A reference to the next node in the sequence.

Example:

Let's create a simple linked list with nodes containing values: $[3 \rightarrow 7 \rightarrow 5]$. Here, 3 is the first node, which points to 7, and 7 points to 5.

graph LR
A(3) --> B(7)
B --> C(5)

Stacks

A stack is a data structure that follows the Last In, First Out (LIFO) principle, where elements are inserted and deleted from the same end, typically called the top.

Key Terms:

• Push: Adding an element to the top of the stack.
• Pop: Removing the top element from the stack.

Example:

Let's perform push and pop operations on a stack with elements $[2, 5, 8]$.

• After pushing 10: $[2, 5, 8, 10]$
• After popping: $[2, 5, 8]$

Queues

A queue is a data structure that follows the First In, First Out (FIFO) principle, where elements are inserted at the rear and deleted from the front.

Key Terms:

• Enqueue: Adding an element to the rear of the queue.
• Dequeue: Removing an element from the front of the queue.

Example:

Consider a queue with elements $[4, 6, 9]$.

• After enqueueing 2: $[4, 6, 9, 2]$
• After dequeuing: $[6, 9, 2]$

Trees

A tree is a hierarchical data structure consisting of nodes connected by edges. It has a root node and child nodes.

Key Terms:

• Root: The topmost node of the tree.
• Parent: A node connected to one or more child nodes.
• Child: A node connected to its parent node.

Example:

Let's represent a simple tree with nodes:

       1
      / \
     2   3
    / \
   4   5

Graphs

A graph is a non-linear data structure consisting of nodes (vertices) and edges that connect these nodes.

Key Terms:

• Vertex: Represents a node in a graph.
• Edge: Represents a connection between two vertices.

Example:

Consider a graph with vertices $[A, B, C]$ and edges $[(A, B), (B, C)]$.

Common Mistakes

• Forgetting to initialize data structures before using them.
• Incorrectly updating pointers in linked lists.
• Mixing up push and pop operations in stacks.
• Not considering the order of elements in queues.
• Failing to define appropriate relationships between nodes in trees or graphs.

Key Points

• Data structures are essential for efficient data organization and manipulation.
• Each data structure has specific operations and characteristics that determine its usage.
• Understanding the relationships between elements in a data structure is crucial for proper implementation.
• Choosing the right data structure depends on the requirements of the specific problem.

Practice Questions

1. Explain the difference between an array and a linked list.
2. Perform the push and pop operations on a stack with elements $[3, 6, 9]$.
3. Enqueue the elements $[7, 4, 2]$ into a queue and then dequeue two elements.
4. Draw a tree with nodes $[1, 2, 3, 4]$ where node 2 is the parent of nodes 1 and 3.
5. Create a graph with vertices $[A, B, C, D]$ and edges $[(A, B), (B, C), (C, D)]$.

Practice Question 1:

The difference between an array and a linked list lies in how the elements are stored in memory. An array stores elements in contiguous memory locations, allowing for fast random access, while a linked list uses nodes with references to the next node, enabling dynamic memory allocation and insertion/deletion operations.

Practice Question 2:

• After pushing 10: $[3, 6, 9, 10]$
• After popping: $[3, 6, 9]$

Practice Question 3:

• After enqueueing $[7, 4, 2]$: $[7, 4, 2]$
• After dequeuing twice: $[2]$

Practice Question 4:

       2
      / \
     1   3
           \
            4

Practice Question 5:

         A -- B -- C -- D