Introduction to Data Structures

Institutional Framework & Academic Vision

Institution: Xiamen University Malaysia
Course Code & Module: ERA 213 Data Structure (Lecture 1 - Week 1)
Vision Statement: Xiamen University Malaysia aspires to become a university with a distinct global outlook, featuring first-class teaching and research, and embracing cultural diversity.
Mission Statement: To nurture young talents with dignity and wisdom, turning them into fine citizens of the region who will contribute to the prosperity of the people and social progress of Malaysia, China and Southeast Asia.

Role of Data Structures in Robotics

Robotics Applications of Data Structures

Data structures serve as the foundational architecture enabling robots to process environmental inputs and make autonomous decisions effectively.

Sensor History → List / Array:
- Robots store recent sensor readings, images, and measurements sequentially in order.
- Example sequence of sensor data values: 0.12, 0.15, 0.14, 0.20, 0.18.
- Example implementation syntax: readings.append(new_value) to append a new sensor reading.
Command Processing → Queue:
- Incoming sensor messages and motion commands (FORWARD, LEFT, STOP, PICK) are processed strictly in their arrival order using First In, First Out (FIFO) logic.
- Example Python implementation syntax: from collections import deque.
Backtracking / Path Reversal → Stack:
- When encountering a dead end during exploration (A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ Dead end!), a robot backtracks step by step using Last In, First Out (LIFO) logic.
- Example implementation syntax: path.pop() to remove and return to the last recorded position.
Map Representation & Navigation → Graph:
- Robotic environments are mapped as nodes representing physical locations (Room A, Corridor, Room B, Charging Dock) connected by edges for path planning.
- Common path planning algorithms: Breadth-First Search (BFS), Depth-First Search (DFS), and $A^*$ (A-Star).
Robot State & Fast Parameter Lookup → Dictionary / Hash Table:
- Provides fast direct access to system parameters and state variables:
- 'battery' $\rightarrow$ '82%'
- 'mode' $\rightarrow$ 'AUTO'
- 'x' $\rightarrow$ 3.4
- 'y' $\rightarrow$ 7.1
- 'target' $\rightarrow$ 'box'
- 'gripper' $\rightarrow$ 'closed'
- Example retrieval syntax: state['battery'] for fast lookup by key.
Urgent Task Scheduling → Priority Queue:
- Resolves execution order when multiple concurrent events occur based on task urgency:
1. Priority 1 (Obstacle Avoidance): Stop or replan trajectory immediately.
2. Priority 2 (Delivery Task): Navigate to target destination.
3. Priority 3 (Logging): Write system diagnostic data to disk.

Impact of Data Structures on Robotic Software Systems

Systems Without Structured Data Structures:
- Relies on unstructured code, arbitrary state flags, and unorganized variables (e.g., messy conditional blocks if x == 1:).
- Results in slow processing times, difficult debugging, poor code modularity, and error-prone programs.
Systems With Structured Data Structures:
- Utilizes clean abstractions (e.g., queue = deque(), state = {'battery': 82}, path = []).
- Ensures organized data management, rapid real-time decision making, maintainable codebases, and robust robotics applications.

Core Definitions and Conceptual Foundations

Data Structure Definition: A data structure is a systematic way of organizing, storing, and managing data in a computer so that it can be accessed, modified, and processed efficiently.
Structural Role: Data structures govern how individual elements are arranged, how links are established, and how operations interact with the stored data.
Dual Facets of Data Structures:
- Logical Structure (Abstraction): The conceptual view of the data model and relationships independent of implementation (e.g., linear sequence, tree hierarchy, network graph).
- Storage Structure (Physical Memory Layout): The underlying implementation in physical RAM (e.g., contiguous array blocks, scattered nodes connected via memory pointers).

Taxonomy and Classification of Data Structures

Data structures are categorized into two major classes: Primitive and Non-Primitive Data Structures.

Primitive Data Structures:
- Basic, built-in data types provided directly by programming languages to store single values.
- Examples & Sample Values:
- Integer: $-2, 0, 4, 5$
- Float: $2.1, 4.05$
- Character: $\text{'A'}, \text{'b'}, \text{'c'}, \text{'D'}$
- Pointer: Holds absolute memory addresses.
Non-Primitive Data Structures:
- Complex structures constructed using primitive types, capable of storing multiple values and defining complex relationships between elements.
- Linear Data Structures: Elements are organized in a sequential, 1D order. Every element (except the first and last) possesses exactly one predecessor and one successor.
- Array
- Linked List
- Stack
- Queue
- Non-Linear Data Structures: Elements are organized hierarchically or in a network topology, allowing single elements to connect to multiple other elements.
- Graph
- Trees

Abstract Data Type (ADT)

ADT Definition: An Abstract Data Type defines the high-level specification of a data structure, separating what operations can be performed from how those operations are implemented.
Formula: $\text{ADT} = \text{Interface} + \text{Contract}$
List ADT Specification Example in C:
- Function signatures defining the interface:
- void init(Array *a): Initialize the list.
- void append(Array *a, int value): Append an item to the end.
- int get(Array *a, int index): Retrieve element at target index.
- void freeArray(Array *a): Free allocated memory.
Decoupling Implementation: Multiple concrete storage structures (such as contiguous arrays or linked node lists) can implement the exact same ADT interface.

Fundamental Data Structure Implementations

Arrays

Array Bookshelf Analogy

Definition: An array is a linear collection of elements of the same data type stored in continuous, contiguous memory locations.
Core Characteristics:
- Stores homogeneous data (identical type).
- Random access via zero-based indexing.
- Fixed static size defined at memory allocation.
Declaration Syntax in C: int arr[10];
- int: Data type of elements.
- arr: Variable name.
- 10: Fixed number of elements allocated.
Indexing & Memory Calculation:
- First index: arr[0]
- Last index for array of length $n$ : arr[n-1]
- Length Formula: $\text{Length} = (\text{Upper Bound} - \text{Lower Bound}) + 1$
- Calculation Example for indices 0 to 9: $(9 - 0) + 1 = 10$
C Processing Example:

#include <stdio.h>

int main() {
    int myNumbers[] = {25, 50, 75, 100};

    // Access first element (index 0)
    printf("%d
", myNumbers[0]); // Outputs: 25

    // Modify second element (index 1)
    myNumbers[1] = 60;
    printf("%d
", myNumbers[1]); // Outputs: 60

    return 0;
}

Common Operations: Creation, Traversal, Insertion, Deletion, Modification, Merging.
Dimensional Hierarchy:
- 1D Array: Traversed via 1 single loop.
- 2D Array: Matrix format traversed via 2 nested loops.
- n-D Array: Hyper-dimensional matrices used in machine learning, requiring $n$ nested loops.

Linked Lists

Array vs Linked List Representation

Types of Linked List

Definition: A dynamic data structure consisting of nodes connected sequentially via explicit pointers. Memory allocation is non-contiguous.
Node Structure:
- Data Field: Stores payload information (integer, float, character, etc.).
- Pointer Field: Stores memory address pointing to the subsequent node.
C Node Structure Definition:

#include <stdio.h>
#include <stdlib.h> // Required for malloc() and free()

struct Node {
    int data;
    struct Node* next;
};

Operational Mechanics: Insertion and deletion do not require element-shifting (unlike arrays). However, random access is not supported; accessing elements requires sequential pointer traversal starting from the Head node.
Varieties of Linked Lists:
- Singly Linked List: Uni-directional pointer chain where each node points only to the next.
- Doubly Linked List: Bi-directional chain where each node contains both a next pointer and a prev pointer.
- Circular Linked List: The next pointer of the final node points directly back to the Head node.
- Doubly Circular Linked List: Combines bi-directional pointers with a closed-loop structure connecting tail and head nodes.

Stacks

Stack Operation Mechanics

Definition: A linear data structure in which insertions and deletions occur strictly at a single termination point called the Top.
Governing Property: Last In, First Out (LIFO).
Core Operations:
- PUSH: Insert element onto the Top of the stack.
- POP: Remove element from the Top of the stack.
- TOP: Pointer referencing the most recently added element.
- Base: Fixed, immutable bottom boundary of the stack.
Operational Tracing Example:
- Step 1: PUSH(A) $\rightarrow$