#include
using namespace std;
template
struct list_node
{
list_node* next; // 指向下一个节点的指针
list_node* prev; // 指向前一个节点的指针
T data; //list 数据
};
template
class list;
template
class list_iterator
{
public:
friend class list;
private:
typedef list_node* link_type;
list_node* node;//数据成员 ,为一个节点的指针。
//比较iterator是否相等
public:
list_iterator()
{
}
list_iterator(list_node<T>* p)
{
node = p ;
}
int operator==(const list_iterator<T>& x) const
{
return node == x.node;
}
int operator!=(const list_iterator<T>& x) const
{
return node != x.node;
}
//*操作符,使得访问iterator就像访问一个指针
T& operator*() const
{
return (*node).data;
}
//自增操作符. ++
list_iterator& operator++()
{
node = (link_type)((*node).next); //使iterator包含的是下一个节点
return *this;
}
//自减操作符 --
list_iterator& operator--()
{
node = (link_type)((*node).prev);
return *this;
}
};
template
class list
{
public:
typedef list_iterator iterator;
typedef list_node* link_type;
private:
link_type node;
link_type node_head;
link_type node_end;
link_type node_tend;
size_t length; //list的长度。
public:
//默认构造函数,创建一个空的list
list()
{
length = 0;
node_end = node_head = NULL;
node = node_end;
}
~list()
{
this->clear();
}
public:
iterator begin()
{
list_iterator p_ite;
p_ite = node_head;
return p_ite;
}
//返回list的末节点。注意,末节点是最后一个元素的下一个节点。末节点不包含元素的值
iterator end()
{
list_iterator p_ite;
p_ite = node_end->next;
return p_ite;
}
//判断是否为空
bool empty() const
{
return length == 0;
}
// 返回list的长度
size_t size() const
{
return length;
}
//返回list的头部 值引用
T& front()
{
return begin();
}
//返回list的末尾 值的引用
T& back()
{
return *(--end());
}
//在指定iterator之前插入新结点
void insert(list_iterator position,int n, const T& x)//insert(插入的位置,插入的个数,插入的数值)
{
for(int i=0;i
{
list_node temp = new list_node;
temp->data = x;
temp->next = position.node;
position.node->prev->next = temp;
temp->prev = position.node->prev;
position.node->prev = temp;
position.node = temp;
}
}
// 在头部插入一个元素
void push_front(const T& x)
{
insert(begin(),1,x);
}
//在尾部插入一个元素
void push_back(const T& x)
{
list_node* temp = new list_node;
temp->data = x;
temp->next = NULL;
temp->prev = NULL;
//如果链表为空
if(node_head == NULL)
{
node_head = node_end = temp;
}
//若果有多个节点
else
{
node_end->next = temp;
temp->prev = node_end;
}
node_end = temp;
length++;
}
// 删除一个结点
iterator erase(list_iterator position)
{
link_type next_node = (link_type)position.node->next;
link_type prev_node = (link_type)position.node->prev;
prev_node->next = next_node;
next_node->prev = prev_node;
delete(position.node);
--length; //长度减1
return iterator(next_node);
}
// 清空一个list的所有元素
void clear()
{
list_node* temp = node_head;
list_node* deltemp = NULL;
while(temp != NULL)
{
if(temp->next == NULL)
{
delete temp;
temp = NULL;
break ;
}
deltemp = temp;
temp = temp->next;
delete deltemp;
deltemp = NULL;
}
length = 0;
node_end = node_head = NULL;
node = node_end;
}
//删除头部元素
void pop_front()
{
erase(begin());
}
//删除尾部元素
void pop_back()
{
iterator temp = end();
erase(temp);
}
list(int a)
{
length = 0;
node_end = node_head = NULL;
node = node_end;
for(int i=0;i<a;i++)
{
push_back(0);
}
}
list(int a,int b)
{
length = 0;
node_end = node_head = NULL;
node = node_end;
for(int i=0;i<a;i++)
{
push_back(b);
}
}
};