#include <iostream>
using namespace std;
template <typename T>
class DualCircleLinkList
{
private:
//数据节点
struct Node
{
T value;
Node* next;
Node* pre;
Node(Node* thePrev=NULL,Node* theNext=NULL)
:next(theNext),pre(thePrev){}
};
//头指针
Node* m_head;
//尾指针
Node* m_tail;
//链表长度
int m_length;
//定位功能函数减少减少代码冗余
Node* position(int i)
{
Node* ret = m_head;
for(int p = 0; p < i; p++)
{
ret = ret->next;
}
return ret;
}
//创建一个节点
Node* create()
{
return new Node();
}
//销毁节点
void destroy(Node* p)
{
delete p;
}
public:
DualCircleLinkList()
{
m_head = NULL;
m_tail = NULL;
m_length = 0;
}
//插入
bool insert(int i, const T& e)
{
bool ret = ((0 <= i) && (i <= m_length));
if(ret)
{
Node* node = create();
if(node != NULL)
{
node->value = e;
}
//如果在头部插入
if(i == 0)
{
//如果链表为空
if(isEmpty())
{
m_head = node;
m_tail = node;
m_tail->next = m_head;
m_head->pre = m_tail;
}
else
{
m_head->pre = node;
node->next = m_head;
//头指针前移
m_head = node;
m_tail->next = m_head;
m_head->pre = m_tail;
}
m_length++;
}
//在链表尾部插入
else if(i == length())
{
//如果链表为空
if(isEmpty())
{
m_head = node;
m_tail = node;
m_tail->next = m_head;
m_head->pre = m_tail;
}
else
{
m_tail->next = node;
node->pre = m_tail;
//尾指针后移
m_tail = node;
m_tail->next = m_head;
m_head->pre = m_tail;
}
m_length++;
}
else
{
//先定位到待插入位置的前一个节点
Node* current = position(i - 1);
node->next = current->next;
node->pre = current;
current->next->pre = node;
current->next = node;
}
m_length++;
}
return ret;
}
//删除指定下标的元素
bool remove(int i)
{
bool ret = ((0 <= i) && (i < m_length));
Node* toDel = NULL;
if(ret)
{
//如果在头部删除
if(i == 0)
{
toDel = m_head;
m_head = m_head->next;
m_head->pre = m_tail;
m_tail->next = m_head;
destroy(toDel);
}
else
{
Node* current = position(i - 1);
toDel = current->next;
if(i == m_length - 1)
{
current->next = m_head;
m_tail = current;
m_head->pre = m_tail;
m_tail->next = m_head;
}
else
{
toDel->next->pre = current;
current->next = toDel->next;
}
destroy(toDel);
}
m_length--;
}
else
{
ret = false;
}
return ret;
}
bool insert(const T& e)
{
return insert(m_length, e);
}
void ShowValue()
{
Node* node = m_head;
do
{
cout << node->value << "->";
node = node->next;
}while(node != m_head);
}
int find(const T& e)
{
int ret = -1;
int i = 1;
Node* slider = m_head;
do
{
if(slider->value == e)
{
ret = i;
break;
}
else
{
slider = slider->next;
i++;
}
}while(slider != m_head);
return ret;
}
void clear()
{
const int size = length();
if(!isEmpty())
{
for(int i = 0; i < size; i++)
{
Node* toDel = m_head->next;
destroy(m_head);
m_head = toDel;
m_length--;
}
}
}
int length()
{
return m_length;
}
bool isEmpty()
{
return m_length == 0 ? true : false;
}
~DualCircleLinkList()
{
clear();
}
};
int main()
{
DualCircleLinkList<int> dl;
for(int i = 0; i < 5; i++)
{
dl.insert(0, i);
}
dl.ShowValue();
dl.remove(4);
cout << endl;
dl.ShowValue();
cout << endl;
return 0;
}
运行结果
