# Python 实现双向链表

#!usr/bin/env python
#-*- coding:utf-8 -*-

"""
@author:yzk13
@time: 2018/04/18

https://blog.csdn.net/qq490691606/article/details/49948263
"""

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

"""
双向链表类
"""
def __init__(self):
"""
初始化链表
"""
tail = Node(None)
self.tail = tail

@property
def length(self):
"""
获取链表长度
:return:
"""
length = 0
while node.next != self.tail:
length += 1
node = node.next
return length

def print(self):
"""
打印
:return:
"""
if self.length == 0:
print('Nothing')
else:
print('[', end='')
while node.next != self.tail:
print(node.value, ', ', end='')
node = node.next
print('%s]' % node.value)

def append(self, value):
"""
表尾添加节点
:return:
"""
node = Node(value)
pre = self.tail.pre
# 两点之间进行双双链接
pre.next = node
node.pre = pre
node.next = self.tail
self.tail.pre = node
return node

def get(self, index):
"""
获取节点
:param index:
:return:
"""
if index < 0 or index > self.length:
print('Index错误，索引越界')
return None
else:
while index:
node = node.next
index -= 1
return node

def insert(self, index, value):
"""
插入
:param index:
:param value:
:return:
"""
if index < 0 or index > self.length:
print('Index 错误, 索引越界')
next_node = self.get(index)
# 开始插入
node = Node(value)
pre_node = next_node.pre

pre_node.next = node
node.pre = pre_node
node.next = next_node
next_node.pre = node
return node

def delete(self, index):
"""
删除节点
:param index:
:return:
"""
node = self.get(index)
if node:
node.pre.next = node.next
node.next.pre = node.pre
return True
else:
return False

def reverse(self):
"""
反转链表
:return:
1.node.next --> node.pre
node.pre --> node.next
tail.pre --> None
"""
tail = self.tail

# 调用递归，对每个节点进行交换位置
def reverse(pre_node, node):
if node:
next_node = node.next
node.next = pre_node
pre_node.pre = node

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

else:

def clear(self):
"""
清空链表
:return:
"""

if __name__ == '__main__':

# 测试在表尾添加节点
l.append(3)
l.append(4)
l.append(5)
l.print()

# 测试get
i = 0
print('第', i, '个元素为: ', l.get(i).value)

# 测试索引插入
print('索引插入...')
l.insert(1, 7)
l.insert(0, 8)
l.print()

# 测试删除节点
print('删除节点...')
l.delete(0)
l.delete(3)
l.print()

# 测试反转
print('反转...')
l.reverse()
l.print()

# 测试清空
print('清空...')
l.clear()
l.print()

# 测试长度
print('链表长度为: ', l.length)

162 篇文章60 人订阅

0 条评论

## 相关文章

1050

3574

2085

3136

821

853

3456

### Python变量类型全书

? 糖豆贴心提醒，本文阅读时间6分钟 一、Python 变量类型简介 1、Python中变量的特点： 我们知道，在Python中，变量有如下的特点： （1）...

2497

4126

3285