链表定义
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
单向链表，又叫单链表、单向表，是由一个个节点组成的，每个节点是一种信息集合，包含元素本身以及下一个节点的地址。节点在内存中是非连续分布的，在程序运行期间，根据需要可以动态的创建节点，这就使得链表的长度没有逻辑上的限制，有限制的是堆的大小。
在单向链表中，每个节点中存储着下一个节点的地址。基于单向链表，在每个节点内增加一个前驱节点的地址，这就是所谓的双向链表，又叫双链表、双向表。
如单向链表的尾节点指针指向头节点，即为循环单向链表。
如单向链表的头、尾节点指针互相指，即为循环双向链表。
指针是C/C++等语言中的概念，也就是内存地址；python中没有指针，也很少直接操作地址。
在 python 这一类没有指针的语言里，很难真正体现出链表的精髓，只能模拟出一个静态链表来意思意思。
单向表类的实现
模仿python中二叉树的节点Node类，把左右子树的left,right换成一个Next，就有点像了。因为刚学python不久功力有限，愣是用字符串和列表，伪实现了一个单向表的类：
class Node(): def __init__(self,val=None,Next=None): self.val = val self.Next = Next def __repr__(self): return 'listNode('+str(self.val)+')' def __getitem__(self, slices): list = self.values() return list[slices] def is_empty(self): return self.val is None def value(self): return self.val def values(self): head = self t = 'head' r = [] while eval(t) is not None: r.append(eval(t).val) t+='.Next' return r def size(self): if self.is_empty(): return 0 r = self.values() return len(r) def append(self, node): if self.val is None: self.val = node return head = self t = 'head' while eval(t) is not None: t+='.Next' exec(f'{t}=Node({node})') def pop(self): head = self if head.size() < 2: res = head.val head.val = None return res t = 'head' while eval(t).Next is not None: t+='.Next' res = eval(t).val exec(f'{t}=None') return res def pprint(self): r = self.values() r = [i.join(["'"]*2) if type(i) is str else str(i) for i in r] print('->'.join(r))
之所以说是“伪实现”，因为根本就是用字符串和列表模拟出来的效果。尽管这个类如此不入门，有点傻傻的，用上海咸话的讲法，称之为“捣浆糊”。但还是能完成不少功能的。呈上测试代码，如下：
1. 逐个赋值
>>> LinkedList = Node() >>> LinkedList.is_empty() True >>> LinkedList.size() 0 >>> LinkedList = Node(1) >>> LinkedList.is_empty() False >>> LinkedList.size() 1 >>> LL = LinkedList >>> LL.Next = Node(2) >>> LL listNode(1) >>> LL.Next listNode(2) >>> LL.val 1 >>> LL.Next.val 2 >>> LL.value() 1 >>> LL.Next.value() 2 >>> LL.values() [1, 2] >>> >>> >>> LinkedList = Node() >>> LinkedList = Node(1,Node(2)) >>> linked = Node(1,Node(2)) >>> linked.Next.Next = Node('3',Node(4)) >>> linked.pprint() 1->2->'3'->4 >>> linked.values() [1, 2, '3', 4] >>>
注：此链表类允许数字、字符串混装
2.追加append()和弹出pop()
>>> single = Node(1,Node(2,Node(3,Node(4,Node(5))))) >>> single.pprint() 1->2->3->4->5 >>> single.append(6) >>> single.pprint() 1->2->3->4->5->6 >>> single.pop() 6 >>> single.pop() 5 >>> single.pprint() 1->2->3->4 >>>
3. 嵌套赋值或用循环赋值
>>> single = Node(1,Node(2,Node(3,Node(4,Node(5))))) >>> single.size() 5 >>> single.values() [1, 2, 3, 4, 5] >>> >>> >>> link = Node() >>> for i in range(1,9): link.append(i) >>> link.pprint() 1->2->3->4->5->6->7->8 >>>
4. 索引和切片
>>> lList = Node() >>> t = [lList.append(i) for i in range(1,9)] >>> lList.pprint() 1->2->3->4->5->6->7->8 >>> lList[:] [1, 2, 3, 4, 5, 6, 7, 8] >>> lList[::-1] [8, 7, 6, 5, 4, 3, 2, 1] >>> lList[0] 1 >>> lList[1] 2 >>> lList[7] 8 >>> lList[-1] 8 >>> lList[-2] 7 >>> lList[-8] 1 >>> lList[:5] [1, 2, 3, 4, 5] >>> lList[5:] [6, 7, 8] >>> lList[::2] [1, 3, 5, 7] >>> lList[1::2] [2, 4, 6, 8] >>>
注：链表一般是不带索引功能的，这里用类的内置方法__getitem__(self, slices)来强加一个索引和切片的功能，完全是继承了列表的功能。
5. 删除和插入
>>> single = Node(1,Node(2,Node(3,Node(4,Node(5))))) >>> single.pprint() 1->2->3->4->5 >>> single.Next.Next = single.Next.Next.Next >>> single.pprint() 1->2->4->5 >>> >>> tmp = single.Next.Next >>> single.Next.Next = Node(6) >>> single.Next.Next.Next = tmp >>> single.pprint() 1->2->6->4->5 >>>
注：删除和插入方法没有直接写进这个类里，但也能用代码实现类似操作。
单链表真实的删除和插入操作过程，如下所示：
6. 单链表的反转(倒序)
>>> linked = Node() >>> assign = [linked.append(i) for i in range(1,9)] >>> linked.pprint() 1->2->3->4->5->6->7->8 >>> tmp,linked = linked,Node() >>> while not tmp.is_empty(): linked.append(tmp.pop()) >>> linked.pprint() 8->7->6->5->4->3->2->1 >>>
注：用循环反复追加append原链表的pop()返回值完成倒序操作。
“捣浆糊”版的链表类就到此结束吧，准备下一篇再来重写一个进阶一点的链表类 ^_^
