#includeiostream#includestring#includestdexceptusing namespace std;templatetypename Eclass Dlist{struct Node{E val;Node *next;//后驱Node *prev;//前驱Node(const E value):val(value),next(nullptr),prev(nullptr){}};Node *head;//哨兵头Node *tail;//哨兵尾int size;//检查索引是否为合法的元素索引 (0,size-1)bool isElementIndex(int index)const{return index0 indexsize;}//检查索引是否为合法的插入位置(0,size]bool isPositionIndex(int index)const{return index0 indexsize;}void checkElementIndex(int index)const{if(!isElementIndex(index)){throw out_of_range(Index: to_string(index),sizeto_string(size));}}void checkPositionIndex(int index)const{if(!isPositionIndex(index)){throw out_of_range(Index: to_string(index),sizeto_string(size));}}Node *getNode(int index)const{if(indexsize/2){ //根据索引位置决定从头找还是从尾找Node *phead-next; //头节点向后遍历for(int i0;iindex;i){pp-next;}return p;}else{Node *ptail-prev; //尾节点向前遍历for(int isize-1;iindex;i--){pp-prev;}return p;}}public:Dlist(){headnew Node(E()); // 创建头哨兵tailnew Node(E()); // 创建尾哨兵head-nexttail; //初始状态 头指向尾 尾指向头tail-prevhead;size0;}~Dlist(){while(size0){removeFirst();}delete head;delete tail;}void addFirst(const E e){Node *newNodenew Node(e);Node *temphead-next;//暂存第一个真实结点temp-prevnewNode;newNode-nexttemp;head-nextnewNode;newNode-prevhead;size;}void addLast(const E e){Node* newNodenew Node(e);Node* temptail-prev; //暂存最后一个真实节点temp-nextnewNode;newNode-prevtemp;newNode-nexttail;tail-prevnewNode;size;}void insert(int index,const E element){checkPositionIndex(index);if(indexsize){addLast(element);return ;}//找到前驱Node *pgetNode(index);Node *prevp-prev;Node *newNodenew Node(element);// 将 newNode 插入到 prev 和 p 之间p-prevnewNode;prev-nextnewNode;newNode-prevprev;newNode-nextp;size;}// 获取链表当前元素个数int size1() const{return size;}// 判断链表是否为空bool isEmpty()const{return size0;}E removeFirst(){if(isEmpty()){throw out_of_range(No elemnets to remove);}Node *xhead-next;Node *tempx-next;head-nexttemp;temp-prevhead;E valx-val;x-prevnullptr;x-nextnullptr;delete x;size--;return val;}E removeLast(){if(isEmpty())throw out_of_range(No elements to remove);Node *xtail-prev;Node *tempx-prev;tail-prevtemp;temp-nexttail;E valx-val;x-prevnullptr;x-nextnullptr;delete x;size--;return val;}E remove(int index){checkElementIndex(index);Node *xgetNode(index); // 找到目标节点Node *prevx-prev;Node *nextx-next;// 将目标节点的前驱和后继相连 实现摘除目标节点prev-nextnext;next-prevprev;E valx-val;x-prevnullptr;x-nextnullptr;delete x;size--;return val;}// 获取第一个元素E getFirst()const{if(isEmpty()){throw out_of_range(No elements in the list);}return head-next-val;}// 获取最后一个元素E getLast()const{if(isEmpty()){throw out_of_range(No elements in the list);}return tail-prev-val;}// 获取指定位置的元素E get(int index) const {checkElementIndex(index);Node* p getNode(index);return p-val;}// 修改指定位置的元素并返回旧值E set(int index,const E element){checkElementIndex(index);Node *pgetNode(index);E oldvalp-val;p-valelement;return oldval;}//打印链表内容void print()const{coutsizesizeendl;Node *phead-next;// 从第一个真实节点开始while(p!tail){ // 遇到尾哨兵即停止coutp-val;if(p-next!tail){cout-;// 非最后一个元素时打印连接符}pp-next;}cout-nullendl;}};int main(){Dlistintlist;list.addLast(1);list.addFirst(0);list.addLast(2);list.insert(2,100);cout初始链表:endl;list.print();coutremoveFirst:list.removeFirst()endl;coutremoveLast:list.removeLast()endl;coutremove(1):list.remove(1)endl;cout \n删除后链表: endl;list.print();coutgetFirst:list.getFirst()endl;coutgetLast:list.getLast()endl;coutget(0)list.get(0)endl;cout \nset(0, 999) 旧值: list.set(0, 999) endl;cout修改后endl;list.print();cout\nsize:list.size1()endl;coutisEmpty:list.isEmpty()endl;return 0;}