C++实现双链表基本接口

柔光的暖阳◎ 2022-06-12 08:20 218阅读 0赞

#### **首先先简单通过图示区分单链表和双链表的结构差异：** ####

![这里写图片描述][SouthEast]

--------------------

#### **单链表的基本接口实现可参考：[单链表简单实现][Link 1]** ####

--------------------

#### **接下来就是双链表的基本接口实现：** ####

#include <iostream>
    #include <assert.h>
    using namespace std;
    
    typedef int DataType;
    
    struct ListNode
    {
        ListNode* _next;
        ListNode* _prev;
        DataType _data;
    
        ListNode(DataType x)
            :_next(NULL)
            , _prev(NULL)
            , _data(x)
        {}
    };
    
    typedef ListNode Node;
    
    class List
    {
    
    public:
        List()
            :_head(NULL)
            ,_tail(NULL)
        {}
    
        List(const List& l)
            :_head(NULL)
            ,_tail(NULL)
        {
            Copy(l);
        }
    
        void Copy(const List& l)
        {
            Node* cur = l._head;
            while (cur)
            {
                PushBack(cur->_data);
                cur = cur->_next;
            }
        }
    
        List& operator=(const List& l)
        {
            Destory();
            Copy(l);
            return *this;
        }
    
        ~List()
        {
            Destory();
        }
    
        void Destory()
        {
            if (_head)
            {
                Node* cur = _head;
                while (_head)
                {
                    cur = _head;
                    _head = _head->_next;
                    delete cur;
                }
                _head = _tail = NULL;
            }
        }
    
        void PushBack(DataType x)
        {
            if (_head == NULL)
            {
                Node* tmp = new Node(x);
                tmp->_next = tmp->_prev = NULL;
                _head = _tail = tmp;
            }
            else
            {
                Node* tmp = new Node(x);
                _tail->_next = tmp;
                tmp->_prev = _tail;
                _tail = tmp;
            }
        }
    
        void PopBack()
        {
            if (_head == NULL)
            {
                return;
            }
            else if (_head->_next == NULL)
            {
                delete _head;
                _head = _tail = NULL;
            }
            else
            {
                Node* tmp = _tail;
                _tail = _tail->_prev;
                _tail->_next = NULL;
                delete tmp;
            }
        }
    
        void PushFront(DataType x)
        {
            if (_head == NULL)
            {
                _head = _tail = new Node(x);
            }
            else
            {
                Node* tmp = new Node(x);
                tmp->_next = _head;
                _head->_prev = tmp;
                _head = _head->_prev;
            }
        }
    
        void PopFront()
        {
            if (_head == NULL)
            {
                return;
            }
            else if (_head->_next == NULL)
            {
                delete _head;
                _head = _tail = NULL;
            }
            else
            {
                Node* tmp = _head;
                _head = _head->_next;
                delete tmp;
                _head->_prev = NULL;
            }
        }
    
        Node* Find(DataType x)
        {
            Node* cur = _head;
            while (cur)
            {
                if (cur->_data == x)
                    return cur;
                cur = cur->_next;
            }
            return NULL;
        }
    
        // 在pos的前面插入x
        void Insert(Node* pos, DataType x)
        {
            assert(pos);
            if ((pos == 0) || (pos->_prev == NULL))
            {
                PushFront(x);
            }
            else
            {
                Node* font = pos->_prev;
                Node* tmp = new Node(x);
                tmp->_prev = font;
                tmp->_next = pos;
                font->_next = tmp;
                pos->_prev = tmp;
            }
        }
    
        //删除pos位置的元素
        void Erase(Node* pos)
        {
            assert(pos);
            if ((pos == 0) || (pos->_prev == NULL))
            {
                PopFront();
            }
            else if (pos->_next == NULL)
            {
                PopBack();
            }
            else
            {
                Node* font = pos->_prev;
                Node* last = pos->_next;
                font->_next = last;
                last->_prev = font;
                delete pos;
            }
        }
    
        //逆序整个双链表
        void Reverse()
        {
            Node* cur = _head;
            while (cur)
            {
                swap(cur->_next,cur->_prev);
                cur = cur->_prev;
            }
            swap(_head, _tail);
        }
    
    
        void Print()
        {
            Node* cur = _head;
            while (cur)
            {
                cout << cur->_data << "->";
                cur = cur->_next;
            }
            cout << "NULL" << endl;
        }
    
    private:
        Node* _head;
        Node* _tail;
    };

--------------------

#### **注：在一些操作实现时，一定要要考虑清楚各种情况，再进行情况的分类尽量提高代码的复用程度。** ####

[SouthEast]: /images/20220612/6e3e68a6f4364e0db5cd19fee3c5156d.png
[Link 1]: http://blog.csdn.net/sssssuuuuu666/article/details/75400679