主要实现双链表如下功能:
void AddBack(T val); //链表尾部添加元素
void AddFront(T val); //链表头部添加元素
bool InsertAt(int pos, T val); //在指定的索引处插入元素
bool RemoveBack(); //尾部删除元素
bool RemoveFront(); //头部删除元素
bool RemoveAt(int pos); //删除指定索引处元素
bool Find(T val); //找到元素返回索引,没找到返回-1
void Clear(); //清空链表
bool IsEmpty();//判断链表是否为空
int Size(); //返回链表元素个数
1.定义链表节点类
template<class T>
class DNode
{
public:
~DNode(void){ }
T val; //节点值
DNode<T>* next; //指向后面节点指针
DNode<T>* prior; //指向前面节点指针
DNode(T nVal)
{
val = nVal;
next = prior = NULL;
}
DNode(void){}
};
2.双链表类定义
#include "DNode.h"
#include <iostream>
using namespace std;
template<class T>
class DLinkList
{
int size;
public:
DNode<T>* head; //指向头部的指针
DNode<T>* tail; //指向尾部指针
DLinkList(void)
{
head = tail = NULL;
size = 0;
}
~DLinkList(void){ Clear(); }
void AddBack(T val) //尾部添加元素
{
DNode<T>* pNode = new DNode<T>(val);
if(head == NULL) //链表为空时
{
head = tail = pNode;
}
else{
tail->next = pNode;
pNode->prior = tail;
tail = pNode; //新节点是尾部节点
}
size ++;
}
void AddFront(T val) //头部添加元素
{
DNode<T>* pNode = new DNode<T>(val);
if(head == NULL) //链表为空时
{
head = tail = pNode;
}
else{
head->prior = pNode;
pNode->next = head;
head = pNode;
}
size ++;
}
bool InsertAt(int
pos, T val) //任意位置插入元素
{
DNode<T>* pNode = NULL;
if(pos < 0 || pos > size){
cout<<"out of range"<<endl;
returnfalse;
}
pNode = new DNode<T>(val);
if(pos == 0) // 头部位置
AddFront(val);
elseif(pos
== size - 1)
AddBack(val);
else{
DNode<T>* priorNode = GetPointerAt(pos - 1);
pNode->next = priorNode->next;
pNode->prior = priorNode;
priorNode->next->prior = pNode;
priorNode->next = pNode;
}
size++;
return true;
}
bool RemoveAt(int
pos) //删除指定索引处元素
{
DNode<T>* pNode =NULL;
if(size == 0){
cout<<"list is empty"<<endl;
returnfalse;
}
if(pos < 0 || pos > size - 1){
cout<<"out of range"<<endl;
returnfalse;
}
if(size == 1)
Clear();
else{
if(pos == 0) //头部位置
{
pNode = head;
head = head->next;
head->prior = NULL;
delete pNode;
}
else{
DNode<T>* priorNode = GetPointerAt(pos - 1);
pNode = priorNode->next;
priorNode->next = pNode->next;
pNode->next->prior = priorNode;
delete pNode;
if(pos == size - 1) //如果是尾部元素
tail = priorNode;
}
}
}
bool RemoveBack(){return
RemoveAt(size - 1);}
bool RemoveFront(){return
RemoveAt(0);}
int Find(T val)
{
int index = 0;
DNode<T>* ip = head;
while(ip != NULL){
if(ip->val == val)
return index;
ip = ip->next;
index++;
}
return -1;
}
bool IsEmpty(){return
size == 0 ?true:false;}
int Size(){return
size;}
void Clear(){
while(head != NULL){
DNode<T>* tmp = head->next;
delete head;
head = tmp;
}
tail = NULL;
size = 0;
}
private:
DNode<T>* GetPointerAt(int pos)
{
DNode<T>* pNode = NULL;
if(pos < 0 || pos>size - 1)
cout<<"out of range"<<endl;
else{
pNode = head;
for(int
i = 1; i<= pos; i++)
pNode = pNode->next;
}
return pNode;
}
};