鱼C论坛

 找回密码
 立即注册
查看: 2259|回复: 0

[技术交流] Python实现双链数据结构(实现迭代协议,支持切片)

[复制链接]
发表于 2020-3-12 04:33:25 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 Stubborn 于 2020-3-12 04:38 编辑

链表--双向链表


关于双链表,还有大佬有什么更好的建议吗???求提点


双向链表

又称为**双链表**,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱,因此,在双向链表中,节点由三部分组成:节点数据,指向下一个节点的指针(`next`指针),指向前一个节点的指针(`prev`指针)。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表

双向链表图例


prev.png


双链表特点

  • - 创建双链表时无需指定链表的长度。
  • - 比起单链表,双链表需要多一个指针用于指向前驱节点,所以需要存储空间比单链表多一点。
  • - 双链表的插入和删除需要同时维护 next 和 prev 两个指针。
  • - 双链表中的元素访问需要通过顺序访问,即要通过遍历的方式来寻找元素。


Python代码实现,实现迭代协议,支持切片

  1. # -*- coding: utf-8 -*-
  2. # !/usr/bin/python3
  3. """
  4. @ Version : ??
  5. @ Author : Alex
  6. @ Software : Pycharm
  7. @ Time : 2020/3/9 下午3:18
  8. """

  9. import sys

  10. _no_value = object()


  11. class EmptyException(Exception): ...


  12. class Iterator:

  13.     def __init__(self, node):
  14.         self.node = node

  15.     def __iter__(self):
  16.         return self

  17.     def __next__(self):
  18.         try:
  19.             cls = self.node
  20.             self.node = self.node.next
  21.         except AttributeError:
  22.             raise StopIteration()
  23.         return cls


  24. class DoubleLinkedList:
  25.     """
  26.     双链表,只有头部的pre,和尾部的next指针为None
  27.     """

  28.     class _Node:
  29.         """value表示值,key表示内存地址"""

  30.         def __init__(self, value):
  31.             self.value = value
  32.             self.key = id(self)
  33.             self.pre = None
  34.             self.next = None

  35.         def __str__(self):
  36.             return f'<--key:{self.key}\tvalue:{self.value}-->'

  37.         def __repr__(self):
  38.             return f'<--key:{self.key}\tvalue:{self.value}-->'

  39.     def __init__(self, capacity=0xffff):
  40.         self._head = None
  41.         self._length = 0  # 链表中已有的节点个数,或者说长度
  42.         self.capacity = capacity  # 链表的最多可容纳的节点个数
  43.         self.head = self._head

  44.     def __iter__(self):
  45.         return Iterator(self._head)

  46.     def __len__(self):
  47.         return self._length

  48.     def __contains__(self, value):
  49.         cur = self._head
  50.         while cur is not None:
  51.             if cur.val == value:
  52.                 return True
  53.             cur = cur.next
  54.         return False

  55.     def __getitem__(self, index):
  56.         if isinstance(index, slice):
  57.             return self._slice(index)

  58.         if (not self.is_empty) or (index > self._length) or (index + self._length < 0):
  59.             raise IndexError('DoubleLinkedList index out of range')
  60.         if index < 0:
  61.             index += self._length + 1
  62.         return self._getitem(index)

  63.     def __setitem__(self, index, value):
  64.         node = self[index]
  65.         node.value = value

  66.     def __delitem__(self, index):
  67.         """
  68.         删除一个节点:
  69.             per_node <---> node <-->  next_node
  70.                 per_node的next指向next_node
  71.                 next_node的pre指向per_node
  72.                 node 的pre和next修改为None,或者del
  73.         """
  74.         node = self[index]
  75.         try:
  76.             node.pre.next, node.next.pre = node.next, node.pre
  77.             node.pre = node.next = None
  78.             self._length -= 1
  79.         except AttributeError:
  80.             raise IndexError('DoubleLinkedList index out of range')

  81.     @property
  82.     def is_empty(self):
  83.         return bool(self._head)

  84.     @property
  85.     def length(self):
  86.         return self._length

  87.     def _slice(self, s):
  88.         cls = type(self)()
  89.         start, stop, step = s.start or 0, s.stop or sys.maxsize, s.step or 1
  90.         [cls.append(self[i].value) for i in list(range(start, stop, step))]
  91.         return cls

  92.     def _getitem(self, index):
  93.         idx = 1
  94.         node = self._head
  95.         while node.next:
  96.             if idx == index: break
  97.             node = node.next
  98.             idx += 1
  99.         return node

  100.     def _add(self, node):
  101.         """头部添加"""
  102.         node.next = self._head
  103.         self._head = node
  104.         if node.next is not None: node.next.pre = node

  105.     def _append(self, node):
  106.         """尾部添加"""
  107.         head = self._head
  108.         while head.next:
  109.             head = head.next
  110.         head.next = node
  111.         node.pre = head

  112.     def _insert(self, node, index):
  113.         """
  114.         :param node:    需要插入的节点
  115.         :param index:   插入的索引位置

  116.         _per_node <---> node <-->_node
  117.         修改_per_node的next指针,指向node
  118.         修改_node的pre指针,指向node
  119.         在分别修改node的next和pre指针指向前后node节点
  120.         """
  121.         _node = self[index]
  122.         _per_node = _node.pre
  123.         if _per_node is None: self._add(node)

  124.         _per_node.next = node
  125.         node.pre = _node.pre
  126.         node.next = _node
  127.         _node.pre = node

  128.     def append(self, value, index=None, head=False):
  129.         """
  130.             添加一个节点, 默认从尾部添加
  131.         :param value: 节点值
  132.         :param index: int型  如果有值,认为是插入一个节点
  133.         :param head:  bool型 如果是True,认为是从头部插入
  134.         注意如果index和head同为True , 默认为头部插入节点
  135.         """
  136.         if self._length == self.capacity:
  137.             raise EmptyException("链表超出最大长度")
  138.         node_cls = self._Node(value)
  139.         if self._head is None or head:
  140.             self._add(node_cls)
  141.         elif index is not None:
  142.             self._insert(node_cls, index)
  143.         else:
  144.             self._append(node_cls)

  145.         self._length += 1

  146.     def delete(self, key):
  147.         del self[key]

  148.     def get(self, index, val_type=_no_value):
  149.         """
  150.         val_type: 如果有设置默认值,发生报错将返回默认值
  151.         """
  152.         if val_type is not _no_value:
  153.             try:
  154.                 return self[index]
  155.             except Exception as e:
  156.                 return val_type
  157.         return self[index]


  158. if __name__ == '__main__':
  159.     t = DoubleLinkedList()
  160.     t.append(2)
  161.     t.append(3)
  162.     t.append(4)
  163.     print(len(t[1:5:2]))
  164.     for i in t: print(i)
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-13 13:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表