Python实现双链数据结构(实现迭代协议，支持切片)

Stubborn

链表--双向链表


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

双向链表

又称为**双链表**，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，因此，在双向链表中，节点由三部分组成：节点数据，指向下一个节点的指针(`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)