CSC 201 — Data Structures Condensed Course Notes v1

A comprehensive set of flashcards covering key concepts in Data Structures, focusing on Abstract Data Types, Object-Oriented Programming principles, algorithm efficiency, and data structure comparisons.

Abstract Data Types (ADTs)

A logical description of a data type defined by its behavior, specifying the operations supported, not the implementation.

Java Interfaces

In Java, interfaces represent ADTs by defining method names and signatures without implementations.

Data Structures vs ADTs

ADTs provide a logical view of data, while data structures provide a physical representation. Multiple structures can implement the same ADT.

Object-Oriented Programming (OOP)

A programming paradigm that organizes code using objects, which combine data fields and methods.

Inheritance (Is-a Relationship)

A feature allowing a class to inherit fields and methods from another class, such as a Notebook being a Computer.

Has-a Relationship (Aggregation)

A relationship where a class contains another object as a field, like a Computer having Memory.

Method Overriding

Occurs when a subclass provides a method with the same signature as one from the superclass.

Method Overloading

Occurs when multiple methods share the same name but differ in their parameter lists.

Polymorphism

A feature allowing a superclass reference to refer to a subclass object and determine the correct overridden method at runtime.

Abstract Classes

Classes that cannot be instantiated and may contain both abstract and concrete methods.

Algorithm Efficiency

Describes how the runtime or memory usage of an algorithm grows relative to input size.

Big-O Notation

A mathematical notation used to express the growth rate of an algorithm, primarily focusing on the worst-case scenario.

Common Big-O Classes

Includes O(1), O(log n), O(n), O(n log n), O(n²), O(2^n), and O(n!).

Arrays

Data structures that store elements contiguously and allow constant-time access by index but have a fixed size.

ArrayList

A resizable array implementation of the List ADT that dynamically tracks its size and capacity.

Singly Linked Lists

Data structures where each node contains data and a reference to the next node.

Doubly Linked Lists

Linked lists where each node references both the next and previous nodes, facilitating efficient insertion and removal.

Circular Linked Lists

Linked lists where the last node links back to the first, useful for round-robin scheduling.

Stacks

LIFO data structures where only the top element is accessible, supporting push, pop, and peek operations.

Queues

FIFO data structures with insertions at the rear and removals at the front.

Deque

A double-ended queue allowing insertions and removals at both ends.

ArrayList

A resizable array implementation of the List ADT that dynamically tracks its size and capacity.

Adding an element to an ArrayList (conceptual)

When adding an element to an ArrayList, if the internal array is full, a new, larger array is allocated, and all existing elements are copied to the new array before the new element is added.

void add(E item) {
    if (size == capacity) {
        resize(); // Create bigger array, copy elements
    }
    elements[size++] = item;
}

Singly Linked Lists

Data structures where each node contains data and a reference to the next node.

Doubly Linked Lists

Linked lists where each node references both the next and previous nodes, facilitating efficient insertion and removal.

Circular Linked Lists

Linked lists where the last node links back to the first, useful for round-robin scheduling.

Basic Node Structure for Singly Linked List

A node in a singly linked list typically contains two parts: a data field to store the element and a next reference (or pointer) to the subsequent node in the list. The last node's next reference is usually null.

class Node<T> {
    T data;
    Node<T> next;
    Node(T data) {
        this.data = data;
        this.next = null;
    }
}

Stacks

LIFO data structures where only the top element is accessible, supporting push, pop, and peek operations.

Common Implementation Strategies for Stacks

Stacks can be efficiently implemented using either a dynamic array (like ArrayList) or a singly linked list. Both offer constant-time O(1) operations for push, pop, and peek, assuming array resizing amortized cost is considered.

Conceptual push operation for an Array-Based Stack

To push an element onto an array-based stack, the element is placed at the current top index, and then the top index is incremented. If the array is full, it must be resized.

void push(E item) {
    if (size == capacity) {
        resize(); // Allocate new, larger array and copy elements
    }
    elements[size++] = item; // 'size' acts as the 'top' index
}

Conceptual pop operation for a Linked List-Based Stack

To pop an element from a linked list-based stack, the element at the head (which represents the top of the stack) is returned, and the head pointer is updated to point to the next node.

E pop() {
    if (isEmpty()) throw new EmptyStackException();
    E item = head.data;
    head = head.next;
    size--;
    return item;
}

Queues

FIFO data structures with insertions at the rear and removals at the front.

Common Implementation Strategies for Queues

Queues are often implemented using a circular array for efficient O(1) enqueue and dequeue operations, or a singly linked list which also provides O(1) time complexity for these operations.

Conceptual enqueue operation for a Linked List-Based Queue

To enqueue an element into a linked list-based queue, a new node is created and added to the rear of the list. If the queue was empty, the new node also becomes the front.

void enqueue(E item) {
    Node<E> newNode = new Node<>(item);
    if (isEmpty()) {
        front = newNode;
        rear = newNode;
    } else {
        rear.next = newNode;
        rear = newNode;
    }
    size++;
}

Conceptual dequeue operation for a Linked List-Based Queue

To dequeue an element from a linked list-based queue, the element at the front of the list is returned, and the front pointer is updated to point to the next node.

E dequeue() {
    if (isEmpty()) throw new EmptyQueueException();
    E item = front.data;
    front = front.next;
    if (front == null) { // Queue became empty
        rear = null;
    }
    size--;
    return item;
}

Deque

A double-ended queue allowing insertions and removals at both ends.

ArrayList

A resizable array implementation of the List ADT that dynamically tracks its size and capacity.

Adding an element to an ArrayList (conceptual)

When adding an element to an ArrayList, if the internal array is full, a new, larger array is allocated, and all existing elements are copied to the new array before the new element is added.

void add(E item) {
    if (size == capacity) {
        resize(); // Create bigger array, copy elements
    }
    elements[size++] = item;
}

Time Complexity for ArrayList get(index)

Accessing an element by its index in an ArrayList takes constant time, O(1), because array elements are stored contiguously in memory.

Time Complexity for ArrayList add(item) at the end

Adding an element to the end of an ArrayList is typically O(1) amortized time. In the worst case, when resizing is needed, it becomes O(n) due to copying elements to a new array.

Time Complexity for ArrayList remove(index)

Removing an element from an ArrayList at a given index is O(n) because all subsequent elements must be shifted to fill the gap.

Singly Linked Lists

Data structures where each node contains data and a reference to the next node.

Doubly Linked Lists

Linked lists where each node references both the next and previous nodes, facilitating efficient insertion and removal.

Node Structure for Doubly Linked List

A node in a doubly linked list contains data, a next reference to the subsequent node, and a previous reference to the preceding node.

class DoublyNode<T> {
    T data;
    DoublyNode<T> next;
    DoublyNode<T> previous;
    DoublyNode(T data) {
        this.data = data;
        this.next = null;
        this.previous = null;
    }
}

Advantage of Doubly Linked Lists for Deletion

Deleting a node in a doubly linked list is more efficient (O(1)) once the node to be deleted is found, as you have direct access to its previous node through the previous reference, allowing re-linking without needing to traverse from the head.

Circular Linked Lists

Linked lists where the last node links back to the first, useful for round-robin scheduling.

Basic Node Structure for Singly Linked List

A node in a singly linked list typically contains two parts: a data field to store the element and a next reference (or pointer) to the subsequent node in the list. The last node's next reference is usually null.

class Node<T> {
    T data;
    Node<T> next;
    Node(T data) {
        this.data = data;
        this.next = null;
    }
}

Stacks

LIFO data structures where only the top element is accessible, supporting push, pop, and peek operations.

Common Implementation Strategies for Stacks

Stacks can be efficiently implemented using either a dynamic array (like ArrayList) or a singly linked list. Both offer constant-time O(1) operations for push, pop, and peek, assuming array resizing amortized cost is considered.

Implementing a Stack using an Array

An array can implement a stack by using one end as the 'top'. Elements are pushed by adding them to the next available position and incrementing a 'top' pointer/index. Popping involves retrieving the element at the 'top' and decrementing the pointer.

Conceptual push operation for an Array-Based Stack

To push an element onto an array-based stack, the element is placed at the current top index, and then the top index is incremented. If the array is full, it must be resized.

void push(E item) {
    if (size == capacity) {
        resize(); // Allocate new, larger array and copy elements
    }
    elements[size++] = item; // 'size' acts as the 'top' index
}

Conceptual pop operation for a Linked List-Based Stack

To pop an element from a linked list-based stack, the element at the head (which represents the top of the stack) is returned, and the head pointer is updated to point to the next node.

E pop() {
    if (isEmpty()) throw new EmptyStackException();
    E item = head.data;
    head = head.next;
    size--;
    return item;
}

Queues

FIFO data structures with insertions at the rear and removals at the front.

Common Implementation Strategies for Queues

Queues are often implemented using a circular array for efficient O(1) enqueue and dequeue operations, or a singly linked list which also provides O(1) time complexity for these operations.

Circular Array for Queues: Mechanism

In a circular array implementation of a queue, the front and rear pointers (or indices) wrap around to the beginning of the array when they reach the end, effectively treating the array as continuous or circular.

Conceptual enqueue operation for a Circular Array-Based Queue

To enqueue an element into a circular array-based queue, the rear pointer is incremented (modulo array capacity) and the element is placed at that new position. If the queue is full, resizing or an error may occur.

void enqueue(E item) {
    if (isFull()) throw new FullQueueException();
    rear = (rear + 1) % capacity;
    elements[rear] = item;
    size++;
}

Conceptual dequeue operation for a Circular Array-Based Queue

To dequeue an element from a circular array-based queue, the element at the front pointer's position is returned, and the front pointer is then incremented (modulo array capacity).

E dequeue() {
    if (isEmpty()) throw new EmptyQueueException();
    E item = elements[front];
    front = (front + 1) % capacity;
    size--;
    return item;
}

Conceptual enqueue operation for a Linked List-Based Queue

To enqueue an element into a linked list-based queue, a new node is created and added to the rear of the list. If the queue was empty, the new node also becomes the front.

void enqueue(E item) {
    Node<E> newNode = new Node<>(item);
    if (isEmpty()) {
        front = newNode;
        rear = newNode;
    } else {
        rear.next = newNode;
        rear = newNode;
    }
    size++;
}

Conceptual dequeue operation for a Linked List-Based Queue

To dequeue an element from a linked list-based queue, the element at the front of the list is returned, and the front pointer is updated to point to the next node.

E dequeue() {
    if (isEmpty()) throw new EmptyQueueException();
    E item = front.data;
    front = front.next;
    if (front == null) { // Queue became empty
        rear = null;
    }
    size--;
    return item;
}

Implementing a Queue using Two Stacks (Conceptual)

A queue can be implemented using two stacks: one for enqueue operations (pushing elements onto it) and one for dequeue operations (popping elements from it). When the dequeue stack is empty, all elements are popped from the enqueue stack and pushed onto the dequeue stack to reverse their order.

Deque

A double-ended queue allowing insertions and removals at both ends.