本文共 1327 字，大约阅读时间需要 4 分钟。

链表

1. 单链表

链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域item和指向下一个节点的指针next。通过节点之间的相互连接，最终串联成一个链表。

创建链表:

• 头插法: 新插入的节点变为头节点
• 尾插法: 新插入的节点变为尾节点

单链表节点的插入和删除:

2. 双链表

双链表的每个节点有两个指针: 一个指向后一个节点，另一个指向前一个节点。

3. 单链表代码:

'''TOPIC: 链表author: Bluetime: 2020-08-12QQ: 2458682080'''# 创建一个节点类class Node:    def __init__(self, item):        self.item = item        self.next = Nonea = Node(1)b = Node(2)c = Node(3)a.next = bb.next = cprint(a.next.next.item)

结果:

3

头插法:

# 头插法def creat_linklist_head(li):    head = Node(li[0])    for element in li[1:]:        node = Node(element)        node.next = head        head = node    return head# 打印链表的函数def print_linklist(lk):    while lk:        print(lk.item, end=',')        lk = lk.nextlk = creat_linklist_head([1, 2, 3])print_linklist(lk)

结果为:

3,2,1,

尾插法:

# 尾插法def creat_linklist_tail(li):    head = Node(li[0])    tail = head    for element in li[1:]:        node = Node(element)        tail.next = node        tail = node    return head# 打印链表的函数def print_linklist(lk):    while lk:        print(lk.item, end=',')        lk = lk.nextlk = creat_linklist_tail([1, 2, 3, 4, 5])print_linklist(lk)

结果为:

1,2,3,4,5,

4. 复杂度分析

5. 总结

1. 链表在插入和删除的操作上明显快于顺序表
2. 链表的内存可以更灵活的分配

可以试利用链表重新实现栈和队列，链表这种链式存储的数据结构对树和图的结构有很大的启发性。

转载地址：http://ibiwi.baihongyu.com/