// list.h
#pragma once
#include <memory>
#include <iostream>

template<typename T> struct node;  // node提前申明
#define ptr std::shared_ptr<node<T>>  

template<typename T> struct node {
    node() : succ(nullptr) {  }
    node(T e) : data(e), succ(nullptr) { }
    ~node() { std::cout  << data << " node has been auto released\n"; }
    ptr AsSucc(T const& e);
    ptr succ;
    T data;
};

template<typename T> inline ptr node<T>::AsSucc(const T & e)
{
    ptr x = std::make_shared<node<T>>(e);
    if (!x) return nullptr;
    x->succ = succ;
    succ = x;
    std::cout << "create node, address: [ " << x << " ] value: " << x.get()->data << std::endl;
    return nullptr;
}

// list
template<typename T> class list {
public:
    list() { std::cout << "list has been created" << std::endl; init(); }
    ~list() {
        remove_all();
        std::cout << "list has been destroyed\n";
    }
public:
    const int size() const { return m_size; }
    const bool empty() const { return m_size <= 0; }
    ptr PushFront(const T& e);
    ptr PushBack(const T& e);
    ptr InsertAsSucc(const T& e, ptr p);
    void PopFront();
    void PopBack();
    void Remove(ptr p);
    void Remove(const T & e, bool bDelSame);
    void travel();
private:
    void init();
    void remove_all();
    ptr tail();
    ptr pred_tail();
private:
    ptr m_head;
    int m_size;
};

template<typename T> void list<T>::init()
{
    m_head = std::make_shared<node<T>>();
    if (!m_head) return;
    std::cout << "create guard node, address: [ " << m_head << " ] value: " 
              << m_head.get()->data << std::endl;
    m_head->succ = nullptr;
    m_size = 0;
}

template<typename T> inline void list<T>::remove_all()
{
    // 由于是智能指针，无需释放节点。要释放也不是不行，孤立节点即可。
    while (m_size != 0) 
        PopFront();

    std::cout << "release gurad node, adrress: [ 0x" << m_head.get() << " ] value: ";
    m_head = nullptr;
    m_size = 0;
}

template<typename T> inline ptr list<T>::PushFront(const T& e) {
    m_size++;
    return m_head->AsSucc(e);
}

template<typename T> inline ptr list<T>::PushBack(const T& e)
{
    auto p = tail();
    m_size++;
    return p->AsSucc(e);
}

template<typename T> ptr list<T>::InsertAsSucc(const T& e, ptr p) {
    m_size++;
    return p->AsSucc(e);
}

template<typename T>
inline void list<T>::PopFront()
{
    m_size--;
    // 孤立节点p之后，节点p自动释放
    ptr p = m_head->succ;
    m_head->succ = p->succ;
    std::cout << "pop from front adrress: [ 0x" << p.get() << " ] value: ";
    p = nullptr;
}

template<typename T> inline void list<T>::PopBack()
{
    m_size--;
    // 孤立节点p之后，节点p自动释放
    ptr p = pred_tail();
    p->succ = nullptr;
    std::cout << "pop from back adrress: [ 0x" << p.get() << " ] value: ";
    p = nullptr;
}

template<typename T> inline void list<T>::Remove(ptr p)
{
    if (p == nullptr || p->succ == nullptr) return;
    // 孤立节点q之后，节点q自动释放
    auto q = p->succ;
    p->succ = p->succ->succ;
    q->succ = nullptr;
    std::cout << "remove element adrress: [ 0x" << p.get() << " ] value: ";
    q = nullptr;
    m_size--;
}

template<typename T> inline void list<T>::Remove(const T& e, bool bDelSame)
{
    if (m_size <= 0) return;
    for (auto curr = m_head->succ; curr->succ != nullptr; curr = curr->succ) 
    {
        while (curr->data == e || curr->succ->data == e) 
        {
            if (curr->data == e) 
            {
                PopFront();
                if (!bDelSame || (curr = m_head) == nullptr)
                    return;
            }
            else if (curr->succ->data == e) 
            {
                Remove(curr);
                if (!bDelSame || curr->succ == nullptr) 
                    return;
            }
        }
    }
}

template<typename T>
inline void list<T>::travel()
{
    for (auto p = m_head->succ; p != nullptr; p = p->succ)
        std::cout << p->data << " ";
    std::cout << std::endl;
}

template<typename T>
ptr list<T>::tail()
{
    ptr tail = nullptr;
    for (tail = m_head; tail != nullptr && tail->succ != nullptr; tail = tail->succ);
    return tail;
}

template<typename T>
ptr list<T>::pred_tail()  // 可恶，没有指向前驱的指针，所以还得重新找尾节点的前驱
{
    ptr pred = NULL;
    for (pred = m_head; pred != nullptr && pred->succ != nullptr 
        && pred->succ->succ != nullptr; pred = pred->succ);
    return pred;
}

// test.cpp
#include "list.h"

int main() {
    list<int> l;
    l.PushBack(3);
    l.PushBack(6);
    l.PushBack(3);
    l.PushBack(4);
    l.PushBack(5);
    l.PushBack(3);
    l.PushBack(4);
    l.PushBack(3);
    l.travel();
    l.Remove(3, true);
    l.Remove(4, true);
    l.travel();
    return 0;
}

测试结果：