# Python 实现双向链表（图解）

## 双向链表基本方法实现（Python）

### 1. 初始化链表

```"""节点类"""
class Node(object):
def __init__(self, data=None):
self.data = data
self.pre = None
self.next = None

"""初始化双向链表"""

def __init__(self):
"""
设置头尾，操作比较容易
头－－（next）－－》尾
尾－－（pre）－－》头
:return:
"""
head = Node()
tail = Node()
self.head = head
self.tail = tail
self.head.next = self.tail
self.tail.pre = self.head```

### 2. 获取链表长度

```"""获取链表长度"""

def __len__(self):
length = 0
node = self.head
while node.next != self.tail:
length += 1
node = node.next
return length```

### 3. 追加节点

```"""追加节点"""

def append(self, data):
"""
:param data:
:return:
"""
node = Node(data)
pre = self.tail.pre
pre.next = node
node.pre = pre
self.tail.pre = node
node.next = self.tail
return node```

### 4. 获取节点

``` """获取节点"""
def get(self, index):
"""
获取第index个值，若index>0正向获取else 反向获取
:param index:
:return:
"""
length = len(self)
index = index if index >= 0 else length + index
if index >= length or index < 0: return None
node = self.head.next
while index:
node = node.next
index -= 1
return node```

### 5. 设置节点

```"""设置节点"""

def set(self, index, data):
node = self.get(index)
if node:
node.data = data
return node```

### 6. 插入节点

```"""插入节点"""

def insert(self, index, data):
"""
因为加了头尾节点所以获取节点node就一定存在node.next 和 node.pre
:param index:
:param data:
:return:
"""
length = len(self)
if abs(index + 1) > length:
return False
index = index if index >= 0 else index + 1 + length

next_node = self.get(index)
if next_node:
node = Node(data)
pre_node = next_node.pre
pre_node.next = node
node.pre = pre_node
node.next = next_node
next_node.pre = node
return node```

### 7. 删除节点

```"""删除节点"""

def delete(self, index):
node = self.get(index)
if node:
node.pre.next = node.next
node.next.pre = node.pre
return True

return False```

### 8. 反转链表

```"""反转链表"""
def __reversed__(self):
"""
1.node.next --> node.pre
node.pre --> node.next
2.head.next --> None
tail.pre --> None
3.head-->tail
tail-->head
:return:
"""
pre_head = self.head
tail = self.tail

def reverse(pre_node, node):
if node:
next_node = node.next
node.next = pre_node
pre_node.pre = node
if pre_node is self.head:
pre_node.next = None
if node is self.tail:
node.pre = None
return reverse(node, next_node)
else:
self.head = tail
self.tail = pre_head

return reverse(self.head, self.head.next)```

### 9. 清空链表

```"""清空链表"""
def clear(self):
self.head.next = self.tail
self.tail.pre = self.head```

0 条评论

• ### Python Ast介绍及应用

Abstract Syntax Trees即抽象语法树。Ast是python源码到字节码的一种中间产物，借助ast模块可以从语法树的角度分析源码结构。此外，我们...

• ### Linux下切换Python版本

这两天遇到一个问题需要在 python3 的环境下进行测试，由于Linux默认已经安装了Python2.7，并且作者一直也在使用 ，所以需要重新安装并临时切换到...

• ### centos 7 安装python3.6

centos7 默认安装了python2.7.5,当需要使用python3的时候，可以手动下载python源码后编译安装.

• ### 手把手用Python教你如何发现隐藏wifi

细心的小伙伴可能知道，小编之前发布过一篇使用Python发现酒店隐藏的针孔摄像头，没有来得及上车的小伙伴也没关系，可以戳这篇文章了解一下：使用Pyhton带你...

• ### angularJS学习之路（七）---子控制器关于是引用机制还是复制机制的问题---原型继承

原型继承 要弄清一点：    修改父级对象中的alue值会同时修改 子对象中的alue值，但是反过来就不行了，

• ### 剑指offer - 二叉搜索树与双向链表 - JavaScript

题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

• ### 【文章推荐】霸王餐，如何吃出霸气有力的互联网商业模式

Super注：这是阿超一位朋友的一篇文章，对“罗辑思维”感兴趣的朋友可以看看。这位朋友希望与更多人交流，大家对其话题感兴趣，可以加他微信，见文末。 ...

• ### 【编程基础】Win32窗口下调试输出

在Win32的console下，我们可以用基本的printf，来输出调试信息，这个很方便。不过要是在非console的窗口模式应用程序里面，就不能使用print...

• ### 为什么说它对 Android 未来的发展十分重要？

由于其开放性，Android 在其前十年取得了显著的增长。有大量的设备可供选择，蓬勃发展的开发者生态系统提供了许多应用和游戏，为这些设备赋予了长久的生命力。作为...