链表

链表是一种在存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现。链表是由一系列的结点组成，结点可以在运行时动态生成。每个结点包含两部分：数据域与指针域。数据域存储数据元素，指针域存储下一结点的指针。

资料来源：https://zhuanlan.zhihu.com/p/60057180

单向链表

它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
image.png
由图可知：

  • head 保存首地址，item 存储数据，next 指向下一结点地址。

链表的优缺点：

  • 链表失去了序列的随机读取优点，同时链表增加了指针域，空间开销也较大。
  • 但它对存储空间的使用要相对灵活。
  • 优势示例：
    • 列如：有一堆数据[1,2,3,5,6,7]，要在3和5之间插入4, 如果用数组，需要将5之后的数据都往后退一位，然后再插入4，这样非常麻烦，但是如果用链表，我就直接在3和5之间插入4就行。


定义节点

结点的数据结构为数据元素(item)与 指针(next)

  1. class Node(object):
  2.     """单链表的结点"""
  4.     def __init__(self, item):
  5.         # item存放数据元素
  6.         self.item = item
  7.         # next是下一个节点的标识
  8.         self.next = None

定义链表

链表需要具有首地址指针head。

  1. class SingleLinkList(object):
  2.     """单链表"""
  4.     def __init__(self):
  5.         self._head = None

示例：创建链表

  1. class Node(object):
  2.     """单链表的结点"""
  4.     def __init__(self, item):
  5.         # item存放数据元素
  6.         self.item = item
  7.         # next是下一个节点的标识
  8.         self.next = None
  11. class SingleLinkList(object):
  12.     """单链表"""
  14.     def __init__(self):
  15.         self._head = None
  18. if __name__ == '__main__':
  19.     # 创建链表
  20.     link_list = SingleLinkList()
  21.     # 创建结点
  22.     node1 = Node(1)
  23.     node2 = Node(2)
  25.     # 将结点添加到链表
  26.     link_list._head = node1
  27.     # 将第一个结点的next指针指向下一结点
  28.     node1.next = node2
  30.     # 访问链表
  31.     print(link_list._head.item)  # 访问第一个结点数据 输出：1
  32.     print(link_list._head.next.item)  # 访问第二个结点数据 输出：2

在链表中添加操作方法（增删改查）

主要实现功能如下：

  • is_empty()链表是否为空
  • length()链表长度
  • items()获取链表数据迭代器
  • add(item)链表头部添加元素
  • addend(item) 链表尾部添加元素
  • insert(pos,item) 指定位置添加元素
  • remove(item) 删除节点
  • find(item) 查找节点是否存在

代码如下：

  1. class Node(object):
  2.     """单链表的结点"""
  4.     def __init__(self, item):
  5.         # item存放数据元素
  6.         self.item = item
  7.         # next是下一个节点的标识
  8.         self.next = None
  11. class SingleLinkList(object):
  12.     """单链表"""
  14.     def __init__(self):
  15.         self.head = None
  17.     def is_empty(self):
  18.         """判断链表是否为空"""
  19.         return self.head is None
  21.     def length(self):
  22.         """链表长度"""
  23.         # 初始指针指向head
  24.         cur = self.head
  25.         count = 0
  26.         # 指针指向None 表示到达尾部
  27.         while cur is not None:
  28.             count += 1
  29.             # 指针下移
  30.             cur = cur.next
  31.         return count
  33.     def items(self):
  34.         """遍历链表"""
  35.         # 获取head指针
  36.         cur = self.head
  37.         # 循环遍历
  38.         while cur is not None:
  39.             # 返回生成器
  40.             yield cur.item
  41.             # 指针下移
  42.             cur = cur.next
  44.     def add(self, item):
  45.         """向链表头部添加元素"""
  46.         node = Node(item)
  47.         # 新结点指针指向原头部结点
  48.         node.next = self.head
  49.         # 头部结点指针修改为新结点
  50.         self.head = node
  52.     def append(self, item):
  53.         """尾部添加元素"""
  54.         node = Node(item)
  55.         # 先判断是否为空链表
  56.         if self.is_empty():
  57.             # 空链表，head 指向新结点
  58.             self.head = node
  59.         else:
  60.             # 不是空链表，则找到尾部，将尾部next结点指向新结点
  61.             cur = self.head
  62.             while cur.next is not None:
  63.                 cur = cur.next
  64.             cur.next = node
  66.     def insert(self, index, item):
  67.         """指定位置插入元素"""
  68.         # 指定位置在第一个元素之前，在头部插入
  69.         if index <= 0:
  70.             self.add(item)
  71.         # 指定位置超过尾部，在尾部插入
  72.         elif index > (self.length() - 1):
  73.             self.append(item)
  74.         else:
  75.             # 创建元素结点
  76.             node = Node(item)
  77.             cur = self.head
  78.             # 循环到需要插入的位置
  79.             for i in range(index - 1):
  80.                 cur = cur.next
  81.             node.next = cur.next
  82.             cur.next = node
  84.     def remove(self, item):
  85.         """删除节点"""
  86.         cur = self.head
  87.         pre = None
  88.         while cur is not None:
  89.             # 找到指定元素
  90.             if cur.item == item:
  91.                 # 如果第一个就是删除的节点
  92.                 if not pre:
  93.                     # 将头指针指向头节点的后一个节点
  94.                     self.head = cur.next
  95.                 else:
  96.                     # 将删除位置前一个节点的next指向删除位置的后一个节点
  97.                     pre.next = cur.next
  98.                 return True
  99.             else:
  100.                 # 继续按链表后移节点
  101.                 pre = cur
  102.                 cur = cur.next
  104.     def find(self, item):
  105.         """查找元素是否存在"""
  106.         return item in self.items()
  109. if __name__ == '__main__':
  110.     link_list = SingleLinkList()
  111.     # 向链表尾部添加数据
  112.     for i in range(5):
  113.         link_list.append(i)
  114.     # 向头部添加数据
  115.     link_list.add(6)
  116.     # 遍历链表数据
  117.     for i in link_list.items():
  118.         print(i, end='\t')
  119.     # 链表数据插入数据
  120.     link_list.insert(3, 9)
  121.     print('\n', list(link_list.items()))
  122.     # 删除链表数据
  123.     link_list.remove(0)
  124.     # 查找链表数据
  125.     print(link_list.find(4))

输出结果：

  1. 6    0    1    2    3    4    
  2. [6, 0, 1, 9, 2, 3, 4]
  3. True

循环链表

image.png

单向循环链表为单向链表的变种，链表的最后一个next指向链表头，新增一个循环。

循环链表定义

  1. class Node(object):
  2.     """单链表的结点"""
  4.     def __init__(self, item):
  5.         # item存放数据元素
  6.         self.item = item
  7.         # next是下一个节点的标识
  8.         self.next = None
  11. class SingleCycleLinkList(object):
  12.     """循环链表"""
  13.     def __init__(self):
  14.         self.head = None
  16.     def is_empty(self):
  17.         """判断链表是否为空"""
  18.         return self.head is None
  20.     def length(self):
  21.         """链表长度"""
  22.         # 链表为空
  23.         if self.is_empty():
  24.             return 0
  25.         # 链表不为空
  26.         count = 1
  27.         cur = self.head
  28.         while cur.next != self.head:
  29.             count += 1
  30.             # 指针下移
  31.             cur = cur.next
  32.         return count
  34.     def items(self):
  35.         """ 遍历链表 """
  36.         # 链表为空
  37.         if self.is_empty():
  38.             return
  39.         # 链表不为空
  40.         cur = self.head
  41.         while cur.next != self.head:
  42.             yield cur.item
  43.             cur = cur.next
  44.         yield cur.item
  46.     def add(self, item):
  47.         """ 头部添加结点"""
  48.         node = Node(item)
  49.         if self.is_empty():  # 为空
  50.             self.head = node
  51.             node.next = self.head
  52.         else:
  53.             # 添加结点指向head
  54.             node.next = self.head
  55.             cur = self.head
  56.             # 移动结点，将末尾的结点指向node
  57.             while cur.next != self.head:
  58.                 cur = cur.next
  59.             cur.next = node
  60.         # 修改 head 指向新结点
  61.         self.head = node
  63.     def append(self, item):
  64.         """尾部添加结点"""
  65.         node = Node(item)
  66.         if self.is_empty():  # 为空
  67.             self.head = node
  68.             node.next = self.head
  69.         else:
  70.             # 寻找尾部
  71.             cur = self.head
  72.             while cur.next != self.head:
  73.                 cur = cur.next
  74.             # 尾部指针指向新结点
  75.             cur.next = node
  76.             # 新结点指针指向head
  77.             node.next = self.head
  79.     def insert(self, index, item):
  80.         """ 指定位置添加结点"""
  81.         if index <= 0:  # 指定位置小于等于0，头部添加
  82.             self.add(item)
  83.         # 指定位置大于链表长度，尾部添加
  84.         elif index > self.length() - 1:
  85.             self.append(item)
  86.         else:
  87.             node = Node(item)
  88.             cur = self.head
  89.             # 移动到添加结点位置
  90.             for i in range(index - 1):
  91.                 cur = cur.next
  92.             # 新结点指针指向旧结点
  93.             node.next = cur.next
  94.             # 旧结点指针 指向 新结点
  95.             cur.next = node
  97.     def remove(self, item):
  98.         """ 删除一个结点 """
  99.         if self.is_empty():
  100.             return
  101.         cur = self.head
  102.         pre = Node
  103.         # 第一个元素为需要删除的元素
  104.         if cur.item == item:
  105.             # 链表不止一个元素
  106.             if cur.next != self.head:
  107.                 while cur.next != self.head:
  108.                     cur = cur.next
  109.                 # 尾结点指向 头部结点的下一结点
  110.                 cur.next = self.head.next
  111.                 # 调整头部结点
  112.                 self.head = self.head.next
  113.             else:
  114.                 # 只有一个元素
  115.                 self.head = None
  116.         else:
  117.             # 不是第一个元素
  118.             pre = self.head
  119.             while cur.next != self.head:
  120.                 if cur.item == item:
  121.                     # 删除
  122.                     pre.next = cur.next
  123.                     return True
  124.                 else:
  126.                     pre = cur  # 记录前一个指针
  127.                     cur = cur.next  # 调整指针位置
  128.         # 当删除元素在末尾
  129.         if cur.item == item:
  130.             pre.next = self.head
  131.             return True
  133.     def find(self, item):
  134.         """ 查找元素是否存在"""
  135.         return item in self.items()
  138. if __name__ == '__main__':
  139.     link_list = SingleCycleLinkList()
  140.     print(link_list.is_empty())
  141.     # 头部添加元素
  142.     for i in range(5):
  143.         link_list.add(i)
  144.     print(list(link_list.items()))
  145.     # 尾部添加元素
  146.     for i in range(6):
  147.         link_list.append(i)
  148.     print(list(link_list.items()))
  149.     # 添加元素
  150.     link_list.insert(3, 45)
  151.     print(list(link_list.items()))
  152.     # 删除元素
  153.     link_list.remove(5)
  154.     print(list(link_list.items()))
  155.     # 元素是否存在
  156.     print(4 in link_list.items())