Data Structures

What are Data Structures?

Data structures are specialized formats for organizing, processing, retrieving, and storing data. They provide efficient ways to access and modify data based on specific use cases.

Why Data Structures Matter

Efficient data organization
Fast search and retrieval
Optimal memory usage
Problem-specific solutions
Algorithm optimization

Arrays (Lists)

Arrays are the most fundamental data structure - a collection of elements stored in contiguous memory locations. In Spindle, we use lists which behave like arrays.

Creating Arrays

Arrays can store any type of data: numbers, strings, or even mixed types.

creating_arrays.spdl

# Creating different types of arrays
numbers <- [1, 2, 3, 4, 5]
names <- ["Alice", "Bob", "Charlie"]
mixed <- [1, "hello", 3.14, 0]
DISPLAY("Numbers array: ")
DISPLAY(numbers)
DISPLAY("Names array: ")
DISPLAY(names)
DISPLAY("Mixed array: ")
DISPLAY(mixed)

Accessing Array Elements

Array elements are accessed using their index. Spindle uses 1-based indexing, meaning the first element is at index 1.

accessing_elements.spdl

# Accessing elements (1-based indexing)
numbers <- [10, 20, 30, 40, 50]
first_element <- numbers[1]
second_element <- numbers[2]
last_element <- numbers[5]
DISPLAY("First element: ")
DISPLAY(first_element)
DISPLAY("Second element: ")
DISPLAY(second_element)
DISPLAY("Last element: ")
DISPLAY(last_element)

Modifying Array Elements

You can change the value of any element in an array by assigning a new value to its index.

modifying_elements.spdl

# Modifying array elements
numbers <- [1, 2, 3, 4, 5]
DISPLAY("Original: ")
DISPLAY(numbers)

numbers[1] <- 100
DISPLAY("After changing first element: ")
DISPLAY(numbers)

numbers[3] <- 300
DISPLAY("After changing third element: ")
DISPLAY(numbers)

Adding Elements to Arrays

You can add new elements to the end of an array by using an index beyond the current length.

adding_elements.spdl

# Adding elements to an array
numbers <- [1, 2, 3]
DISPLAY("Original array: ")
DISPLAY(numbers)

APPEND(numbers, 4)
DISPLAY("After adding 4: ")
DISPLAY(numbers)

APPEND(numbers, 5)
DISPLAY("After adding 5: ")
DISPLAY(numbers)

Array Length

The LENGTH function returns the number of elements in an array.

array_length.spdl

# Getting array length
numbers <- [1, 2, 3, 4, 5]
names <- ["Alice", "Bob"]
length_numbers <- LENGTH(numbers)
length_names <- LENGTH(names)
DISPLAY("Numbers array length: ")
DISPLAY(length_numbers)
DISPLAY("Names array length: ")
DISPLAY(length_names)

Linked Lists

Linked lists are linear data structures where elements are stored in nodes, and each node points to the next node in the sequence. We can simulate linked lists using arrays in Spindle.

Creating a Linked List

We'll use an array to store the data and implement linked list operations.

linked_list_create.spdl

# Creating a linked list using an array
linked_list <- []

PROCEDURE APPEND(data) {
    # Add data to the end of the list
    linked_list[LENGTH(linked_list) + 1] <- data
    DISPLAY("Added: ")
    DISPLAY(data)
}

# Add some elements
APPEND(10)
APPEND(20)
APPEND(30)

DISPLAY("Linked list: ")
DISPLAY(linked_list)

Displaying a Linked List

We can traverse the linked list to display all elements with arrow notation.

linked_list_display.spdl

# Displaying linked list with arrows
linked_list <- [10, 20, 30, 40]

PROCEDURE DISPLAY_LIST() {
    DISPLAY("Linked List:")
    i <- 1
    REPEAT LENGTH(linked_list) TIMES {
        DISPLAY(linked_list[i] + " -> ")
        i <- i + 1
    }
    DISPLAY("None")
}

DISPLAY_LIST()

Searching in a Linked List

We can search for a specific element and return its position in the list.

linked_list_search.spdl

# Searching in linked list
linked_list <- [10, 20, 30, 40]

PROCEDURE SEARCH(target) {
    i <- 1
    position <- 1
    
    REPEAT LENGTH(linked_list) TIMES {
        IF (linked_list[i] == target) {
            RETURN position
        }
        i <- i + 1
        position <- position + 1
    }
    RETURN -1
}

# Search for elements
position_30 <- SEARCH(30)
position_50 <- SEARCH(50)

DISPLAY("30 found at position: ")
DISPLAY(position_30)
DISPLAY("50 found at position: ")
DISPLAY(position_50)

Stacks

Stacks follow the Last-In-First-Out (LIFO) principle, where the last element added is the first one removed. Think of it like a stack of plates.

Creating a Stack

We'll implement a stack using an array with push and pop operations.

stack_create.spdl

# Creating a stack
stack <- []

PROCEDURE PUSH(item) {
    # Add item to top of stack
    stack[LENGTH(stack) + 1] <- item
    DISPLAY("Pushed: ")
    DISPLAY(item)
}

PROCEDURE POP() {
    # Remove and return top item
    IF (LENGTH(stack) == 0) {
        DISPLAY("Stack is empty!")
        RETURN "EMPTY"
    }
    
    top_item <- stack[LENGTH(stack)]
    DISPLAY("Popped: ")
    DISPLAY(top_item)
    RETURN top_item
}

# Add some elements
PUSH("First")
PUSH("Second")
PUSH("Third")

DISPLAY("Stack: ")
DISPLAY(stack)

Stack Operations

Let's see how push and pop operations work in sequence.

stack_operations.spdl

# Stack operations demonstration
stack <- []

PROCEDURE PUSH(item) {
    stack[LENGTH(stack) + 1] <- item
    DISPLAY("Pushed: ")
    DISPLAY(item)
}

PROCEDURE POP() {
    IF (LENGTH(stack) == 0) {
        RETURN "EMPTY"
    }
    top_item <- stack[LENGTH(stack)]
    DISPLAY("Popped: ")
    DISPLAY(top_item)
    RETURN top_item
}

# Demonstrate LIFO behavior
PUSH("A")
PUSH("B")
PUSH("C")

DISPLAY("Stack before popping: ")
DISPLAY(stack)
POP()
POP()
POP()

Checking Stack Status

We can check if a stack is empty and peek at the top element without removing it.

stack_status.spdl

# Stack status operations
stack <- []

PROCEDURE IS_EMPTY() {
    RETURN LENGTH(stack) == 0
}

PROCEDURE PEEK() {
    IF (LENGTH(stack) == 0) {
        RETURN "Stack is empty"
    }
    RETURN stack[LENGTH(stack)]
}

PROCEDURE PUSH(item) {
    stack[LENGTH(stack) + 1] <- item
}

# Test stack status
DISPLAY("Is empty: ")
DISPLAY(IS_EMPTY())
PUSH("Hello")
DISPLAY("Is empty: ")
DISPLAY(IS_EMPTY())
DISPLAY("Top element: ")
DISPLAY(PEEK())

Queues

Queues follow the First-In-First-Out (FIFO) principle, where the first element added is the first one removed. Think of it like a line of people.

Creating a Queue

We'll implement a queue using an array with enqueue and dequeue operations.

queue_create.spdl

# Creating a queue
queue <- []

PROCEDURE ENQUEUE(item) {
    # Add item to back of queue
    queue[LENGTH(queue) + 1] <- item
    DISPLAY("Enqueued: ")
    DISPLAY(item)
}

PROCEDURE DEQUEUE() {
    # Remove and return front item
    IF (LENGTH(queue) == 0) {
        DISPLAY("Queue is empty!")
        RETURN "EMPTY"
    }
    
    front_item <- queue[1]
    DISPLAY("Dequeued: ")
    DISPLAY(front_item)
    RETURN front_item
}

# Add some elements
ENQUEUE("First")
ENQUEUE("Second")
ENQUEUE("Third")

DISPLAY("Queue: ")
DISPLAY(queue)

Queue Operations

Let's see how enqueue and dequeue operations work in sequence.

queue_operations.spdl

# Queue operations demonstration
queue <- []

PROCEDURE ENQUEUE(item) {
    queue[LENGTH(queue) + 1] <- item
    DISPLAY("Enqueued: ")
    DISPLAY(item)
}

PROCEDURE DEQUEUE() {
    IF (LENGTH(queue) == 0) {
        RETURN "EMPTY"
    }
    front_item <- queue[1]
    DISPLAY("Dequeued: ")
    DISPLAY(front_item)
    RETURN front_item
}

# Demonstrate FIFO behavior
ENQUEUE("A")
ENQUEUE("B")
ENQUEUE("C")

DISPLAY("Queue before dequeuing: ")
DISPLAY(queue)
DEQUEUE()
DEQUEUE()
DEQUEUE()

Common Data Structure Operations

Let's look at some common operations you'll perform on data structures.

Traversing Arrays

Traversing means visiting each element in a data structure exactly once.

array_traversal.spdl

# Traversing an array
numbers <- [10, 20, 30, 40, 50]

DISPLAY("Traversing array:")
i <- 1
REPEAT LENGTH(numbers) TIMES {
    DISPLAY("Element ")
    DISPLAY(i)
    DISPLAY(": ")
    DISPLAY(numbers[i])
    i <- i + 1
}

Finding Maximum Value

We can find the maximum value in an array by comparing each element.

find_maximum.spdl

# Finding maximum value in array
numbers <- [5, 12, 3, 8, 15]
maximum <- numbers[1]
REPEAT 5 TIMES {
    IF ((numbers[n] > maximum)) {
        maximum <- numbers[n]
    }
}
DISPLAY("Maximum value: ")
DISPLAY(maximum)

Counting Elements

We can count how many times a specific element appears in an array.

count_elements.spdl

# Counting occurrences of an element
numbers <- [1, 2, 2, 3, 2, 4, 2]
count_2 <- 0
REPEAT 7 TIMES {
    IF ((numbers[n] == 2)) {
        count_2 <- count_2 + 1
    }
}
DISPLAY("Number 2 appears ")
DISPLAY(count_2)
DISPLAY(" times")

Practice Exercises

Practice implementing these data structure operations to reinforce your understanding.

Exercise 1: Reverse an Array

Write a function that reverses the elements in an array.

reverse_array.spdl

PROCEDURE REVERSE_ARRAY(arr) {
    reversed <- []
    i <- LENGTH(arr)
    
    REPEAT LENGTH(arr) TIMES {
        reversed[LENGTH(reversed) + 1] <- arr[i]
        i <- i - 1
    }
    RETURN reversed
}

# Test the function
original <- [1, 2, 3, 4, 5]
reversed <- REVERSE_ARRAY(original)
DISPLAY("Original: ")
DISPLAY(original)
DISPLAY("Reversed: ")
DISPLAY(reversed)

Exercise 2: Check if Array is Sorted

Write a function that checks if an array is sorted in ascending order.

check_sorted.spdl

PROCEDURE IS_SORTED(arr) {
    i <- 1
    REPEAT (LENGTH(arr) - 1) TIMES {
        IF (arr[i] > arr[i + 1]) {
            RETURN 0  # Not sorted
        }
        i <- i + 1
    }
    RETURN 1  # Sorted
}

# Test the function
sorted_array <- [1, 2, 3, 4, 5]
unsorted_array <- [3, 1, 4, 2, 5]

DISPLAY("Is [1,2,3,4,5] sorted? ")
DISPLAY(IS_SORTED(sorted_array))
DISPLAY("Is [3,1,4,2,5] sorted? ")
DISPLAY(IS_SORTED(unsorted_array))

Exercise 3: Remove Duplicates

Write a function that removes duplicate elements from an array.

remove_duplicates.spdl

PROCEDURE REMOVE_DUPLICATES(arr) {
    unique <- []
    i <- 1
    
    REPEAT LENGTH(arr) TIMES {
        # Check if element already exists
        found <- 0
        j <- 1
        REPEAT LENGTH(unique) TIMES {
            IF (arr[i] == unique[j]) {
                found <- 1
                BREAK
            }
            j <- j + 1
        }
        
        IF (found == 0) {
            APPEND(unique, arr[i])
        }
        i <- i + 1
    }
    RETURN unique
}

# Test the function
with_duplicates <- [1, 2, 2, 3, 4, 4, 5]
without_duplicates <- REMOVE_DUPLICATES(with_duplicates)
DISPLAY("Original: ")
DISPLAY(with_duplicates)
DISPLAY("Without duplicates: ")
DISPLAY(without_duplicates)

Ready to Learn More?

Now that you understand data structures, explore these related topics:

Algorithm Complexity Abstraction Practice MCQs