Python实现链表介绍
学习数据结构的的链表和树时，会遇到节点（node）这个词，节点是处理数据结构的链表和树的基础。节点是一种数据元素，包括两个部分：一个是实际需要用到的数据；另一个存储下一个节点位置。
链表是一系列节点串联形成的数据结构，链表存储有序的元素集合，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的部分和一个指向下一个元素的链接部分组成。因此链表增删非首尾元素时不需要移动元素，只需要更改链接部分的值即可。
这里以最简单的单链表为例介绍。
单链表每个节点的结构如下：
所谓单链表就是只有一个指向其他节点的变量，也就是在这种类型的数据结构中，任何两个数据元素之间只有一个链接。参见下图：
链表是一系列节点串联形成的，因此链表中的元素在内存中并不是连续的。
C语言是通过指针将节点连接成链表和树结构的，Python没有指针怎么办呢？
众所周知，C语言实现的链表是由一个一个的结点构成，每个结点分为数据域和指针域，指针域中存储了其后继结点的地址，通过地址来访问下一个结点，然后一步一步的串联起来形成了一个链表。对于单链表，任何两个数据元素之间只有一个链接指向。
Python怎么表示链表呢？
现在以单链表的建立和遍历为例介绍，在Python中可以通过实现一个类来创建节点。在下面的示例中，我们创建一个名为Node的类，这个类由两部分——两个成员——组成：dataval用于保存数据，nextval用于保存后续元素 。
#单链表的建立和遍历
#定义Node的类
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
#创建节点
# 1、为节点添加数据
e1 = Node("D1")
e2 = Node("D2")
e3 = Node("D3")
e4 = Node("D4")
# 2、建立连接：通过节点对象传递适当的值来指向下一个数据元素
e1.nextval = e2
e2.nextval = e3
e3.nextval = e4
#遍历节点元素
thisvalue = e1 #从第一个节点开始
while thisvalue:
print(thisvalue.dataval)
thisvalue = thisvalue.nextval
运行输出：
D1
D2
D3
D4
链表的操作包括了创建、删除、插入、输出等。
创建就是空间的分配，将头、尾指针及链表结点个数等初始化。删除和插入根据被操作元素的位置可以细分为头删除（插入），尾删除（插入），中间删除（插入）。这是是单链表最基本的操作，除此之外还有其它操作。
插入操作
头插入实际上是增加一个新节点，然后把新增加的结点指针指向原来头指针指向的元素，再把头指针指向新增的节点。
尾插入也是增加一个新节点，该节点指针置为null，然后把原尾结点指针指向新增加的节点，最后把尾指针指向新增加的节点即可。
中间插入稍复杂，首先增加一个节点，然后新增节点的指针指向插入位置的后一个节点，把插入位置的前一个节点指针指向新插入节点即可。
删除操作
删除头元素时，先将头指针指向下一个节点，然后把原头结点的指针置空即可。
删除尾元素时，首先找到链表倒数第2个元素，然后把尾指针指向这个元素，接着把原倒数第2个元素的指针置空。
删除中间元素相对复杂一些，首先将要删除的节点的前一个节点指针指向要删除的节点的下一个节点，然后把要删除节点的指针置空。
上面提到是单链表最基本的操作，除此之外还有其它操作不多说了。下面给出代码示例。
下面给出一个单链表综合例子（来源 https://www.jianshu.com/p/9f2aca048c84）
#定义单向链表的节点类
class SingleListNode(object):
"""单节点类"""
def __init__(self, _item, _next=None):
self.item = _item #节点的值域
self.next = _next
#定义单向链表类的初始定义
class SingleLinkedList(object):
"""单链表类"""
def __init__(self):
self.head = None
def is_empty(self):
return self.head is None
def add(self, newdata):
node = SingleListNode(newdata, _next=self.head)
self.head = node
def append(self, newdata):
node = SingleListNode(newdata)
if self.is_empty():
self.head = node
else:
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = node
def insert(self, pos, newdata):
"""将newdata插入pos位置之后"""
if pos <= 0:
self.add(newdata)
elif pos > self.length() - 1:
self.append(newdata)
else:
node = SingleListNode(newdata)
cur = self.head
count = 0
while count < pos - 1:
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, olddata):
"""从单链表中删除所有的olddata"""
cur = self.head
pre = None
while cur is not None:
if cur.item == olddata:
if not pre:
self.head = cur.next
else:
pre.next = cur.next
cur = cur.next
else:
pre = cur
cur = cur.next
def length(self):
"""返回单链表的长度"""
cur = self.head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count
def travel(self):
"""打印整个单链表
return
------
ls: list，从前至后的单链表"""
cur = self.head
ls = []
while cur is not None:
ls.append(cur.item)
cur = cur.next
return ls
def search(self, data):
cur = self.head
while cur is not None:
if cur.item == data:
return True
else:
cur = cur.next
return False
#测试代码
SL = SingleLinkedList()
print('单链表是否为空：', SL.is_empty())
SL.add(1)
SL.add(2)
SL.append(5)
print('单链表为：', SL.travel())
SL.insert(2, 3)
print('单链表中是否有4：', SL.search(4))
print('单链表为：', SL.travel())
print('单链表长度：', SL.length())
SL.remove(2)
print('单链表为：', SL.travel())
运行输出：
单链表是否为空： True
单链表为： [2, 1, 5]
单链表中是否有4： False
单链表为： [2, 1, 3, 5]
单链表长度： 4
单链表为： [1, 3, 5]
附录、列表（list）是如何在CPython中实现的？
Python 中的 list 并不是传统（计算机科学）意义上的列表,从本质上讲，它是可变长度的数组。传统的列表，也叫做链表（Linked List），通常是由一系列的节点来实现的。关于这点详情可见：
列表是如何在CPython中实现的？https://docs.python.org/zh-cn/3/faq/design.html#why-are-there-separate-tuple-and-list-data-types
还可参见python 列表和链表的区别_Yake1965的博客-CSDN博客_列表和链表
文章出处登录后可见！
