C++实现双向链表（List）分享！

list是C++容器类中的“顺序存储结构”所包含的一种结构。list是非连续存储结构，具有双链表结构，支持前向/后向遍历，且支持高效的随机删除/插入。

实现代码如下：

**list.h**

  #pragma once    #include<stdio.h>  #include<assert.h>  #include<iostream>  using namespace std;    typedef int DataType;    struct ListNode  {   ListNode* _next;   ListNode* _prev;     DataType _data;     ListNode(DataType x)    :_data(x)    , _next(NULL)    , _prev(NULL)   {}  };

**test.cpp**

  #define _CRT_SECURE_NO_WARNINGS 1    #include "list.h"    class List{   typedef ListNode Node;  public:   List()    :_head(new Node(DataType())){    _head->_next = _head;    _head->_prev = _head;   }     List(const List& l)    :_head(new Node(DataType())){    _head->_next = _head;    _head->_prev = _head;    Node* cur = l._head->_next;    while (cur!=l._head){     PushBack(cur->_data);     cur = cur->_next;    }   }     List& operator=(const List& l){    if (this != &l){     //swap(_head, l._head);    }    return *this;   }     ~List(){    Node* cur = _head->_next;    while (cur != _head){     Node* next= cur->_next;     delete cur;     cur = next;    }    delete _head;    _head = NULL;   }     void PushBack(DataType x){    Node* prev = _head->_prev;    Node* new_node = new Node(x);    prev->_next = new_node;    new_node->_prev = prev;    _head->_prev = new_node;    new_node->_next = _head;   }     void PushFront(DataType x){//插在头结点之后    Node* cur = _head->_next;    Node* new_node = new Node(x);    new_node->_next = cur;    cur->_prev = new_node;    new_node->_prev = _head;    _head->_next = new_node;   }     void PopBack(){    Node* delete_node = _head->_prev;    Node* cur = delete_node->_prev;    _head->_prev = cur;    cur->_next = _head;    delete delete_node;   }     void PopFront(){    Node* delete_node = _head->_next;    Node* cur = delete_node->_next;      _head->_next = cur;    cur->_prev = _head;    delete delete_node;   }     Node* Find(DataType x){    Node* to_find = _head->_next;    while (to_find != _head){     if (to_find->_data == x){      return to_find;     }     to_find = to_find->_next;    }    return NULL;   }     void Insert(Node* pos, DataType x){//在pos位置前插入数据    assert(pos);    Node* new_node = new Node(x);    Node* prev = pos->_prev;    new_node->_next = pos;    pos->_prev = new_node;    new_node->_prev = prev;    prev->_next = new_node;   }     void Erase(Node* pos){    assert(pos);    Node* prev = pos->_prev;    Node* next = pos->_next;    prev->_next = next;    next->_prev = prev;    delete pos;   }     void Print() const{    Node* cur = _head->_next;    cout <<" _head->";    while (cur!= _head){     cout << cur->_data << "->";     cur = cur->_next;    }    cout << endl;    Node* pos = _head->_prev;    while (pos != _head){     cout << pos->_data << "<-";     pos = pos->_prev;    }    cout << "_head" << endl;   }  private:   Node* _head;  };    void TestList(){   List L;   L.PushBack(1);   L.PushBack(2);   L.PushBack(4);   L.PushBack(5);   L.PopBack();   L.Print();     ListNode* pos = L.Find(1);    printf("pos->data：%d[%p]n",pos->_data,pos);   pos = L.Find(2);   printf("pos->data：%d[%p]n", pos->_data, pos);   pos = L.Find(4);   printf("pos->data：%d[%p]n", pos->_data, pos);   printf("n");     L.Insert(pos, 3);   L.Print();   L.Erase(pos);   L.Print();   printf("n");     List L1;   L1.PushFront(4);   L1.PushFront(3);   L1.PushFront(2);   L1.PushFront(1);   L1.Print();   L1.PopFront();   L1.Print();    }    int main(){   TestList();   return 0;  }

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持<计算机技术网(www.ctvol.com)!!>。

—-想了解C++实现双向链表（List）分享！全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>