Data Structures Exam 1

What does a template do?

A template lets you write generic code that works with many data types without rewriting it for each one. They are resolved at compile time.

Example of writing a function template

template <typename T>

T maxValue(T a, T b) {

    return (a > b) ? a : b;

}

What using a function template looks like

int x = maxValue(3, 5);        // T becomes int
double y = maxValue(2.5, 1.1); // T becomes double

Writing a class template

template <typename T>
class Box {
private:
    T value;
public:
    Box(T v) : value(v) {}
    T getValue() { return value; }
};

What using a class template looks like

Box<int> intBox(10);
Box<string> strBox("hello");

Box<int> and Box<string> are different classes. The compiler generates separate versions for each type.

Why do templates matter in data structures?

Most data structures (lists, stacks, trees, vectors) should work for any type, not just int.

What is a constructor?

A constructor is a special function that:

• Has the same name as the class

• Has no return type

• Runs automatically when an object is created

Example of a constructor

class Node {
public:
    int data;
    Node* next;

    Node(int d) {
        data = d;
        next = nullptr;
    }
};

What are constructors used for?

• Initializing variables

• Allocating memory

• Setting default values

• Putting the object into a valid state

What is a destructor?

A destructor is a special function that:

• Has the same name as the class

• Starts with ~

• Has no parameters

• Runs automatically when an object is destroyed

Example of a destructor

class Node {
public:
    ~Node() {
        // clean up resources
    }
};

When are destructors called?

• Object goes out of scope

• delete is called on a dynamically allocated object

• Program ends

Why are destructors important in data structures?

Data structures often use dynamic memory. If you don’t delete it, you get memory leaks.

Example:

~LinkedList() {
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

What do vectors manage?

• Size → number of elements actually in the vector

• Capacity → amount of memory allocated

size <= capacity

What does the size() function do?

• Returns the number of elements in the vector

• Does not include unused capacity

What does the capacity() function do?

• Returns how many elements the vector can hold before reallocation

• Grows automatically (usually doubles)

What does the resize(n) function do?

• If n > size, it adds elements (default initialized)

• If n < size, it removes elements

What does the reserve(n) function do?

• Ensures capacity is at least n

• Does not change size

• Used to avoid repeated reallocations

What does the push_back(n) function do?

• Adds elements to the end

• Increases size by 1

• May increase capacity if full

What does the at(index) function do?

• Accesses element with bounds checking

• Throws an exception if index is invalid

• Safer than operator[]

What does the data() function do?

• Returns pointer to underlying array

• Allows direct memory access

• Dangerous if vector resized afterward

Example of a singly-linked node

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

Example of a doubly-linked node

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

Insert at Beginning (push_front)

Singly:

newNode->next = head;
head = newNode;

Doubly:

newNode->next = head;
head->prev = newNode;
head = newNode;

O(1)

Insert at Beginning (push_back)

Singly:

• Traverse to last node

• Set last→next = newNode

O(n) unless tail pointer exists)

Doubly: Use tail pointer

tail->next = newNode;
newNode->prev = tail;
tail = newNode;

Insert After a Node

Singly:

newNode->next = curr->next;
curr->next = newNode;

Doubly:

newNode->next = curr->next;
newNode->prev = curr;
curr->next->prev = newNode;
curr->next = newNode;

Remove from Beginning (pop_front)

Singly:

Node* temp = head;
head = head->next;
delete temp;

Doubly:

head = head->next;
head->prev = nullptr;

Remove from End (pop_back)

Singly:

• Traverse to second-to-last node

• Set its next to nullptr

O(n)

Doubly:

tail = tail->prev;
tail->next = nullptr;

O(1)

Remove a Node (Doubly Linked List)

curr->prev->next = curr->next;
curr->next->prev = curr->prev;
delete curr;

Find (Singly and Doubly)

Node* curr = head;
while (curr != nullptr) {
    if (curr->data == target) return curr;
    curr = curr->next;
}

O(n)

Insert in Sorted Order

• Traverse until curr->data > newValue

• Insert before curr

Singly:

• Must track prev

Doubly:

• Easier because of prev pointer

O(n)

Forward Traversal (print)

Node* curr = head;
while (curr != nullptr) {
    cout << curr->data << " ";
    curr = curr->next;
}

Backward Traversal (printReverse)

• Only possible efficiently in doubly-linked lists

Node* curr = tail;
while (curr != nullptr) {
    cout << curr->data << " ";
    curr = curr->prev;
}