C++双向链表

双向链表顾名思义就是每个结点具有两个指针，一个指向前一个结点，一个指向后一个结点，我们不必拘束与单链表的创建遍历操作等，这样大大减少了使用中存在的效率问题。



在单链表中，我们有一个数据域还有一个指针域，数据域用来存储相关数据，而指针域负责链表之间的“联系”，双向链表具有两个指针域，一个负责向后连接，一个负责向前连接。

//单链表结构
template<class T>
struct List{
    T data;
    struct List* next;
};
//双向链表结构
template<class T>
struct DNode{
	public:
		T value;
		DNode *prev;
		DNode *next;
};

同单链表一样，对双向链表的操作也有创建，插入，遍历，删除，销毁。

双向链表的创建

struct DNode{
	public:
		T value;
		DNode *prev;
		DNode *next;
	public:
		DNode(){
		}
		DNode(T t,DNode *prev,DNode *next){
			this->value=t;
			this->prev=prev;
			this->next=next;
		}
};

在创建双向链表的时候，我们需要初始化的有两个指针。同单链表一样，我们需要一个头指针来标志链表的信息。因此我们可以写出该函数的定义：运用构造函数创建双向链表

双向链表具体操作：

template<class T>
class DoubleCircleList{
	public:
		DoubleCircleList();  //构造函数 创建链表 
		~DoubleCircleList();  //析构函数 销毁链表 	
		int size();	//长度 
		int is_empty();//判断是否为空 
		T get(int index); //返回index值的位置 
		T get_first();//返回第一个位置 
		T get_last();//返回最后一个位置 
		int insert(int index,T t);//在index位置后插入数值 
		int insert_first(T t);//在头插入 
		int append_last(T t);//在尾插入 
		int Delete(int index);//删除index值 
		int Delete_first();//删除头结点 
		int Delete_last();//删除尾结点 
	private:
		int count;
		DNode<T>* phead;
		DNode<T>* get_node(int index);
};

1.计算链表的长度

template<class T>
DoubleCircleList<T>::DoubleCircleList():count(0){
	//创建“表头 ，注意：表头没有存储数据！ 
	phead=new DNode<T>();
	phead->prev=phead->next=phead;
	//设置链表计数为0
	//cout=0; 
}

2.销毁链表

//析构函数   销毁链表
template<class T>
DoubleCircleList<T>::~DoubleCircleList(){
	DNode<T>* ptmp;   
	DNode<T>* pnode=phead->next;	
	while(pnode!=phead){	//一直循环往后找 
		ptmp=pnode;	//
		pnode=pnode->next;
		delete ptmp;
	}
	delete phead;
	phead=NULL;
}





3.计算结点的数目

//返回结点数目
template<class T>
int DoubleCircleList<T>::size(){
	return count;
}

4.判断链表是否为空

template<class T>
int DoubleCircleList<T>::is_empty(){
	return count==0;
} 

5.寻找结点位置

template<class T>
DNode<T>* DoubleCircleList<T>::get_node(int index){
	//判断参数有效性
	if(index<0||index>=count){
		cout<<"get node failed! the index in out of bound!"<<endl;
		return NULL;
	} 
	//正向查找 
	if(index<=count/2){
		int i=0;
		DNode<T>* pindex=phead->next;
		while(i++<index){
			pindex=pindex->next;
		}
		return pindex;
	}
	//反向查找
	 int j=0;
	 int rindex=count-index-1;
	 DNode<T>* prindex=phead->prev;
	 while(j++<rindex){
	 	prindex=prindex->prev;
	 }
	 return prindex;
}

6.返回结点位置的值

template<class T>
T DoubleCircleList<T>::get(int index){
	return get_node(index)->value;
}

7.获取第一个结点的值

template<class T>
T DoubleCircleList<T>::get_first(){
	return get_node(0)->value;
} 

8.获取最后一个结点的值

template<class T>
T DoubleCircleList<T>::get_last(){
	return get_node(count-1)->value;
} 

9.将结点插入index之后

template<class T>
int DoubleCircleList<T>::insert(int index,T t){
	if(index==0)
		return insert_first(t);
	DNode<T>* pindex=get_node(index);
	DNode<T>* pnode=new DNode<T>(t,pindex->prev,pindex);
	pindex->prev->next=pnode;
	pindex->prev=pnode;
	count++;
	return 0;

}

10.结点插入到第一个位置

//将结点插入到第一个结点处
template<class T>
int DoubleCircleList<T>::insert_first(T t){
	DNode<T>* pnode=new DNode<T>(t,phead,phead->next);
	phead->next->prev=pnode;
	phead->next=pnode;
	count++;
	return 0;
} 

11.结点插入到最后一个位置

template<class T>
int DoubleCircleList<T>::append_last(T t){
	DNode<T>* pnode=new DNode<T>(t,phead->prev,phead);
	phead->prev->next=pnode;
	phead->prev=pnode;
	count++;
	return 0;
} 

12.删除index结点.

template<class T>
int DoubleCircleList<T>::Delete(int index){
	DNode<T>* pindex=get_node(index);
	pindex->next->prev=pindex->prev;
	pindex->prev->next=pindex->next;
	delete pindex;
	count--;
	return 0;
}

13.删除第一个结点

template<class T>
int DoubleCircleList<T>::Delete_first(){
	return Delete(0);
} 

14.删除最后一个结点

template<class T>
int DoubleCircleList<T>::Delete_last(){
	return Delete(count-1);
} 

完整代码：

//DoubleCircleList.h
#include<iostream>
using namespace std;
template<class T>
struct DNode{
	public:
		T value;
		DNode *prev;
		DNode *next;
	public:
		DNode(){
		}
		DNode(T t,DNode *prev,DNode *next){
			this->value=t;
			this->prev=prev;
			this->next=next;
		}
};
template<class T>
class DoubleCircleList{
	public:
		DoubleCircleList();  //构造函数 创建链表 
		~DoubleCircleList();  //析构函数 销毁链表 	
		int size();	//长度 
		int is_empty();//判断是否为空 
		T get(int index); //返回index值的位置 
		T get_first();//返回第一个位置 
		T get_last();//返回最后一个位置 
		int insert(int index,T t);//在index位置后插入数值 
		int insert_first(T t);//在头插入 
		int append_last(T t);//在尾插入 
		int Delete(int index);//删除index值 
		int Delete_first();//删除头结点 
		int Delete_last();//删除尾结点 
	private:
		int count;
		DNode<T>* phead;
		DNode<T>* get_node(int index);
};
template<class T>
DoubleCircleList<T>::DoubleCircleList():count(0){
	//创建“表头 ，注意：表头没有存储数据！ 
	phead=new DNode<T>();
	phead->prev=phead->next=phead;
	//设置链表计数为0
	//cout=0; 
}
//析构函数 
template<class T>
DoubleCircleList<T>::~DoubleCircleList(){
	DNode<T>* ptmp;   
	DNode<T>* pnode=phead->next;	
	while(pnode!=phead){	//一直循环往后找 
		ptmp=pnode;	//
		pnode=pnode->next;
		delete ptmp;
	}
	delete phead;
	phead=NULL;
}
//返回结点数目
template<class T>
int DoubleCircleList<T>::size(){
	return count;
}
template<class T>
int DoubleCircleList<T>::is_empty(){
	return count==0;
} 
template<class T>
DNode<T>* DoubleCircleList<T>::get_node(int index){
	//判断参数有效性
	if(index<0||index>=count){
		cout<<"get node failed! the index in out of bound!"<<endl;
		return NULL;
	} 
	//正向查找 
	if(index<=count/2){
		int i=0;
		DNode<T>* pindex=phead->next;
		while(i++<index){
			pindex=pindex->next;
		}
		return pindex;
	}
	//反向查找
	 int j=0;
	 int rindex=count-index-1;
	 DNode<T>* prindex=phead->prev;
	 while(j++<rindex){
	 	prindex=prindex->prev;
	 }
	 return prindex;
}
template<class T>
T DoubleCircleList<T>::get(int index){
	return get_node(index)->value;
}
//获取第1个结点值
template<class T>
T DoubleCircleList<T>::get_first(){
	return get_node(0)->value;
} 
//获取最后一个结点值
template<class T>
T DoubleCircleList<T>::get_last(){
	return get_node(count-1)->value;
} 
//将结点插入到index位置之前
template<class T>
int DoubleCircleList<T>::insert(int index,T t){
	if(index==0)
		return insert_first(t);
	DNode<T>* pindex=get_node(index);
	DNode<T>* pnode=new DNode<T>(t,pindex->prev,pindex);
	pindex->prev->next=pnode;
	pindex->prev=pnode;
	count++;
	return 0;

}
//将结点插入到第一个结点处
template<class T>
int DoubleCircleList<T>::insert_first(T t){
	DNode<T>* pnode=new DNode<T>(t,phead,phead->next);
	phead->next->prev=pnode;
	phead->next=pnode;
	count++;
	return 0;
} 
//结点追加到链表末尾
template<class T>
int DoubleCircleList<T>::append_last(T t){
	DNode<T>* pnode=new DNode<T>(t,phead->prev,phead);
	phead->prev->next=pnode;
	phead->prev=pnode;
	count++;
	return 0;
} 
//删除index位置结点
template<class T>
int DoubleCircleList<T>::Delete(int index){
	DNode<T>* pindex=get_node(index);
	pindex->next->prev=pindex->prev;
	pindex->prev->next=pindex->next;
	delete pindex;
	count--;
	return 0;
}
//删除第一个结点
template<class T>
int DoubleCircleList<T>::Delete_first(){
	return Delete(0);
} 
//删除最后一个结点
template<class T>
int DoubleCircleList<T>::Delete_last(){
	return Delete(count-1);
} 

//DoubleCircleList.cpp
#include <iostream>
#include "DoubleCircleList.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
void int_test()
{
	int iarr[4] = {10, 20, 30, 40};//定义一个数组
 
	cout << "\n开始测试 int数据" << endl;
	// 创建双向链表
	DoubleCircleList<int>* pdlink = new DoubleCircleList<int>();
 
	pdlink->insert(0, 20);        // 将 20 插入到第一个位置
	pdlink->append_last(10);    // 将 10 追加到链表末尾
	pdlink->insert_first(30);    // 将 30 插入到第一个位置
 
	// 双向链表是否为空
	cout << "is_empty()=" << pdlink->is_empty() <<endl;
	// 双向链表的大小
	cout << "size()=" << pdlink->size() <<endl;
 
	// 打印双向链表中的全部数据
	int sz = pdlink->size();
	for (int i=0; i<sz; i++)
		cout << "pdlink("<<i<<")=" << pdlink->get(i) <<endl;
}

int main(int argc, char** argv) {
	int_test();
	return 0;
}

双向循环链表：

#include<stdio.h>  
#include<stdlib.h>  
#include<malloc.h>  
typedef struct DOUBLE_LIST  
{  
    int data;  
    struct DOUBLE_LIST *prev;  
    struct DOUBLE_LIST *next;  
}double_list;  
double_list *createlist()       //创建有n个元素的双向链表 并输入元素  
{  
    double_list *head, *p, *q;  
    int n,x;  
    head = (double_list *)malloc(sizeof(double_list));  
    head->prev = head;  
    head->next = head;  
    p = head;  
    printf("输入要创建双向链表的元素的个数：\n");  
    scanf("%d",&n);  
    for(int i=0;i<n;i++)  
    {  
        scanf("%d", &x);  
        q = (double_list *)malloc(sizeof(double_list));  
        q->data = x;  
        p->next = q;  
        head->prev = q;  
        q->prev = p;  
        q->next = head;  
        p = q;  
    }  
    return head;  
}  
//遍历并且输出这些元素  
void printlist(double_list *head)  
{  
    double_list *p;  
    p = head;  
    p = p->next;  
    while(p!=head)  
    {  
        printf("%d  ", p->data);  
        p = p->next;  
    }  
    printf("\n");  
}  
//得到现在双向链表中的元素的个数  
int lengthlist(double_list *head)  
{  
    double_list *p;  
    p = head;  
    p = p->next;  
    int coun = 0;  
    while(p!=head)  
    {  
        coun++;  
        p = p->next;  
    }  
    return coun;  
}  
//在第i个元素之前插入数据data  
void insertlist_f(double_list *head, int i, int data)  
{  
    double_list *p = head, *q;  
    p = p->next;  
    i--;  
    while(i--)  
        p = p->next;  
    q = (double_list *)malloc(sizeof(double_list));  
    q->data = data;  
    (p->prev)->next = q;  
    q->prev = p->prev;  
    q->next = p;  
    p->prev = q;  
}  
//删除第i个位置的元素  
void deletelist_i(double_list *head, int i)  
{  
    double_list *p = head;  
    p = p->next;  
    i--;  
    while(i--)  
        p = p->next;  
    (p->prev)->next = p->next;  
    (p->next)->prev = p->prev;  
    free(p);  
}  
//删除值为x的元素  
void deletelist_x(double_list *head, int x)  
{  
    double_list *p = head, *q;  
    p = p->next;  
    while(p!=head)  
        if(p->data == x)  
        {  
            q = p->next;  
            (p->prev)->next = p->next;  
            (p->next)->prev = p->prev;  
            free(p);  
            p = q;  
        }  
        else  
            p = p->next;  
}  
//对双向链表进行排序  
void sortlist(double_list *head)  //升序  
{  
    double_list *p = head, *q, *t;  
    p = p->next;  
    for(;p!=head;p=p->next)  
        for(t = p->next;t!=head;t=t->next)  
        {  
            if(p->data > t->data)  
            {  
                int a = p->data;  
                p->data = t->data;  
                t->data = a;  
            }  
        }  
}  
int main()  
{  
    double_list *head;  
    head = createlist();  
    deletelist_x(head, 2);  
    //sortlist(head);  
    printlist(head);  
    insertlist_f(head, 2, 2);  
    printlist(head);  
  
    return 0;  
}  


双向链表的遍历来说我只给出了前序遍历的代码，没有写后序遍历的代码，这其实是差不多的，但是因为双向链表可以进行两个方向的遍历，这给我们带来了很大的方便。

一、什么是双链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。




二、双链表的基本操作
创建、遍历、测长、插入、删除
#include <iostream>
#include <stdio.h>
using namespace std;


//结点类
class Node {
public:
	int data;
	Node *pPre, *pNext;
};

//双向链表类
class DoubleLinkList {
public:
	DoubleLinkList() {
		head = new Node;
		head->data = 0;
		head->pNext = NULL;
		head->pPre = NULL;
	}
	~DoubleLinkList() { delete head; }
	void CreateLinkList(int n);				//创建链表
	void InsertNode(int position, int d);	//在指定位置处插入结点
	void TraverseLinkList();				//遍历链表
	bool IsEmpty();							//判断链表是否为空
	int GetLength();						//获得链表长度
	void DeleteNode(int position);			//删除指定位置处结点
	void DeleteLinkList();					//删除链表
private:
	Node *head;
};

void DoubleLinkList::CreateLinkList(int n) {
	if (n < 0) {
		cout << "输入结点个数错误！" << endl;
		exit(EXIT_FAILURE);
	}
	else {
		int i = 0;
		Node *pnew, *ptemp;
		ptemp = head;
		i = n;
		while (n-- > 0) {
			cout << "请输入第" << i - n << "个结点值：";
			pnew = new Node;
			cin >> pnew->data;
			pnew->pNext = NULL;   //也可以放while外，但需要初始化
			pnew->pPre = ptemp;
			ptemp->pNext = pnew;
			ptemp = pnew;
		}
	}
}

void DoubleLinkList::InsertNode(int position, int d) {
	if (position < 0 || position > GetLength() + 1) {
		cout << "输入位置错误！" << endl;
		exit(EXIT_FAILURE);
	}
	else {
		Node *pnew, *ptemp;
		pnew = new Node;
		pnew->data = d;
		ptemp = head;

		while (position-- > 1)
			ptemp = ptemp->pNext;

		if (ptemp->pNext != NULL)
			ptemp->pNext->pPre = pnew;
		pnew->pNext = ptemp->pNext;
		pnew->pPre = ptemp;
		ptemp->pNext = pnew;
		ptemp = pnew;
	}
}

void DoubleLinkList::TraverseLinkList() {
	Node *ptemp = head->pNext;
	while (ptemp != NULL) {
		cout << ptemp->data << " ";
		ptemp = ptemp->pNext;
	}
	cout << endl;
}

bool DoubleLinkList::IsEmpty() {
	if (head->pNext == NULL)
		return true;
	else
		return false;
}

int DoubleLinkList::GetLength() {
	int n = 0;
	Node *ptemp = head->pNext;
	while (ptemp != NULL) {
		n++;
		ptemp = ptemp->pNext;
	}
	return n;
}

void DoubleLinkList::DeleteNode(int position) {
	if (position < 0 || position > GetLength()) {
		cout << "输入数据错误!" << endl;
		exit(EXIT_FAILURE);
	}
	else {
		Node *pdelete, *ptemp;
		ptemp = head;

		while (position-- > 1)
			ptemp = ptemp->pNext;
		pdelete = ptemp->pNext;
		if (pdelete->pNext != NULL)
			pdelete->pNext->pPre = ptemp;
		ptemp->pNext = pdelete->pNext;
		delete pdelete;
		pdelete = NULL;
	}
}

void DoubleLinkList::DeleteLinkList() {
	Node *pdelete, *ptemp;
	pdelete = head->pNext;
	while (pdelete != NULL) {
		ptemp = pdelete->pNext;
		head->pNext = ptemp;
		if (ptemp != NULL)
			ptemp->pPre = head;
		delete pdelete;
		pdelete = ptemp;
	}
}

//测试函数
int main() {
	DoubleLinkList dl;
	int position = 0, value = 0, n = 0;
	bool flag = false;

	cout << "请输入需要创建双向链表的结点个数：";
	cin >> n;
	dl.CreateLinkList(n);

	cout << "打印链表值如下：";
	dl.TraverseLinkList();

	cout << "请输入插入结点的位置和值：";
	cin >> position >> value;
	dl.InsertNode(position, value);

	cout << "打印链表值如下：";
	dl.TraverseLinkList();

	cout << "请输入要删除结点的位置：";
	cin >> position;
	dl.DeleteNode(position);

	cout << "打印链表值如下：";
	dl.TraverseLinkList();

	dl.DeleteLinkList();
	flag = dl.IsEmpty();
	if (flag)
		cout << "删除链表成功！" << endl;
	else
		cout << "删除链表失败！" << endl;

	system("pause");
	return 0;
}

参考：（C++版）链表（三）——实现双向链表的创建、插入、删除等简单操作（链表有从一到四的系列，都写的很好，单向循环和双向循环链表可直接参考）

#include <iostream>
using namespace std;

template <class T> class DblList;

template <class T>
struct DblNode
{
	friend class DblList<T>;
public:
	DblNode(T &dt) :data(dt) {}
	DblNode() {}
//private:
	T data;
	DblNode *lLink;
	DblNode *rLink;
};

template <class T>
class DblList
{
public:
	DblList() 
	{
		first = new DblNode<T>();
		first->lLink = first->rLink = first;
	};
	DblNode<T> * getFirst()
	{
		return first;
	}
	//在p1的右边插入p2
	void Insert(DblNode<T> * p1, DblNode<T> * p2);
	void Delete(DblNode<T> * p);

private:
	DblNode<T> *first;
};

template <class T>
void DblList<T>::Insert(DblNode<T> * p1, DblNode<T> * p2)
{
	p2->lLink = p1;
	p2->rLink = p1->rLink;

	p1->rLink->lLink = p2;
	p1->rLink = p2;
}

template <class T>
void DblList<T>::Delete(DblNode<T> * p)
{
	if (p == first)
		return;

	p->lLink->rLink = p->rLink;
	p->rLink->lLink = p->lLink;

	delete p;
}


int main()
{
	DblList<int> iDl;

	
	int a1 = 10, a2 = 20, a3 = 30, a4 = 40;
	DblNode<int> *node1 = new DblNode<int>(a1);
	DblNode<int> *node2 = new DblNode<int>(a2);
	DblNode<int> *node3 = new DblNode<int>(a3);
	DblNode<int> *node4 = new DblNode<int>(a4);

	iDl.Insert(iDl.getFirst(),node1);
	iDl.Insert(iDl.getFirst(), node2);
	iDl.Insert(iDl.getFirst(), node3);
	iDl.Insert(iDl.getFirst(), node4);
	

	cout<< iDl.getFirst() ->rLink->data<<endl;
	cout << iDl.getFirst()->rLink->rLink->data << endl;
	cout << iDl.getFirst()->rLink->rLink->rLink->data << endl;
	cout << iDl.getFirst()->rLink->rLink->rLink->rLink->data << endl;

	cout << endl << endl;

	iDl.Delete(node1);
	iDl.Delete(node4);

	cout << iDl.getFirst()->rLink->data << endl;
	cout << iDl.getFirst()->rLink->rLink->data << endl;
	//cout << iDl.getFirst()->rLink->rLink->rLink->data << endl;
	
	return 0;
}

运行结果：



 

使用 VS2017 + Windows 7

偶尔当一条咸鱼，今天试一下用C++实现双向链表

--------------------------------------------------------include.h       ----------------------------------------------------

-------- 有一些大佬说尽量避免头文件写到一个文件夹中，但是目前还没有找到好的书写方式
#pragma once
#ifndef __INCLUDE__
#define __INCLUDE__

#include <iostream>
#include <string>
#include <vector>

using namespace std;

#endif 


---------------------------------------------------------DoubleLink.h---------------------------------------------------

-----DoubleLink.h
#pragma once
#include "include.h"
#include "test.h"
using namespace std;
typedef struct Link  -- 节点
{
	int item;
	Link* next;
	Link* prev;
};

class DoubleLink
{
private:
	int length;  -- 链表长度
	Link* header;-- 第一个节点
	Link* tail;  -- 最后一个节点
public:
	DoubleLink();
	Link* CreateItem();                  --创建内存
	bool Push(int item);                 -- 压入到链表最后一个位置
	int Pop();                           -- 从取出最后一个
	bool InsertItem(int index, int item);-- 插入到指定位置
	int DeleteAt(int index);             -- 删除指定位置
	void SelectAll();                    -- 打印所有节点
};


-------------------------------------------------------------DoubleLink.cpp------------------------------------------------------------

#include "DoubleLink.h"

DoubleLink::DoubleLink()
{
    header = CreateItem();
    tail = header;
    length = 0;
}

bool DoubleLink::Push(int item) -- 压入到最后一个节点
{
    Link* link = CreateItem();  -- 首先 创建一块相应的内存
    if (!link)                  -- 如果创建失败
    	return false;
    link->item = item;
    link->prev = tail;
    tail->next = link;
    tail = link;
    tail->next = header;
    header->prev = tail;
    length++;
    return true;
}

int DoubleLink::Pop()
{
    Link* link = header->next;
    int item = 0;
    for (int i = 0; i < length - 1; i++)
    {
    	link = link->next;
    }
    item = link->item;
    tail = link->prev;
    tail->next = link->next;
    length--;
    free(link);                  -- 释放内存地址
    link = NULL;                 -- 让他指向0x000000地址
    return item;
}

Link* DoubleLink::CreateItem()
{
    Link* item = (Link*)malloc(sizeof(Link)); -- 注意 我们是使用malloc创建的内存 所以应该是用free释放 而不是delete
    return item;
}

bool DoubleLink::InsertItem(int index, int item)
{
    if (index > length)
    {
    	cout << "索引超出" << endl;
    	return false;
    }
    Link* link = CreateItem();
    link->item = item;
    Link* temp = header;
    for (int i = 0; i < index; i++)
    {
    	temp = temp->next;
    }
    link->prev = temp->prev;    -- 和冒泡的替换差不多
    link->next = temp;
    temp->prev->next = link;
    temp->prev = link;
    length++;
    return true;
}

int DoubleLink::DeleteAt(int index)
{
    if (index > length || index < 1)
    {
    	cout << "索引超出" << endl;
    	return false;
    }
    Link* link;
    int data = 0;
    if (index > length / 2)            -- 为了节省 所以我们分为向前遍历和向后遍历
    {
    	link = header;
    	for (int i = 0; i < index; i++)
    	{
    		link = link->next;
    	}
    	link->prev->next = link->next;
    	link->next->prev = link->prev;
    	data = link->item;
    	free(link);
    	link = NULL;
    	cout << "" << endl;
    }
    else
    {
    	link = header->prev;
    	for (size_t i = 0; i < length - index; i++)
    	{
    	    link = link->prev;
	    	cout << "Link->Prev:" << link->item << endl;
	    }
	    link->prev->next = link->next;
	    link->next->prev = link->prev;
	    data = link->item;
	    free(link);
	    link = NULL;
    }
    length--;
    return data;
}

void DoubleLink::SelectAll()
{
    Link* link = header->next;
    for (int i = 0; i < length; i++)
    {
    	cout << link->item << endl;
    	link = link->next;
    }
}

------------------------------------------------------------------main.cpp------------------------------------------------------------------------

#include "DoubleLink.h"
int main()
{
    // 在这里 分清指针和地址的关系 地址是使用link.methodName(params object o) 访问
    // 指针是用过 link->methodName(params object o) 访问
    DoubleLink link; 
    for (int i = 0; i < 7; i++)
    {
    	link.Push(i);
    }
    link.InsertItem(1, 1002);
    link.SelectAll();
    cout << "Pop:" << link.Pop() << endl;  -- 因为我们DoubleLink.h 里面有Inclde.h的声明 所以可以直接使用 cout<<endl;
    link.SelectAll();
    cout << "DeleteAt:" << link.DeleteAt(7) << endl;
    link.SelectAll();
    
    system("pause");
    return 0;
}