Unit 1: List and Iterator ADTs

Learning Objectives

• Understand Abstract Data Types (ADTs) for linear structures
• Implement and use vectors, lists, and sequences
• Master iterator design patterns for traversal
• Compare different list implementations and their trade-offs

1. Vectors

Vectors are dynamic arrays that can resize automatically. They provide random access to elements and efficient insertion/deletion at the end.

Vector Implementation in C++ STL

#include <iostream>
#include <vector>
#include <algorithm>

class VectorDemo {
public:
    static void demonstrateVector() {
        std::vector<int> vec;
        
        // Insertion operations
        vec.push_back(10);
        vec.push_back(20);
        vec.push_back(30);
        vec.insert(vec.begin() + 1, 15); // Insert 15 at index 1
        
        std::cout << "Vector contents: ";
        for(const auto& element : vec) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
        
        // Access operations
        std::cout << "Element at index 2: " << vec[2] << std::endl;
        std::cout << "First element: " << vec.front() << std::endl;
        std::cout << "Last element: " << vec.back() << std::endl;
        
        // Size and capacity
        std::cout << "Size: " << vec.size() << std::endl;
        std::cout << "Capacity: " << vec.capacity() << std::endl;
        
        // Deletion operations
        vec.pop_back();
        vec.erase(vec.begin() + 1);
        
        std::cout << "After deletion: ";
        for(const auto& element : vec) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    }
};

2. Lists

Lists are implemented as doubly-linked lists in C++ STL. They provide efficient insertion and deletion at any position but no random access.

List Implementation in C++ STL

#include <iostream>
#include <list>
#include <algorithm>

class ListDemo {
public:
    static void demonstrateList() {
        std::list<int> lst;
        
        // Insertion operations
        lst.push_back(10);
        lst.push_front(5);
        lst.push_back(20);
        lst.push_back(15);
        
        std::cout << "List contents: ";
        for(const auto& element : lst) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
        
        // Find and insert
        auto it = std::find(lst.begin(), lst.end(), 15);
        if(it != lst.end()) {
            lst.insert(it, 12);
        }
        
        std::cout << "After insertion: ";
        for(const auto& element : lst) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
        
        // Sorting and operations
        lst.sort();
        std::cout << "After sorting: ";
        for(const auto& element : lst) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
        
        // Remove elements
        lst.remove(12);
        lst.pop_front();
        lst.pop_back();
        
        std::cout << "Final list: ";
        for(const auto& element : lst) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    }
};

3. Sequences and Deques

Deques (double-ended queues) combine the advantages of vectors and lists, providing efficient insertion/deletion at both ends.

Deque Implementation in C++ STL

#include <iostream>
#include <deque>

class DequeDemo {
public:
    static void demonstrateDeque() {
        std::deque<int> dq;
        
        // Insertion at both ends
        dq.push_back(10);
        dq.push_front(5);
        dq.push_back(20);
        dq.push_front(1);
        
        std::cout << "Deque contents: ";
        for(const auto& element : dq) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
        
        // Random access like vector
        std::cout << "Element at index 2: " << dq[2] << std::endl;
        
        // Deletion from both ends
        dq.pop_front();
        dq.pop_back();
        
        std::cout << "After deletions: ";
        for(const auto& element : dq) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    }
};

4. Iterator Design Pattern

Iterators provide a uniform way to traverse different container types without exposing their internal structure.

Iterator Usage Examples

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

class IteratorDemo {
public:
    static void demonstrateIterators() {
        std::vector<int> vec = {1, 2, 3, 4, 5};
        std::list<int> lst = {10, 20, 30, 40, 50};
        
        // Forward iteration
        std::cout << "Vector forward: ";
        for(auto it = vec.begin(); it != vec.end(); ++it) {
            std::cout << *it << " ";
        }
        std::cout << std::endl;
        
        // Reverse iteration
        std::cout << "Vector reverse: ";
        for(auto it = vec.rbegin(); it != vec.rend(); ++it) {
            std::cout << *it << " ";
        }
        std::cout << std::endl;
        
        // Algorithm usage with iterators
        auto max_it = std::max_element(vec.begin(), vec.end());
        std::cout << "Maximum element: " << *max_it << std::endl;
        
        // Distance between iterators
        auto distance = std::distance(vec.begin(), max_it);
        std::cout << "Index of max element: " << distance << std::endl;
        
        // Advanced iterator manipulation
        auto it = vec.begin();
        std::advance(it, 2);
        std::cout << "Element at position 2: " << *it << std::endl;
    }
    
    // Generic function working with any container
    template<typename Container>
    static void printContainer(const Container& container) {
        std::cout << "Container: ";
        for(auto it = container.begin(); it != container.end(); ++it) {
            std::cout << *it << " ";
        }
        std::cout << std::endl;
    }
};

5. Performance Comparison

Complete Example Program

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <algorithm>
#include <chrono>

int main() {
    std::cout << "=== Unit 1: List and Iterator ADTs Demo ===" << std::endl;
    
    // Vector demonstration
    std::cout << "\n--- Vector Demo ---" << std::endl;
    VectorDemo::demonstrateVector();
    
    // List demonstration
    std::cout << "\n--- List Demo ---" << std::endl;
    ListDemo::demonstrateList();
    
    // Deque demonstration
    std::cout << "\n--- Deque Demo ---" << std::endl;
    DequeDemo::demonstrateDeque();
    
    // Iterator demonstration
    std::cout << "\n--- Iterator Demo ---" << std::endl;
    IteratorDemo::demonstrateIterators();
    
    // Generic container printing
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::list<int> lst = {10, 20, 30, 40, 50};
    std::deque<int> dq = {100, 200, 300};
    
    IteratorDemo::printContainer(vec);
    IteratorDemo::printContainer(lst);
    IteratorDemo::printContainer(dq);
    
    return 0;
}