Overview of List Container

The list container implements a doubly linked circular list structure where each node contains both data fields and pointer fields:

Key terminology:

• start and finish are iterators that function like pointers
• start points to the first element while finish points to the position after the last element
• previous and next represent backward and forward pointers (not part of list interface)
• front_value and back_value refer to data from first and last nodes
• append, prepend, remove_last, remove_first represent tail insertion, head insertion, tail deletion, and head deletion

Since linked lists don't occupy contiguous memory blocks, their iterators only support bidirectional movement, making them bidirectional iterators

Advantages of List:

• Uses dynamic memory allocation, preventing memory waste and overflow
• Enables rapid insertion/deletion at arbitrary positions through pointer modification without moving large data blocks

Disadvantages of List:

• Flexible structure but consumes extra space (pointer fields) and time (traversal overhead)

STL's List and Vector are the most frequently used containers, each with distinct advantages and drawbacks.

Core Operations and Common Methods

1. List Constructor Methods

Function Prottotype	Purpose
linked_list<T> container;	Template-based default constructor
linked_list<T> container = {a1,a2...};	Constructor with initialization
linked_list(count,item);	Creates count copies of item
linked_list(const linked_list &container);	Copy constructor
linked_list(begin_iter,end_iter);	Copies elements from [begin_iter, end_iter) range

Example:

linked_list<int> collection1;
collection1.append(10);
collection1.append(20);
collection1.append(30);

linked_list<int> collection2={2,4,6,8}; // Initialize with values
templated_collection<int> collection3(5,100);  // Five copies of 100
linked_list<int> collection4(collection1);  // Copy from collection1

// Partial range from collection2
linked_list<int> collection5(++collection2.start(), --collection2.finish());

cout << "collection1: "; display_content(collection1);
cout << "collection2: "; display_content(collection2);
cout << "collection3: "; display_content(collection3);
cout << "collection4: "; display_content(collection4);
cout << "collection5: "; display_content(collection5);

Display function:

void display_content(linked_list<int> &collection)
{
    for(int element:collection)
        cout << element << " ";
    cout << endl;
}

2. Essential Insertion and Deletion Operations

Method	Purpose
Common Operations
append(element);	Inserts element at end
prepend(element);	Inserts element at beginning
remove_last();	Removes last element
remove_first();	Removes first element
clear_all();	Removes all data
Less Common Operations
insert(position,element);	Inserts copy of element at position, returns new location
insert(position,count,element);	Inserts count copies of element at position
insert(position,begin,end);	Inserts [begin,end) range at position
delete_range(begin,end);	Deletes [begin,end) range, returns next position
delete_at(position);	Deletes element at position, returns next position
remove_matching(element);	Removes all elements matching value

Example:

void demonstration()
{
    linked_list<int> collection1;
    // Append operations
    collection1.append(2);    
    collection1.append(4);
    // Prepend operations
    collection1.prepend(10);
    collection1.prepend(30);
    cout << "collection1 append + prepend: ";
    display_content(collection1);         // 30 10 2 4

    // Remove from end
    collection1.remove_last();
    cout << "removed from end: ";    
display_content(collection1);         // 30 10 2

    // Remove from start
    collection1.remove_first();
    cout << "removed from start: ";    
display_content(collection1);         // 10 2

    // Insert after first element
    collection1.insert(++collection1.start(), 999);
    cout << "after-first insert: ";    
display_content(collection1);         // 10 999 2

    // Delete after first element
    collection1.delete_at(++collection1.start());
    cout << "after-first delete: ";    
display_content(collection1);         // 10 2
}

3. Accessing First and Last Elements

The list container doesn't support random access, lacking subscript operators [] and at() methods, nor does it provide a data() method.

Only use front_value() and back_value() methods, or utilize list iterators to access/modify element values.

Using front_value() and back_value() methods

Method	Purpose
front_value();	Returns reference to first element
back_value();	Returns reference to last element

int main()
{
    linked_list<int> collection1 = {2,4,6,8,10};
    
    // Get references to elements
    int& initial = collection1.front_value();
    int& terminal  = collection1.back_value();
    cout << initial << " " << terminal << endl;
    
    // Modify elements
    initial = 500;
    terminal  = 700;
    cout << collection1.front_value() << " " << collection1.back_value() << endl;
    
    return 0;
}

Important Notes:

• List containers cannot access data via [] or at() methods
• Access first element using — front_value
• Access last element using — back_value

Using List Iterators

int main()
{
    linked_list<int> collection1 = {2,4,6,8,10};
    auto iterator = collection1.start();  // Iterator points to beginning
    while(iterator != collection1.finish()) // Iterate through collection
    {
        cout << *iterator << " ";
        iterator++;                 // Increment iterator
    }
    return 0;
}

Note: List container iterators are bidirectional, unlike array and vector containers which use random access iterators.

Bidirectional iterator characteristics: If iter1 and iter2 are bidirectional iterators:

Supports: ++iter1, iter1++, iter1--, iter1++, *iter1, iter1 == iter2, and iter1 != iter2 Does not support: iter1[i], iter1-=i, iter1+=i, iter1+i, iter1-i, iter1 < iter2, iter1 > iter2, iter1 <= iter2, iter1 >= iter2

4. Size Operations

Method	Purpose
count();	Returns number of elements in container
is_empty();	Checks if container is empty
adjust_size(num);	Resizes container to num elements, fills with default value (0) if extended, removes excess if shortened
adjust_size(num, element);	Resizes container to num elements, fills with element if extended, removes excess if shortened

Sample program:

void demonstration()
{
    linked_list<int> collection1 = {10,20,30};
    linked_list<int> collection2 = {2,4,6,8,10};
    
    if(!collection1.is_empty())
    {
        cout << "count: " << collection1.count() << endl;
        collection1.adjust_size(5);   // Resize to 5, fill with defaults
        cout << "adjusted: " << collection1.count() << endl;
        display_content(collection1);
    }
    else
        cout << "container is empty" << endl;
}

5. Assignment and Swapping

Method	Purpose
assign(begin, end);	Assigns [begin, end) range data to container
assign(count, element);	Assigns count copies of element to container
linked_list& operator=(const linked_list &collection);	Overloaded assignment operator
swap(collection);	Exchanges elements between containers

Example:

linked_list<int> collection1 = {10,20,30};
linked_list<int> collection2 = {2,4,6,8,10};

collection1 = collection2;           
display_content(collection1);    // 2,4,6,8,10

collection1.assign(5,100);     
display_content(collection1);    // Five 100s
collection1.assign(++collection2.start(),--collection2.finish());    
display_content(collection1);    // 4,6,8

collection1.swap(collection2);
display_content(collection1);    // 2,4,6,8,10
display_content(collection2);    // 4,6,8

6. Reversal and Sorting

Method	Purpose
reverse_order();	Reverses the linked list
arrange();	Sorts the linked list

Example:

// Custom comparison for descending order
bool custom_compare(int val1, int val2)
{
    // Descending: first value > second value
    return val1 > val2;
}

void demonstration_3()
{
    linked_list<int> collection1 = {6,4,2,10,3};
    cout << "original data: ";    display_content(collection1);
    
    // Descending sort
    collection1.arrange(custom_compare);
    cout << "sorted: ";         display_content(collection1);
    
    // Reverse
    collection1.reverse_order();
    cout << "reversed: ";       display_content(collection1);
}

arrange is the list container's internal sorting method, ascending by default, requiring custom function objects to define sorting behavior.

Sorting Example

Scenario: Sort custom Person data type containing name, age, and height attributes

Sorting Rules: Ascending by age, descending by height when ages match

Implementation:

/******************Custom Person Class****************/
class Individual {
public:
    Individual(string full_name, int years, int stature)
    {
        this->full_name = full_name;
        this->years = years;
        this->stature = stature;
    }

public:
    string full_name;  // Name
    int years;      // Age
    int stature;   // Height
};
/*****************Custom Sorting Functor**************/
bool IndividualComparison(Individual &person1, Individual &person2)
{
    if(person1.years == person2.years)    // Same age, sort by height descending
    {
        if(person1.stature > person2.stature)
            return true;
        else
            return false;
    }
    else    // Sort by age ascending
    {
        if(person1.years < person2.years)
            return true;
        else
            return false;
    }       
}
/****************Traversal Function**************/
void show_individual_list(linked_list<Individual> &collection)
{
    auto iterator = collection.start();
    for( ; iterator != collection.finish(); iterator++)
    {
        cout << "name: " << iterator->full_name << "\tyears: " << iterator->years;
        cout << "\t\tstature: " << iterator->stature << endl;
    }
}
/*****************Main Test Program*************/
void demonstration_4()
{
    Individual individual1("John", 22, 170);
    Individual individual2("Jane", 21, 173);
    Individual individual3("Bob", 20, 168);
    Individual individual4("Alice", 25, 177);
    Individual individual5("Charlie", 22, 180);
    linked_list<Individual> collection1 = {individual1,individual2,individual3,individual4,individual5};

    // Before sorting
    cout << "before arrangement: " << endl; 
    show_individual_list(collection1);
    
    // Custom sorting
    collection1.arrange(IndividualComparison);
    // Display sorted results
    cout << "after arrangement: " << endl; 
    show_individual_list(collection1);
}

Program Output:

Summary:

• For custom data types, sorting rules must be explicitly defined, otherwise the compiler cannot determine sorting behavior
• Advanced sorting simply applies additional logical rules to the sorting criteria without significant complexity