专栏首页python3Python 实现双向链表(图解)

Python 实现双向链表(图解)

Python 实现双向链表(图解)


双向链表

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

双向链表基本方法实现(Python)

1. 初始化链表

定义节点结构:指针域pre、next和数据域data 为方便操作添加了head和tail节点,初始化时head.next–>tail,tail.pre–>next

"""节点类"""
class Node(object):
    def __init__(self, data=None):
        self.data = data
        self.pre = None
        self.next = None

"""初始化双向链表"""

def __init__(self):
    """
    设置头尾,操作比较容易
    头--(next)--》尾
    尾--(pre)--》头
    :return:
    """
    head = Node()
    tail = Node()
    self.head = head
    self.tail = tail
    self.head.next = self.tail
    self.tail.pre = self.head

2. 获取链表长度

起始head,每有一个节点,length+1

"""获取链表长度"""

def __len__(self):
    length = 0
    node = self.head
    while node.next != self.tail:
        length += 1
        node = node.next
    return length

3. 追加节点

因为有tail 节点,所以找到tail.pre 节点就好了

"""追加节点"""

def append(self, data):
    """
    :param data:
    :return:
    """
    node = Node(data)
    pre = self.tail.pre
    pre.next = node
    node.pre = pre
    self.tail.pre = node
    node.next = self.tail
    return node

4. 获取节点

获取节点要判断index正负值

 """获取节点"""
def get(self, index):
    """
    获取第index个值,若index>0正向获取else 反向获取
    :param index:
    :return:
    """
    length = len(self)
    index = index if index >= 0 else length + index
    if index >= length or index < 0: return None
    node = self.head.next
    while index:
        node = node.next
        index -= 1
    return node

5. 设置节点

找到当前节点赋值即可

"""设置节点"""

def set(self, index, data):
    node = self.get(index)
    if node:
        node.data = data
    return node

6. 插入节点

插入节点需要找到插入节点的前一个节点pre_node和后一个节点next_node(索引index的正负,前一节点不同,需要判断一下),然后将pre_node.next–>node,node.pre->pre_node;next_node.pre–>node,node.next–>next_node

"""插入节点"""

def insert(self, index, data):
    """
    因为加了头尾节点所以获取节点node就一定存在node.next 和 node.pre
    :param index:
    :param data:
    :return:
    """
    length = len(self)
    if abs(index + 1) > length:
        return False
    index = index if index >= 0 else index + 1 + length

    next_node = self.get(index)
    if next_node:
        node = Node(data)
        pre_node = next_node.pre
        pre_node.next = node
        node.pre = pre_node
        node.next = next_node
        next_node.pre = node
        return node

7. 删除节点

删除节点,也要区分一下索引的正负。找到当前节点的前一个节点pre_node和后一个节点next_node,将pre_node.nex–>next_node即可

"""删除节点"""

def delete(self, index):
    node = self.get(index)
    if node:
        node.pre.next = node.next
        node.next.pre = node.pre
        return True

    return False

8. 反转链表

反转链表的实现有多种方式,比较简单的就是生成一个新的链表--》可以用数组存储所有节点让后倒序生成新的链表 在这里用下面这种方式生产: 可能有点绕 1.node.next –> node.pre;node.pre –> node.next(递归) 2.head.next –> None;tail.pre –> None 3.head–>tail;tail–>head

"""反转链表"""
def __reversed__(self):
    """
    1.node.next --> node.pre
      node.pre --> node.next
    2.head.next --> None
      tail.pre --> None
    3.head-->tail
     tail-->head
    :return:
    """
    pre_head = self.head
    tail = self.tail

    def reverse(pre_node, node):
        if node:
            next_node = node.next
            node.next = pre_node
            pre_node.pre = node
            if pre_node is self.head:
                pre_node.next = None
            if node is self.tail:
                node.pre = None
            return reverse(node, next_node)
        else:
            self.head = tail
            self.tail = pre_head

    return reverse(self.head, self.head.next)

9. 清空链表

类似初始化

"""清空链表"""
def clear(self):
    self.head.next = self.tail
    self.tail.pre = self.head

git 路径 https://github.com/wangpanjun/datastructure.git


作者 [@小王] 2015 年 11月

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python Ast介绍及应用

    Abstract Syntax Trees即抽象语法树。Ast是python源码到字节码的一种中间产物,借助ast模块可以从语法树的角度分析源码结构。此外,我们...

    py3study
  • Linux下切换Python版本

    这两天遇到一个问题需要在 python3 的环境下进行测试,由于Linux默认已经安装了Python2.7,并且作者一直也在使用 ,所以需要重新安装并临时切换到...

    py3study
  • centos 7 安装python3.6

    centos7 默认安装了python2.7.5,当需要使用python3的时候,可以手动下载python源码后编译安装.

    py3study
  • P3372 【模板】线段树 1 线段树模版+懒惰标记

    用户2965768
  • 手把手用Python教你如何发现隐藏wifi

    细心的小伙伴可能知道,小编之前发布过一篇使用Python发现酒店隐藏的针孔摄像头,没有来得及上车的小伙伴也没关系,可以戳这篇文章了解一下:使用Pyhton带你...

    Python进阶者
  • angularJS学习之路(七)---子控制器关于是引用机制还是复制机制的问题---原型继承

    原型继承 要弄清一点:    修改父级对象中的alue值会同时修改 子对象中的alue值,但是反过来就不行了,

    wust小吴
  • 剑指offer - 二叉搜索树与双向链表 - JavaScript

    题目描述:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

    心谭博客
  • 【文章推荐】霸王餐,如何吃出霸气有力的互联网商业模式

    Super注:这是阿超一位朋友的一篇文章,对“罗辑思维”感兴趣的朋友可以看看。这位朋友希望与更多人交流,大家对其话题感兴趣,可以加他微信,见文末。 ...

    罗超频道
  • 【编程基础】Win32窗口下调试输出

    在Win32的console下,我们可以用基本的printf,来输出调试信息,这个很方便。不过要是在非console的窗口模式应用程序里面,就不能使用print...

    程序员互动联盟
  • 为什么说它对 Android 未来的发展十分重要?

    由于其开放性,Android 在其前十年取得了显著的增长。有大量的设备可供选择,蓬勃发展的开发者生态系统提供了许多应用和游戏,为这些设备赋予了长久的生命力。作为...

    Android 开发者

扫码关注云+社区

领取腾讯云代金券