链表

1. 什么是链表

　　链表（Linked List）：一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。即「链表」 是实现线性表的链式存储结构的基础。

　　1. 单链表

　　　每个数据元素占用若干存储单元的组合称为一个「链节点」，还存放一个指出这个数据元素在逻辑关系上的直接后继元素所在链节点的地址，该地址被称为「后继指针 next」

　　2. 双向链表

　　　链表的一种，也叫做双链表。它的每个链节点中有两个指针，分别指向直接后继和直接前驱

　　3. 循环链表

　　　链表的一种。它的最后一个链节点指向头节点，形成一个环

2. 链表的创建和遍历　

# 创建链表
class Link:
    def __init__(self, item):
        self.item = item
        self.next = None

# 头插法插入数据: 头改变
def head_insert(li):
    head = Link(li[0])      # 第一个定为head
    for element in li[1:]:
        link = Link(element)    # 插入链表
        link.next = head        # 链表的next指向当前的head
        head = link             # head指向新插入的元素
    return head

# 尾插法插入数据: 头不变，tail改变
def tail_insert(li):
    head = Link(li[0])      # 指定head
    tail = head             # 指定tail，即尾部，只有一个时，head等于tail
    for element in li[1:]:
        link = Link(element)    # 插入数据
        tail.next = link        # 尾部的next指向插入的数据
        tail = link             # 尾部指向插入的元素
    return head

# 链表遍历
def print_link(lk):
    while lk:
        print(lk.item, end=' ')
        lk = lk.next    # 等价于link.next.next.item，next的数量看元素的个数

a = head_insert([1, 2, 3, 5, 7, 9])
print_link(a)

3. 链表的中间插入

　　代码实现：

# 中间插入数据
def center_insert(index, val):
    count = 0       # 定义一个计数器，用来判断插入的指针位置
    head = tail_insert([1, 2, 3, 5, 7, 9])  # 调用函数插入数据
    curNode = head  # curNode指向插入的位置，初始值为第0个
    while curNode and count < index - 1:
        count += 1
        curNode = curNode.next  # 循环多少次，就叠加多少个next

    node = Link(val)        # 插入元素
    node.next = curNode.next    # 插入元素的next指向当前插入位置的下一个元素，即尾巴相连
    curNode.next = node         # 当前位置的为前一个元素的next，即头部相连
    return  head

 5. 链表的删除

 　　代码实现：

# 删除链表头部
def del_head():
    head = tail_insert([1, 2, 3, 5, 7, 9])  # 插入链表数据
    if head:    # 存在则将head指向他的下一个元素
        head = head.next
    return head


# 从链表中间删除元素
def del_center(index):
    head = tail_insert([1, 2, 3, 5, 7, 9])  # 插入链表数据
    count = 0
    curNode = head
    while curNode and count < index - 1:
        count += 1
        curNode = curNode.next

    curNode.next = curNode.next.next    # 删除元素的前一个元素的next跳过删除的元素，指向删除元素的后一个元素
    return head