用Python玩转数据结构
链表
节点类
根据在前学过的数据结构，那么必须有节点，Python里面没有指针的说法，所以我们用引用来实现
节点类的方法
节点类最基本的功能包括：更新数据，查询数据，更新后继节点和查询后继节点。
class Node(object):
def __init__(self, data):
self.data = data
self.next_node = None
def get_data(self):
"""
获取当前节点的数据
:return: 返回当前节点的数据
"""
return self.data
def set_data(self, data):
"""
设置节点的数据为传入的数据
:param data:
:return: 无返回
"""
self.data = data
def get_next(self):
"""
获取当前节带点的指向
:return: 返回指向的对象
"""
return self.next
def set_next(self, next_node):
"""
修改节点的指向
:param next_node:
:return:无返回
"""
self.next_node = next_node
链表类
我们把节点类先实现，然后再来实现链表类。我们定义一个链表类，并实现初始化方法。在初始化方法中定义了两个属性，分别是head 和length属性。head属性表明头节点，在初始化的时候指向None。length属性表明链表的长度，方便判断列表是否为空和返回链表的长度。
class Linked_list(object):
def __init__(self):
"""
初始化方法，定义一个长度属性方便统计和判断
"""
self.head = None
self.length = 0
链表类的方法
然后我们一个想想我们的链表类需要哪些方法，这是有链表的特性觉得的不是吗？大概列一个列表吧：
- 在末尾插入数据
- 在开头插入数据
- 在指定位置插入 数据
- 修改指定位置的数据
- 获取指定位置的数据
- 查找数据在链表中的数据
- 删除指定位置的数据
- 展示整个链表
- 删除整个链表
- 判断这个链表是否为空
大概就是这些看起来是不是有点多，但是不用担心，我们一点一点的来实现。
判断链表是否为空
首先是判断一个链表是否为空，这个很好实现，我们先看代码：
def isEmpty(self):
"""
判断链表是否为空，如果为空返回True，否则为False
:return:
"""
return self.length == 0
除去注释也就一行代码的事情，用链表的长度和0做一个比较，不相等返回False相等返回True然后就能很好的判断了。
获取链表的长度
同样的获取链表的长度也很简单：
def get_length(self):
return self.length
在链表末尾插入数据
然后就是在末尾插入数据：
def append(self, data_or_node):
"""
在链表的末尾增加一个节点
:param data_or_node:
:return:
"""
item = None
# 这一个判断是为了判断传进来的数据是什么类型的
if isinstance(data_or_node, Node):
item = data_or_node
else:
item = Node(data_or_node)
if not self.head:
self.head = item
self.length += 1
else:
node = self.head
while node.next_node:
node = node.next_node
node.next_node = item
self.length += 1
首先是判断传入进来的数据是什么类型，如果已经是一个节点类的话我们就不用转换，如果不是，我们就将其转换为节点类。这里用到了isinstance()方法，这个方法的作用是判一个对象是否是一个已知的类型，考虑继承的情况。然后判断这个链表的头结点是否存在，也可以通过判断链表的长度来实现。如果头节点不存在，就将这个节点变为头节点。所以有了这个引用，将item的值赋值给head。如果不是的话我们首先就要找到尾节点，通过头节点开始循环，一直找到尾节点，然后引用。不管是那种情况都不能忘记将链表的长度加上1
在链表的头部插入数据
在头部插入数据也很简单，
def add(self, data_or_node):
"""
在链表的最前方插入一个数据
:param data_or_node:
:return:
"""
if isinstance(data_or_node, Node):
item = data_or_node
else:
item = Node(data_or_node)
if not self.head:
self.head = item
self.length += 1
else:
next_node = self.head
self.head = item
item.next_node = next_node
self.length += 1
大部分都差不多，只是在判断不是空链表之后的处理有点不一样。我们将之前头节点的值赋值给一个变量，然后将我们传入的变量指向给原头节点，同时将头节点指向我们传入的变量。
在指定位置插入节点
我们可以通过指定位置插入节点这个是很必要的一个方法，先看代码：
def insert(self, index, data_or_node):
"""
根据给定的索引在链表中插入一个节点
:param index: 索引
:param data_or_node: 数据
:return: 无返回
"""
if self.isEmpty():
print("this Linked list is Empty")
return
if index < 0 or index >= self.length:
print("error: out of index ")
return
item = None
if isinstance(data_or_node, Node):
item = data_or_node
else:
item = Node(data_or_node)
if index == 0:
self.add(item)
return
j = 0
node = self.head
prev = self.head
while j < index:
prev = node
node = node.next_node
j += 1
prev.next_node = item
item.next_node = node
self.length += 1
对于所有给出索引的方法来说，我们都需要判断这个链表是否为空和给定的索引是否越界。然后再把传入的节点通过判断转换为节点类。如果索引的值是0的话就是在头部插入，我们直接调用在前面定义的内部方法就好，然后记得return结束函数，不然那你会将你的所有的节点的值都改变。然后就是关键的步骤，我们定义三个变量，作用分别是：计数器、记录前置节点和记录当前节点。最开始的节点都为头节点，然后开始循环，当j小于索引值的时候呢，循环，同时将node的值赋值给prev，将节点记录下来。当找到插入节点的位置的时候，我们将prev指向我们传入的节点，然后将传入的节点再指向给item就完成在指定位置插入。只要是涉及到节点个数的变化的操作的时候一定要记得对length进行对应的操作。
删除指定位置的节点
说完了增加，按照惯例就是删除了。首先是删除指定位置的节点：
def delete(self, index):
"""
根据给定的索引删除一个节点
:param index: 索引
:return: 无返回
"""
if self.isEmpty():
print("this Linked list is Empty")
return
if index < 0 or index >= self.length:
print("error: out of index ")
return
if index == 0:
self.head = self.head.next_node
self.length -= 1
j = 0
node = self.head
prev = self.head
while j < index:
prev = node
node = node.next_node
j += 1
prev.next_node = node.next_node
self.length -= 1
首先还是几个判断，然后如果是删除头节点，我们将头节点的值指向头节点的下一个。如果不是，就和插入很像了，找到索引对应的位置，然后将prev直接指向node的下一个，然后链表长度减1。
删除整个链表
删除了一个节点就像删除整个链表，这个代码也超级简单：
def clear(self):
"""
清除链表
:return: 无返回
"""
self.head = None
self.length = 0
我们只需要将链表的头节点再指向为空，然后长度变为0就好。
修改指定位置的节点的值
删除也很简单，下面来说修改，修改指定位置节点的值：
def updata_node_item(self, index, data):
"""
根据给出的索引更新一个节点的值
:param index: 索引
:param data: 更新的值
:return: 无返回
"""
if self.isEmpty():
print("this Linked list is Empty")
return
if index < 0 or index >= self.length:
print("error: out of index ")
return
j = 0
node = self.head
while j < index:
node = node.next_node
j += 1
node.data = data
就只是常规的判断然后是循环找到节点后修改值就好。
根据索引获得对应节点的值
查找是一个很重要的功能，有两种需要我们实现，先来第一种：根据索引查找对应的值：
def get_node_item(self, index):
"""
根据索引获取获取节点的值
:param index: 索引
:return: 返回索引对应节点的值
"""
if self.isEmpty():
print("this Linked list is Empty")
return
if index < 0 or index >= self.length:
print("error: out of index ")
return
j = 0
node = self.head
while j < index:
node = node.next_node
j += 1
return node.data
和修改很类似，不同的是我们直接返回值就好
根据值查对应的节点的索引
我们也可以传一个值然后找对应的索引，这样就能做到：
def get_node_index(self, data):
"""
查找一个数据的索引
:param data:数据
:return:索引
"""
node = self.head
j = 0
while node.next_node:
if node.data == data:
return j
else:
node = node.next_node
j += 1
if j == self.length:
print("%s is not found " % str(data))
其实都差不多，但是呢有一种情况需要注意，就是如果当j的值都等于链表的长度的时候说明，链表当中没有这个值。
展示链表
其实到这里就差不多了，然后就是一个展示整个链表的方法：
def show(self):
"""
展示链表
:return:
"""
if self.isEmpty():
print("this is a empty linked list")
n = 0
node = self.head
while n < self.length:
print("node %d : %s" % (n, node.data))
node = node.next_node
n += 1
试试效果
mylinked = Linked_list()
for i in range(10):
mylinked.append(i)
mylinked.show()
print(mylinked.get_length())
print(mylinked.get_node_index(4))
print(mylinked.get_node_item(5))
print(mylinked.updata_node_item(4, 20))
print(mylinked.delete(8))
print(mylinked.insert(0, 420))
mylinked.show()
结果：
node 0 : 0
node 1 : 1
node 2 : 2
node 3 : 3
node 4 : 4
node 5 : 5
node 6 : 6
node 7 : 7
node 8 : 8
node 9 : 9
10
4
5
None
None
None
node 0 : 420
node 1 : 0
node 2 : 1
node 3 : 2
node 4 : 3
node 5 : 20
node 6 : 5
node 7 : 6
node 8 : 7
node 9 : 9
Process finished with exit code 0
完整代码传送门：点这里
