|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 Stubborn 于 2020-3-12 04:38 编辑
链表--双向链表
关于双链表,还有大佬有什么更好的建议吗???求提点
双向链表
又称为**双链表**,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱,因此,在双向链表中,节点由三部分组成:节点数据,指向下一个节点的指针(`next`指针),指向前一个节点的指针(`prev`指针)。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
双向链表图例
双链表特点
- - 创建双链表时无需指定链表的长度。
- - 比起单链表,双链表需要多一个指针用于指向前驱节点,所以需要存储空间比单链表多一点。
- - 双链表的插入和删除需要同时维护 next 和 prev 两个指针。
- - 双链表中的元素访问需要通过顺序访问,即要通过遍历的方式来寻找元素。
Python代码实现,实现迭代协议,支持切片
- # -*- coding: utf-8 -*-
- # !/usr/bin/python3
- """
- @ Version : ??
- @ Author : Alex
- @ Software : Pycharm
- @ Time : 2020/3/9 下午3:18
- """
- import sys
- _no_value = object()
- class EmptyException(Exception): ...
- class Iterator:
- def __init__(self, node):
- self.node = node
- def __iter__(self):
- return self
- def __next__(self):
- try:
- cls = self.node
- self.node = self.node.next
- except AttributeError:
- raise StopIteration()
- return cls
- class DoubleLinkedList:
- """
- 双链表,只有头部的pre,和尾部的next指针为None
- """
- class _Node:
- """value表示值,key表示内存地址"""
- def __init__(self, value):
- self.value = value
- self.key = id(self)
- self.pre = None
- self.next = None
- def __str__(self):
- return f'<--key:{self.key}\tvalue:{self.value}-->'
- def __repr__(self):
- return f'<--key:{self.key}\tvalue:{self.value}-->'
- def __init__(self, capacity=0xffff):
- self._head = None
- self._length = 0 # 链表中已有的节点个数,或者说长度
- self.capacity = capacity # 链表的最多可容纳的节点个数
- self.head = self._head
- def __iter__(self):
- return Iterator(self._head)
- def __len__(self):
- return self._length
- def __contains__(self, value):
- cur = self._head
- while cur is not None:
- if cur.val == value:
- return True
- cur = cur.next
- return False
- def __getitem__(self, index):
- if isinstance(index, slice):
- return self._slice(index)
- if (not self.is_empty) or (index > self._length) or (index + self._length < 0):
- raise IndexError('DoubleLinkedList index out of range')
- if index < 0:
- index += self._length + 1
- return self._getitem(index)
- def __setitem__(self, index, value):
- node = self[index]
- node.value = value
- def __delitem__(self, index):
- """
- 删除一个节点:
- per_node <---> node <--> next_node
- per_node的next指向next_node
- next_node的pre指向per_node
- node 的pre和next修改为None,或者del
- """
- node = self[index]
- try:
- node.pre.next, node.next.pre = node.next, node.pre
- node.pre = node.next = None
- self._length -= 1
- except AttributeError:
- raise IndexError('DoubleLinkedList index out of range')
- @property
- def is_empty(self):
- return bool(self._head)
- @property
- def length(self):
- return self._length
- def _slice(self, s):
- cls = type(self)()
- start, stop, step = s.start or 0, s.stop or sys.maxsize, s.step or 1
- [cls.append(self[i].value) for i in list(range(start, stop, step))]
- return cls
- def _getitem(self, index):
- idx = 1
- node = self._head
- while node.next:
- if idx == index: break
- node = node.next
- idx += 1
- return node
- def _add(self, node):
- """头部添加"""
- node.next = self._head
- self._head = node
- if node.next is not None: node.next.pre = node
- def _append(self, node):
- """尾部添加"""
- head = self._head
- while head.next:
- head = head.next
- head.next = node
- node.pre = head
- def _insert(self, node, index):
- """
- :param node: 需要插入的节点
- :param index: 插入的索引位置
- _per_node <---> node <-->_node
- 修改_per_node的next指针,指向node
- 修改_node的pre指针,指向node
- 在分别修改node的next和pre指针指向前后node节点
- """
- _node = self[index]
- _per_node = _node.pre
- if _per_node is None: self._add(node)
- _per_node.next = node
- node.pre = _node.pre
- node.next = _node
- _node.pre = node
- def append(self, value, index=None, head=False):
- """
- 添加一个节点, 默认从尾部添加
- :param value: 节点值
- :param index: int型 如果有值,认为是插入一个节点
- :param head: bool型 如果是True,认为是从头部插入
- 注意如果index和head同为True , 默认为头部插入节点
- """
- if self._length == self.capacity:
- raise EmptyException("链表超出最大长度")
- node_cls = self._Node(value)
- if self._head is None or head:
- self._add(node_cls)
- elif index is not None:
- self._insert(node_cls, index)
- else:
- self._append(node_cls)
- self._length += 1
- def delete(self, key):
- del self[key]
- def get(self, index, val_type=_no_value):
- """
- val_type: 如果有设置默认值,发生报错将返回默认值
- """
- if val_type is not _no_value:
- try:
- return self[index]
- except Exception as e:
- return val_type
- return self[index]
- if __name__ == '__main__':
- t = DoubleLinkedList()
- t.append(2)
- t.append(3)
- t.append(4)
- print(len(t[1:5:2]))
- for i in t: print(i)
复制代码 |
|