template<typename T>
Dllist class

doubly linked list with sentinel head node

A Doubly-linked List class. This class simply contains a link of node's. By adding a "head" node (sentinel), deleting a node is extremely fast (see "Introduction to Algorithm"). This class does not keep the length information as it is not necessary for the FM algorithm. This saves memory and run-time to update the length information. Note that this class does not own the list node. They are supplied by the caller in order to better reuse the nodes.

Doubly Linked List with Sentinel Head:

    ┌─────────────────┐
    │    Dllist       │
    │  ┌───────────┐  │
    └─▶│   head    │  │
       │ (sentinel)│  │
       └───────────┘  │
         ▲     ▲      │
         │     │      │
    ┌─────┐   ┌─────┐ │
    │prev │───│next │─┘
    └─────┘   └─────┘
      │         │
      │    ┌────▼──┬─────────┐
      │    │       │         │
      │    │ ┌─────▼───┐     │
      │    │ │  Node   │     │
      │    │ │         │     │
      │    │ └─────────┘     │
      │    │     │           │
      │    │     ▼           │
      │    │ ┌─────────┐     │
      │    │ │  Node   │     │
      │    │ │         │     │
      │    │ └─────────┘     │
      │    │     │           │
      │    │     ▼           │
      │    │ ┌─────────┐     │
      │    │ │  Node   │     │
      │    │ │(tail)   │     │
      │    │ └─────────┘     │
      │    │     │           │
      └────┴─────┼───────────┘
                  ▼
             ┌─────────┐
             │  Node   │
             │(head)   │
             └─────────┘

The sentinel head simplifies operations by eliminating special cases
for empty lists and boundary nodes.

Constructors, destructors, conversion operators

Dllist(T data) explicit constexpr noexcept
Construct a new Dllist object.
Dllist() defaulted constexpr
Copy construct a new Dllist object (deleted intentionally)

Public functions

auto is_empty() const noexcept -> bool -> auto constexpr
whether the list is empty
auto clear() noexcept -> void -> auto constexpr
reset the list
auto appendleft(Dllink<T>& node) noexcept -> void -> auto constexpr
append the node to the front
auto append(Dllink<T>& node) noexcept -> void -> auto constexpr
append the node to the back
auto popleft() noexcept -> Dllink< T > & -> auto constexpr
pop a node from the front
auto pop() noexcept -> Dllink< T > & -> auto constexpr
pop a node from the back
auto begin() noexcept -> DllIterator< T > -> auto constexpr
begin
auto end() noexcept -> DllIterator< T > -> auto constexpr
end

Function documentation

template<typename T>
Dllist<T>::Dllist(T data) explicit constexpr noexcept

Construct a new Dllist object.

Parameters
data in the data

template<typename T>
auto Dllist<T>::is_empty() const noexcept -> bool constexpr

whether the list is empty

Returns true

template<typename T>
auto Dllist<T>::appendleft(Dllink<T>& node) noexcept -> void constexpr

append the node to the front

Parameters
node in/out

template<typename T>
auto Dllist<T>::append(Dllink<T>& node) noexcept -> void constexpr

append the node to the back

Parameters
node in/out

template<typename T>
auto Dllist<T>::popleft() noexcept -> Dllink< T > & constexpr

pop a node from the front

Returns Dllist&

Precondition: list is not empty

template<typename T>
auto Dllist<T>::pop() noexcept -> Dllink< T > & constexpr

pop a node from the back

Returns Dllist&

Precondition: list is not empty

template<typename T>
auto Dllist<T>::begin() noexcept -> DllIterator< T > constexpr

begin

Returns DllIterator

template<typename T>
auto Dllist<T>::end() noexcept -> DllIterator< T > constexpr

end

Returns DllIterator