双向链表
主要实现了头插，头删，尾插尾删，任意位置的插入删除，链表的逆置以及链表的深浅拷贝
在这里说明一下，链表用的最多的就是数据的插入什么的，所以这里解决深浅拷贝问题，用的是深拷贝，单链表，顺序表也是一样，都是用了深拷贝。
双向链表相比较于单链表而言，相对复杂一点，有两个指针，来进行实现链式结构
先面试具体代码
#include<iostream>
#include<assert.h>
using namespace std;
typedef int DataType;
struct ListNode
{
ListNode* _next;
ListNode* _prev;
DataType _data;
ListNode(DataType x)
:_next(NULL)
,_prev(NULL)
,_data(x)
{}
};
class List
{
typedef ListNode Node;
public:
List()
:_head(NULL)
,_tail(NULL)
{}
List(const List& l)
:_head(NULL)
,_tail(NULL)
{
//pushback
Copy(l);
}
List& operator=(const List& l)
{
if(this!=&l)
{
Clear();
Copy(l);
}
return *this;
}
~List()
{
Clear();
}
void PushBack(DataType x)
{
if(_head==NULL)
{
_head = _tail = new Node(x);
}
else
{
Node*tmp = new Node(x);
Node*cur = _tail;
cur->_next = tmp;
tmp->_prev = cur;
_tail = tmp;
}
}
void PopBack()
{
if(_head==NULL)
return;
/*else if(_head==_tail)
{
Node*del = _tail;
delete del;
_head = _tail =NULL;
}*/
else
{
Erase(_tail);
// Node*del = _tail;
// Node*prev = _tail->_prev;
// delete del;
// _tail = prev;
}
}
void PushFront(DataType x)
{
if(_head==NULL)
{
_head = _tail = new Node(x);
}
else
{
Node*tmp = new Node(x);
Node*cur = _head;
tmp->_next = cur;
cur->_prev = tmp;
_head = tmp;
}
//Insert(_head,x);
}
void PopFront()
{
if(_head==NULL)
return;
Erase(_head);
}
// 在pos的前面插入一个
void Insert(Node* pos, DataType x)
{
assert(pos);
if(pos==_head)
{
Node*cur = _head;
Node*newhead = new Node(x);
newhead->_next = cur;
cur->_prev = newhead;
_head = newhead;
}
else
{
Node*prev = pos->_prev;
Node*tmp = new Node(x);
prev->_next = tmp;
tmp->_prev = prev;
tmp->_next = pos;
pos->_prev = tmp;
}
}
void Erase(Node* pos)
{
assert(pos);
if(pos==_head)
{
Node*del = _head;
Node*next = _head->_next;
delete del;
del = NULL;
_head = next;
}
else
if(pos==_tail)
{
Node*del = _tail;
Node*prev = _tail->_prev;
prev->_next = del->_next;
delete del;
del = NULL;
_tail = prev;
}
else
{
Node*prev = pos->_prev;
Node*next = pos->_next;
Node*del = pos;
prev->_next = next;
next->_prev = prev;
delete del;
del = NULL;
}
}
Node* Find(DataType x)
{
Node*cur = _head;
while(cur)
{
if(cur->_data==x)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}
void Reverse()
{
if(_head==NULL)
return;
else if(_head==_tail)
return;
else
{
Node*left = _head;
Node*right = _tail;
while((left->_next!= right->_prev)&&(left->_prev != right))
{
swap(left->_data,right->_data);
left = left->_next;
right = right->_prev;
}
}
}
void Print()
{
Node*cur = _head;
while(cur)
{
cout<<cur->_data<<" ";
cur = cur->_next;
}
cout<<endl;
}
void Clear()
{
Node*cur = _head;
while(cur)
{
Node*del = cur;
cur = cur->_next;
delete del;
del = NULL;
}
_head = _tail = NULL;
}
void Copy(const List&l)
{
Node*cur = l._head;
while(cur)
{
PushBack(cur->_data);
cur = cur->_next;
}
}
private:
Node* _head;
Node* _tail;
};
void ListTest()
{
List l1;
l1.PushBack(2);
l1.PushBack(3);
l1.PushBack(4);
l1.PushBack(5);
/*l1.PopBack();
l1.PopBack();
l1.PopBack();
l1.PopBack();
l1.PopBack();*/
//l1.PushFront(5);
//ListNode*ret = l1.Find(5);
//l1.Erase(ret);
//l1.PopBack();
l1.Print();
}
void ListTest1()
{
List l1;
l1.PushBack(2);
l1.PushBack(3);
l1.PushBack(4);
l1.PushBack(5);
l1.Reverse();
/*l1.PopFront();
l1.PopFront();
l1.PopFront();
l1.PopFront();
l1.PopFront();*/
l1.Print();
}
void ListTest2()
{
List l1;
l1.PushBack(2);
l1.PushBack(3);
l1.PushBack(4);
l1.PushBack(5);
List l2(l1);
List l3;
l3 = l1;
l1.Print();
l2.Print();
l3.Print();
}