采用哨兵节点的C++双链表实现
#include<iostream>
#include<string>
#include<stdexcept>
using namespace std;
template<typename E>
class 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 index>=0 &&index<size;
}
//检查索引是否为合法的插入位置(0,size]
bool isPositionIndex(int index)const{
return index>=0 &&index<=size;
}
void checkElementIndex(int index)const{
if(!isElementIndex(index)){
throw out_of_range("Index: "+to_string(index)+",size"+to_string(size));
}
}
void checkPositionIndex(int index)const{
if(!isPositionIndex(index)){
throw out_of_range("Index: "+to_string(index)+",size"+to_string(size));
}
}
Node *getNode(int index)const{
if(index<size/2){ //根据索引位置决定从头找还是从尾找
Node *p=head->next; //头节点向后遍历
for(int i=0;i<index;i++){
p=p->next;
}
return p;
}
else{
Node *p=tail->prev; //尾节点向前遍历
for(int i=size-1;i>index;i--){
p=p->prev;
}
return p;
}
}public:
Dlist(){
head=new Node(E()); // 创建头哨兵
tail=new Node(E()); // 创建尾哨兵
head->next=tail; //初始状态 头指向尾 尾指向头
tail->prev=head;
size=0;
}
~Dlist(){
while(size>0){
removeFirst();
}
delete head;
delete tail;
}
void addFirst(const E& e){
Node *newNode=new Node(e);
Node *temp=head->next;//暂存第一个真实结点
temp->prev=newNode;
newNode->next=temp;
head->next=newNode;
newNode->prev=head;
size++;
}
void addLast(const E& e){
Node* newNode=new Node(e);
Node* temp=tail->prev; //暂存最后一个真实节点
temp->next=newNode;
newNode->prev=temp;
newNode->next=tail;
tail->prev=newNode;
size++;
}
void insert(int index,const E& element){
checkPositionIndex(index);
if(index==size){
addLast(element);
return ;
}
//找到前驱
Node *p=getNode(index);
Node *prev=p->prev;
Node *newNode=new Node(element);
// 将 newNode 插入到 prev 和 p 之间
p->prev=newNode;
prev->next=newNode;
newNode->prev=prev;
newNode->next=p;
size++;
}
// 获取链表当前元素个数
int size1() const{
return size;
}
// 判断链表是否为空
bool isEmpty()const{
return size==0;
}
E removeFirst(){
if(isEmpty()){
throw out_of_range("No elemnets to remove");
}
Node *x=head->next;
Node *temp=x->next;
head->next=temp;
temp->prev=head;
E val=x->val;
x->prev=nullptr;
x->next=nullptr;
delete x;
size--;
return val;
}
E removeLast(){
if(isEmpty())
throw out_of_range("No elements to remove");
Node *x=tail->prev;
Node *temp=x->prev;
tail->prev=temp;
temp->next=tail;
E val=x->val;
x->prev=nullptr;
x->next=nullptr;
delete x;
size--;
return val;
}
E remove(int index){
checkElementIndex(index);
Node *x=getNode(index); // 找到目标节点
Node *prev=x->prev;
Node *next=x->next;
// 将目标节点的前驱和后继相连 实现摘除目标节点
prev->next=next;
next->prev=prev;
E val=x->val;
x->prev=nullptr;
x->next=nullptr;
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 *p=getNode(index);
E oldval=p->val;
p->val=element;
return oldval;
}
//打印链表内容
void print()const{
cout<<"size="<<size<<endl;
Node *p=head->next;// 从第一个真实节点开始
while(p!=tail){ // 遇到尾哨兵即停止
cout<<p->val;
if(p->next!=tail){
cout<<"<->";// 非最后一个元素时打印连接符
}
p=p->next;
}
cout<<"->null"<<endl;
}
};
int main(){
Dlist<int>list;
list.addLast(1);
list.addFirst(0);
list.addLast(2);
list.insert(2,100);
cout<<"初始链表:"<<endl;
list.print();
cout<<"removeFirst:"<<list.removeFirst()<<endl;
cout<<"removeLast:"<<list.removeLast()<<endl;
cout<<"remove(1):"<<list.remove(1)<<endl;
cout << "\n删除后链表:" << endl;
list.print();
cout<<"getFirst:"<<list.getFirst()<<endl;
cout<<"getLast:"<<list.getLast()<<endl;
cout<<"get(0)"<<list.get(0)<<endl;
cout << "\nset(0, 999) 旧值: " << list.set(0, 999) << endl;
cout<<"修改后："<<endl;
list.print();
cout<<"\nsize:"<<list.size1()<<endl;
cout<<"isEmpty:"<<list.isEmpty()<<endl;
return 0;
}