链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
链表由一系列结点组成，结点可以在运行时动态生成
优点
由于不必须按顺序存储，链表在插入、删除的时候可以达到O(1)的复杂度，比线性表快得多
缺点
相比于线性表顺序结构操作复杂，查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)
分类
单向链表
单向链表的链接方向是单向的，对链表的访问要从头部开始顺序读取
组成
每个结点包括两个部分：
是存储数据元素的数据域，
存储下一个结点地址的指针域
示例：
class Node(object):
def __init__(self, item):
self.item = item
self.next = None
操作
- 遍历
- 插入、删除
- 建立
- 头插法
- 尾插法
class Node(object):
def __init__(self, item=None):
self.item = item
self.next = None
def traversal(head_node):
"""链表的遍历"""
cur_node = head_node
while cur_node is not None:
print(cur_node.item)
cur_node = cur_node.next
def add(value, cur_node):
"""链表的插入，在当前节点之后插入新的节点"""
new_node = Node(value)
new_node.next, cur_node.next = cur_node.next, new_node
def delete(cur_node):
"""链表的删除，删除当前节点之后的节点"""
tar_node = cur_node.next
cur_node.next = cur_node.next.next
del tar_node
def create_linklist_f(li):
"""头插法建立链表"""
head = Node()
for num in li:
temp = Node(num)
temp.next, head.next = head.next, temp
return head
def create_linklist_r(li):
"""尾插法建立链表"""
head = Node()
r_node = head
for num in li:
temp = Node(num)
r_node.next, temp.next = temp, None
r_node = r_node.next
return head
双向链表
双向链表每个数据结点中都有两个指针，分别指向直接后继和直接前驱，所以从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点
组成
每个结点包括两个部分：
是存储数据元素的数据域，
存储下一个结点地址的指针域
示例：
class Node(object):
def __init__(self, item):
self.item = item
self.next = None
循环链表
表中最后一个结点的指针域指向头结点，整个链表形成一个环
组成
每个结点包括两个部分：
是存储数据元素的数据域，
存储下一个结点地址的指针域
示例：
class Node(object):
def __init__(self, item):
self.item = item
self.next = None