List in C++

List in C++_

Keypoints

• List conception
• List initialization/construction
• List assignment and swap
• List size operations
• List insertion and deletion
• List data access
• List sort and reverse

List conception

• Not continuous in memory. The elements are stored in different memory blocks. The sequence of elements is achieved by pointers.
• List consists of nodes. Each node has a value and pointers to the previous and next nodes. The first node points to the last node and the last node points to the first node.
• Advantages:
  • List can access and manipuate any element by index without moving elements ublike array.
• Disadvantages:
  • List traversal is slower than array.
  • Occupies more memory than array.

List initialization/construction

• List initialization
  • list<T> lst;: empty list
  • list(beg, end);: initializes the list with the elements in the range of beg to end.
  • list(n, elem);: initializes the list with n elements of value elem.
  • list(const list &lst);: copy constructor.

// list initialization
list<int> l1; // default constructor
for (int i = 0; i < 10; i++) {
    l1.push_back(i);
}

list<int> l2(l1.begin(), l1.end()); // copy constructor
list<int> l3(10, 100); // 10 elements with value 100
list<int> l4(l3); // copy constructor

List assignment and swap

• assign(beg, end);: Assigns new contents to the container, replacing its current contents, and modifying its size accordingly.
• assign(n, elem);: Assigns new contents to the container, replacing its current contents, and modifying its size accordingly.
• list& operator=(const list &lst);: Assigns new contents to the container, replacing its current contents, and modifying its size accordingly.
• swap(lst);: Exchanges the content of the container by the content of lst, which is another list object of the same type. Sizes may differ.

# include <iostream>
# include <list>
using namespace std;

void printList(const list<int> &l){
    for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

void test01(){
    list<int> l1;
    for (int i = 0; i < 10; i++) {
        l1.push_back(i);
    }
    printList(l1);  // 0 1 2 3 4 5 6 7 8 9

    list<int> l2;
    l2 = l1;
    printList(l2);  // 0 1 2 3 4 5 6 7 8 9

    list<int> l3;
    l3.assign(l2.begin(), l2.end());
    printList(l3);  // 0 1 2 3 4 5 6 7 8 9

    list<int> l4;
    l4.assign(10, 100);
    printList(l4);  // 100 100 100 100 100 100 100 100 100 100

    l1.swap(l4);
    printList(l1);  
    printList(l4);
}

int main(){
    test01();
    return 0;
}

List size operations

• size();: Returns the number of elements in the list container.
• empty();: Returns whether the list container is empty.
• resize(num);: Resizes the container so that it contains num elements.
• resize(num, elem);: Resizes the container so that it contains num elements. If num is smaller than the current container size, the content is reduced to its first num elements, removing those beyond. If num is greater than the current container size, the content is expanded by inserting at the end as many elements as needed to reach a size of num. If val is specified, the new elements are initialized as copies of val, otherwise, they are value-initialized.

# include <iostream>
# include <list>
using namespace std;

void printList(const list<int> &l){
    for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

void test01(){
    list<int> l1;
    for (int i = 0; i < 10; i++) {
        l1.push_back(i);
    }
    printList(l1);  // 0 1 2 3 4 5 6 7 8 9

    if (l1.empty()) {
        cout << "l1 is empty" << endl;
    } else {
        cout << "l1 is not empty" << endl;
        cout << "l1 size: " << l1.size() << endl;
    }

    l1.resize(15);
    printList(l1);  // 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0

    l1.resize(20, 100);
    printList(l1);  // 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 100 100 100 100 100

    l1.resize(5);
    printList(l1);  // 0 1 2 3 4
}

int main(){
    test01();
    return 0;
}

List insert and delete

• push_back(elem);: Adds a new element at the end of the list container, after its current last element. The content of val is copied (or moved) to the new element.
• pop_back();: Removes the last element in the list container, effectively reducing the container size by one.
• push_front(elem);: Adds a new element at the beginning of the list container, before its current first element. The content of val is copied (or moved) to the new element.
• pop_front();: Removes the first element in the list container, effectively reducing its size by one.
• insert(const_iterator pos, elem);: The container is extended by inserting a new element at position pos. This new element is constructed in place using args as the arguments for its construction.
• insert(const_iterator pos, n, elem);: The container is extended by inserting new elements before the element at the specified position. This new elements are constructed in place using args as the arguments for their construction.
• insert(const_iterator pos, beg, end);: The container is extended by inserting new elements before the element at the specified position. The new elements are constructed in place using args as the arguments for their construction.
• erase(const_iterator pos);: Removes from the list container either a single element (position) or a range of elements [first,last).
• erase(const_iterator start, const_iterator end);: Removes from the list container either a single element (position) or a range of elements [first,last).
• clear();: Removes all elements from the list container (which are destroyed), and leaving the container with a size of 0.
• remove(val);: Removes from the container all the elements that compare equal to val.

# include <iostream>
# include <list>
using namespace std;

void printList(const list<int> &l){
    for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

void test01(){
    list<int> l1;
    for (int i = 0; i < 10; i++) {
        l1.push_back(i);
    }
    printList(l1);  // 0 1 2 3 4 5 6 7 8 9

    l1.push_front(100);
    printList(l1);  // 100 0 1 2 3 4 5 6 7 8 9

    l1.pop_back();
    printList(l1);  // 100 0 1 2 3 4 5 6 7 8

    l1.pop_front();
    printList(l1);  // 0 1 2 3 4 5 6 7 8

    l1.insert(l1.begin(), 1000);
    printList(l1);  // 1000 0 1 2 3 4 5 6 7 8

    list<int>::iterator it = l1.begin();
    l1.insert(++it, 10000);
    printList(l1);  // 1000 10000 0 1 2 3 4 5 6 7 8

    l1.insert(l1.begin(), 2, 10000);
    printList(l1);  // 10000 10000 1000 10000 0 1 2 3 4 5 6 7 8

    list<int> l2;
    l2.push_back(1000);
    l2.push_back(2000);
    l2.push_back(3000);
    l1.insert(l1.begin(), l2.begin(), l2.end());
    printList(l1);  // 1000 2000 3000 10000 10000 1000 10000 0 1 2 3 4 5 6 7 8

    l1.erase(l1.begin());
    printList(l1);  // 2000 3000 10000 10000 1000 10000 0 1 2 3 4 5 6 7 8

    list<int>::iterator it = l1.begin();
    it++;
    l1.erase(it);
    printList(l1);  // 2000 10000 10000 1000 10000 0 1 2 3 4 5 6 7 8

    l1.remove(10000);
    printList(l1);  // 2000 1000 0 1 2 3 4 5 6 7 8

    l1.erase(l1.begin(), l1.end());
    printList(l1);  // 

    l1.clear();

}

int main(){
    test01();
    return 0;
}

List access

• front();: Access first element
• back();: Access last element
• Cant use [] or at to access elements. Because list is a linked list, not a continuous memory space.
• Iterator can’t be arbitarily added or subtracted, only support ++ and --.

# include <iostream>
# include <list>
using namespace std;


void test01(){
    list<int> l1;
    for (int i = 0; i < 10; i++) {
        l1.push_back(i);
    }
    l1.front() = 0;
    l1.back() = 9;
}

int main(){
    test01();
    return 0;
}

List sort and reverse

• sort();: Sort list. Can’t use sort() to sort user-defined data type, because it’s not continuous memory space.
• reverse();: Reverse list

# include <iostream>
# include <list>
using namespace std;

void test01(){
    list<int> l1;
    l1.push_back(10);
    l1.push_back(30);
    l1.push_back(20);
    l1.push_back(40);
    l1.push_back(80);
    l1.push_back(60);
    l1.push_back(70);
    l1.push_back(50);
    l1.push_back(90);
    l1.push_back(100);

    l1.sort();
    sort(l1.begin(), l1.end()); // error
    for (list<int>::iterator it = l1.begin(); it != l1.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;  // 10 20 30 40 50 60 70 80 90 100

    l1.reverse();
    for (list<int>::iterator it = l1.begin(); it != l1.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;  // 100 90 80 70 60 50 40 30 20 10
}

int main(){
    test01();
    return 0;
}

• Example: Sort user-defined data type

```c++

include

include

using namespace std;

class Person{ public: Person(string name, int age){ this->m_Name = name; // this pointer is a pointer pointing to the current object this->m_Age = age; } string m_Name; int m_Age; int m_Score; };

bool comparePerson(Person &p1, Person &p2){ if (p1.m_Age == p2.m_Age) { return p1.m_Score > p2.m_Score; // If age is the same, sort by score, from large to small } return p1.m_Age < p2.m_Age; // Sort by age, from small to large }

void test01(){ list l1; Person p1("A", 10, 100); Person p2("B", 30, 90); Person p3("C", 30, 80); Person p4("D", 27, 85); l1.push_back(p1); l1.push_back(p2); l1.push_back(p3); l1.push_back(p4);

for (list<Person>::iterator it = l1.begin(); it != l1.end(); it++) {
    cout << "Name: " << (*it).m_Name << " Age: " << (*it).m_Age << endl;
}
cout << endl;   // Name: A Age: 10
                // Name: B Age: 30
                // Name: C Age: 30
                // Name: D Age: 27

l1.sort(comparePerson); // define a function to sort user-defined data type

for (list<Person>::iterator it = l1.begin(); it != l1.end(); it++) {
    cout << "Name: " << (*it).m_Name << " Age: " << (*it).m_Age << endl;
}
cout << endl;   // Name: A Age: 10
                // Name: D Age: 27
                // Name: C Age: 30
                // Name: B Age: 30 }