3-链表

动态数组有个明显的缺点，可能造成内存空间的大量浪费；
能否用到多少就申请多少内存？ 链表可以办到；
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的；

单向链表和双向链表：
复杂度一样，但是双向链表的操作复杂度比单向链表缩小了一半

数组查找元素的复杂度都是O(1)，因为无论是list[0]还是list[100]，会计算出内存地址(index * 数据类型长度 + 首地址)，然后直接访问内存地址；

总结一下数组和链表的比较：

• 动态数组：开辟和销毁内存空间次数相对较少，但可能会造成内存浪费

• 双向链表：开辟和销毁内存空间次数相对较多，但不会造成内存空间的浪费

• 如果频繁在尾部进行添加/删除操作，建议动态数组、双向链表均可选择

• 如果频繁在头部进行添加/删除操作，建议选择双向链表

• 如果有频繁任意位置添加/删除操作，建议选择双向链表

• 如果有频繁的查询操作，建议选择动态数组

ps: 循环双向链表
template<class E>
class CircleLinkList: public AbstractList<E> {

public:
    BDListNode<E> *m_first{nullptr};
    BDListNode<E> *m_last{nullptr};
    BDListNode<E> *m_current{nullptr};

    CircleLinkList() = default;
    ~CircleLinkList() {
        BDListNode<E> *node = m_first;
        while (this->m_size > 0) {
            BDListNode<E> *tmp = node->next;
            delete node;
            node = tmp;
            this->m_size--;
        }
        m_first = nullptr;
        m_last = nullptr;
        m_current = nullptr;
    }

    //让current指向头结点
    void reset() {
        m_current = m_first;
    }

    //让current往后走一步
    E next() {
        if (m_current == nullptr) {
            return E();
        }
        m_current = m_current->next;
        return m_current->val;
    }

    //删除current指向的节点，删除后让current往前走
    E remove() {
        if (m_current == nullptr) {
            return E();
        }
        E oldVal = m_current->val;
        BDListNode<E> *next = m_current->next;
        remove(m_current);
        if (this->m_size == 0) {
            m_current = nullptr;
        } else {
            m_current = next;
        }
        return oldVal;
    }

    /**
    * 清除所有元素
    */
    void clear() {
        BDListNode<E> *node = m_first;
        while (this->m_size > 0) {
            BDListNode<E> *tmp = node->next;
            delete node;
            node = tmp;
            this->m_size--;
        }
        m_first = nullptr;
        m_last = nullptr;
        m_current = nullptr;
    }

    /**
     * 添加元素到尾部
     * @param element
     */
    void add(E element) {
        add(this->m_size, element);
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    E get(int index) {
        return node(index)->val;
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     * @return 原来的元素ֵ
     */
    E set(int index, E element) {
        BDListNode<E> *old = node(index);
        E oldE = old->val;
        old->val = element;
        return oldE;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    void add(int index, E element) {
        this->rangeCheckForAdd(index);
        if (index == this->m_size) {//添加最后一个, next要指向头结点
            BDListNode<E> *oldLast = m_last;
            auto *newN = new BDListNode<E>(element);
            if (oldLast == nullptr) {//只有一个
                newN->prev = newN;
                newN->next = newN;
                m_first = newN;
                m_last = newN;

            } else {
                newN->prev = oldLast;
                newN->next = m_first;
                oldLast->next = newN;
                m_first->prev = newN;
                m_last = newN;
            }
        } else {

            BDListNode<E> *old = node(index);
            BDListNode<E> *prev = old->prev;

            auto *newN = new BDListNode<E>(prev, element, old);
            old->prev = newN;
            prev->next = newN;

            if (old == m_first) {//在0位置添加
                m_first = newN;
            }
        }
        this->m_size++;

    }

    /**
     * 删除index位置的元素
     * @param index
     * @return
     */
    E remove(int index) {
        this->rangeCheck(index);
        return remove(node(index));
    }
    E remove(BDListNode<E> *old) {
        if (this->m_size == 1) {
            m_first = nullptr;
            m_last = nullptr;

        } else {
            BDListNode<E> *prev = old->prev;
            BDListNode<E> *next = old->next;
            prev->next = next;
            next->prev = prev;

            if (old == m_first) {//删除第一个
                m_first = next;
            }
            if (old == m_last) {//删除最后一个
                m_last = next;
            }
        }
        E oldValue = old->val;
        delete old;
        this->m_size--;
        return oldValue;
    }
    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    int indexOf(E element) {
        BDListNode<E> *old = m_first;
        for (int i = 0; i < this->m_size; i++) {
            if (old->val == element) return i;
            old = old->next;
        }

        return ELEMENT_NOT_FOUND;
    }

    string toString() {
        std::ostringstream os;
        os << "size = " << this->m_size << ", 元素 = [";
        BDListNode<E> *node = m_first;
        while (node != nullptr && node->next != m_first) {
            BDListNode<E> *p = node->prev;
            BDListNode<E> *n = node->next;
            os << ( (p != nullptr) ? std::to_string(p->val) : "null") << "_" << node->val << "_" << ((n != nullptr)? std::to_string(n->val) : "null");
            node = node->next;
            if (node->next != m_first) {
                os << ", ";
            }
        }

        os << "]" << std::endl;
        std::cout << os.str() << std::endl;
        return os.str();
    }

private:
    BDListNode<E>* node(int index) {
        this->rangeCheck(index);

        if (index < (this->m_size >> 1)) {
            BDListNode<E> *node = m_first;
            for (int i = 0; i < index; i++) {
                node = node->next;
            }
            return node;
        } else {
            BDListNode<E> *node = m_last;
            for (int i = this->m_size - 1; i > index; i--) {
                node = node->prev;
            }
            return node;
        }
    }
};