1，主程序

  1. """
  2. LinkList.py
  3. 功能：实现单链表的构建和功能操作
  4. 重点代码：
  5. """
  8. # 创建节点类，实例化对象--->将在内存中随意开辟空间
  9. class Node:
  10.     def __init__(self, value, next=None):
  11.         self.value = value  # 有用的数据
  12.         self.next = next  # 循环指向下一个节点，没有数据意义，但有逻辑意义
  15. node1 = Node(1)
  16. node2 = Node(2, node1)  # node2.next = node1
  17. node3 = Node(3, node2)  # node3.next = node2
  19. a = 1
  20. b = (2, a)
  21. c = (3, b)
  24. class LinkList:
  25.     """
  26.     思路： 单链表类，生成对象可以进行增删改查等操作
  27.           具体操作可以通过调用方法完成
  28.     """
  30.     def __init__(self):
  31.         """
  32.         初始化链表，标记一个链表的开端，以便于获取后续的节点
  33.         两种方法：初始化一个节点；初始化一个变量
  34.         """
  35.         self.head = Node(None)
  37.     # 通过list_为链表添加一组节点
  38.     def init_list(self, list_):  # 传入列表，为了与关键字区分，遂加入下划线
  39.         p = self.head  # p作为牺牲的变量，可以移动
  40.         for i in list_:
  41.             p.next = Node(i)
  42.             p = p.next
  44.     # 遍历链表
  45.     def show(self):
  46.         p = self.head.next  # 第一个有效节点
  47.         while p is not None:  # 判断对象是否相等用 is / is not ； 判断值是否相等用== / !=
  48.             print(p.value)
  49.             p = p.next  # p 向后移动
  51.     # 判断链表是否为空,通过头节点的next指针
  52.     def is_empty(self):
  53.         if self.head.next is None:
  54.             return True
  55.         else:
  56.             return False
  58.     def clear(self):
  59.         self.head.next = None  # 仅仅是断开头节点与其他数据节点，数据节点会被Python内存回收机制清理
  61.     # 尾部插入
  62.     def append(self, val):
  63.         p = self.head
  64.         while p.next is not None:
  65.             p = p.next
  66.         p.next = Node(val)
  68.     # 头部插入
  69.     def head_insert(self, val):
  70.         node = Node(val)  # 生成一个节点
  71.         node.next = self.head.next  # 将插入节点与头节点的next指针连接
  72.         self.head.next = node  # 再将head的next指针指向插入节点【如果不这样做，那么就会导致数据节点与头节点失联，等同于线性表链式存储的清空操作】
  74.     # 指定位置插入
  75.     def insert(self, index, val):
  76.         """
  77.         解决思路：首先应该找到插入的位置；生成节点，指针先指向被插入位置的后一个元素；再指向被插入位置的前一个元素；
  78.                 插入位置的确定：从初始化的第一个元素算起，移动次数即为插入位置的索引值；
  79.                 移动方式：首先令新节点的位置等于头节点，然后根据目标位置确定移动次数，比如在索引值为2的位置插入，则移动两次
  80.         评价：链表和列表插入值的平均复杂度没有太大差别
  81.         """
  82.         p = self.head
  83.         for i in range(index):
  84.             if p.next is None:  # 超出索引值位置的最大范围,结束循环
  85.                 break
  86.             p = p.next
  87.         node = Node(val)
  88.         node.next = p.next
  89.         p.next = node
  91.     def delete(self, x):  # x:被删除对象
  92.         p = self.head
  93.         # 结束循环必然存在一个条件为假
  94.         while p.next and p.next.value != x:  # 新建节点，指向下一个元素的节点不能再指向为空
  95.             p = p.next
  96.         if p.next is None:
  97.             raise ValueError("x is not in LinkList.")  # 如果指向空数据结构
  98.         else:
  99.             p.next = p.next.next
  101.     def get_index(self, index):
  102.         if index < 0:  # 判断输入值的范围，不支持小于零的索引方式
  103.             raise IndexError("index out of range.")
  104.         p = self.head.next
  105.         for i in range(index):
  106.             if p.next is None:  # 如果next指针指向空节点，则超出范围，抛出报错
  107.                 raise IndexError("index out of range.")
  108.             p = p.next
  109.         return p.value
  112. l = LinkList()
  113. l.init_list([2, 5, 3, 8, 6])
  114. l.show()

2，测试程序

  1. from LineTable.Linklist import *
  2. import time
  5. l = []
  6. for i in range(999999):
  7.     l.append(i)
  9. link = LinkList()
  10. link.init_list(l)
  12. tm = time.time()
  13. # for i in l:
  14. #     print(i)  # 列表
  15. # link.show()  # 链表
  17. # l.append(8866)
  18. # link.append(8866) # 尾插
  20. # l.insert(0,8866)
  21. # link.head_insert(8866) # 头插
  23. # link.insert(100, 3576)  # 指定位置插入
  24. # link.show()
  26. # link.delete(1)  # 删除
  27. # l.remove(1)
  28. print("-----------------------------")
  29. # link.show()
  31. # link.show()
  32. # print("-----------------------------")
  33. # print(link.get_index(4))
  34. print("time: ", time.time() - tm)