python实现双向链表 -- 详细思路分析

双链表的每个节点都有两个指针，一个指向直接后继，一个指向直接前驱。在双向链表的任意一个节点都能很方便的访问其前后节点。其基本结构如下：

双向链表和单向链表只有在insert、append、remove、add方法上有差别，因此这里可以 使用面向对象的思想 ，继承于单向链表，然后重写这四种方法。

双向链表的节点比单向链表多一个prev指针指向前一个节点

作用： 在链表头部添加元素

作用： 在指定位置插入元素

作用： 在链表尾部添加元素

作用： 删除指定位置元素

#include <iostream>

using namespace std

struct Node

{

int data //节点中的数据 结构体Node的成员变量

Node* next//指向下一节点的指针，习惯用next命名 结构体Node的成员变量

Node( const int&d=int() ) //结构体也可以有构造函数 ,d=T()来指定默认值

:data(d),next(NULL) //用构造函数来初始化成员变量data和指针

{} //所有数据类型，默认初始化都为0，这里data默认初始化为0

}

class Chain //封装链表

{

private: //数据成员通常都是private的

Node* head//首先，我们要一个Node型的指针来保存链表的第一个节点；

int length//再用一个整型变量来记录当前链表内的节点数

public:

Chain()//在构造函数里建立一个空链表，即head指向NULL

:head(NULL),length(0){}//节点数为0

//当我们在类中定义函数时（不是声明），相当于在前面加上一个inline修饰

void delall() //这个函数用来删除链表中的所有节点

{

Node* pdel //定义一个Node型指针用来保存要删除的节点

while( head != NULL ) //当head的指向不为NULL时，就是链表中还存在节点

{

pdel = head //这里备份head的当前指向节点

head = head->next//把head的指向改变为下一节点

delete pdel //把head的原指向给删除掉

} //如此一直下去，尾节点的next肯定是指向NULL的，那删除最后一个的时候

//head就被赋值为NULL，不满足循环条件，退出循环

length = 0 //把节点数归零

}

~Chain(){ delall()} //在析构函数中调用delall函数，来完成对象销毁时清理工作

//这样一个链表必须具备的功能就实现了。下面我们来实现他的增、删、查、改功能

Node*&getpoint( int position ) //对链表的 *** 作，其实全部通过指针来实现的，

{//那就需要定义一个函数来返回当前节点的指针（引用）

if( position<0 || position>length ) //对节点编号进行合法检查

position = length //如果是非法节点编号，那么就把他修改为最后一个节点编号

if( position==0 )//如果编号为0，那就是第一个节点了，

return head//直接返回head就是指向第一个节点的，注意返回的是head本身

Node* head_bak = head //如果编号合法并且不是第一个节点，就开始遍历链表

for( int i=1i <positioni++ )//为什么不直接用head

{//注意这里修改的是成员变量。你把head改了，以后到哪找链表

//我们都是通过head一个一个的往下找节点的。head被修改了。后果显而易见

head_bak = head_bak->next //通过备份的指针来遍历到指定编号前一个节点

}//i不从0开始，减少运算，提高效率

return head_bak->next //这里如果返回head_bak的话。那就是需要的前一个节点了

}

void insert( const int&data, int position ) //如果不修改参数的话，使用引用做参数的时候，最好加上const

{

Node* pin = new Node(data) //需要调用Node的构造函数

pin->next = getpoint(position) //把指定位置的指针返回给新节点的指针

//也就是说，把新的节点的next指向原来这个位置的节点。

getpoint(position) = pin //getpoint()返回的是引用，我们可以直接修改它

//前面的一个节点的next指向我们新的节点。

length++ //链表的节点数+1

}

int del( const int&data )

{

int position = find(data)

if( position !=-1 ) //-1代表没找到

{

Node* &pnext = getpoint(position) //用getponit()来获得指定节点的指向信息

Node* pbak = pnext //用来备份节点的指向信息

pnext = pnext->next//把next指向改为下下个节点。

delete pbak

length--

}

return position

}

//把<<重载，直接输出链表

friend ostream&operator<<( ostream&os, const Chain&oc )

{

Node* phead = oc.head

os <<"[ "

while( phead !=NULL )//判断是否到尾节点

{

os <<phead->data <<' '

phead = phead->next

}

os <<"] " //这个函数，应该没什么好说的了

return os //如果还是不理解，当成固定模式去背吧

}

}

void show()

{

cout <<"******************************" <<endl

cout <<"2- 向链表内添加节点（数据，节点号）" <<endl

cout <<"3- 删除链表内某一个数据（数据）" <<endl

cout <<"0- 退出" <<endl

cout <<"******************************" <<endl

}

int main()

{

Chain link

int position, data, choice, data_new

while( choice != 0 )

{

show()

cout <<"请选择："

cin >>choice

switch ( choice )

{

case 2 :

cout <<"请输入要插入的数据和插入位置："

cin >>data >>position

link.insert( data,position )

cout <<link <<endl

break

case 3 :

cout <<"请输入要删除的数据："

cin >>data

link.del( data )

cout <<link <<endl

break

default :

break

}

}

}

链表： 其中的各对象按线性顺序排列，其顺序有各个对象里的指针决定，为动态集合提供了一种简单而灵活的表示方法。

双向链表： 每一个元素都是一个对象，每个对象有一个关键字key和两个指针：next和prev。如果元素x没有前驱，所以是链表的第一个元素head,若元素x没有后继，因此是链表的最后一个元素tail。如果L.hand=NIL,则链表为空。

---