CurriculumList
List
A <code>std::list</code> is a doubly-linked list. Each element is allocated separately on the heap and contains pointers to the next and previous elements. Elements are NOT contiguous in memory.
011. Initialization
A `std::list` is a doubly-linked list. It can be initialized similarly to a vector.
main.cpp
Terminal
Waiting for execution...
022. Front & Back Modifiers
Because it's a doubly-linked list, `push_front` and `pop_front` are just as fast (O(1)) as `push_back` and `pop_back`.
main.cpp
Terminal
Waiting for execution...
033. Bidirectional Iterators
Lists only support Bidirectional Iterators. You can do `++it` and `--it`, but you CANNOT do `it + 5`.
main.cpp
Terminal
Waiting for execution...
044. O(1) Middle Insert & Erase
Once you have an iterator pointing to a location, inserting or erasing is instantaneous (O(1)) because no elements are shifted. Only pointers are updated.
main.cpp
Terminal
Waiting for execution...
055. Remove
`remove(value)` scans the entire list and deletes all nodes matching the value.
main.cpp
Terminal
Waiting for execution...
066. Splice
`splice` allows you to move elements from one list into another without allocating or deallocating any memory! It just remaps the pointers.
main.cpp
Terminal
Waiting for execution...
077. Sort
Because list elements aren't contiguous, you can't use `std::sort`. Instead, lists have their own highly optimized `.sort()` member function.
main.cpp
Terminal
Waiting for execution...
088. Unique
`.unique()` removes consecutive duplicate elements. The list should usually be sorted first.
main.cpp
Terminal
Waiting for execution...
099. Merge
`.merge(otherList)` merges two SORTED lists into one sorted list, destroying the other list in the process.
main.cpp
Terminal
Waiting for execution...
1010. Reverse
`.reverse()` reverses the entire list in O(N) time just by swapping the next and prev pointers in every node.
main.cpp
Terminal
Waiting for execution...
AI Tutor
Lists allow extremely fast insertion and deletion at ANY point in the sequence (O(1)), provided you already have an iterator pointing there. However, you cannot use <code>[ ]</code> to access elements.