Python 实现双向链表

#!usr/bin/env python  
#-*- coding:utf-8 -*- 

""" 
@author:yzk13 
@time: 2018/04/18
双向链表
https://blog.csdn.net/qq490691606/article/details/49948263
"""

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

class DoublyLinkedList(object):
    """
    双向链表类
    """
    def __init__(self):
        """
        初始化链表
        """
        head = Node(None)
        tail = Node(None)
        self.head = head
        self.tail = tail
        self.head.next = self.tail
        self.tail.pre = self.head

    @property
    def length(self):
        """
        获取链表长度
        :return:
        """
        length = 0
        node = self.head
        while node.next != self.tail:
            length += 1
            node = node.next
        return length

    def print(self):
        """
        打印
        :return:
        """
        if self.length == 0:
            print('Nothing')
        else:
            node = self.head.next
            print('[', end='')
            while node.next != self.tail:
                print(node.value, ', ', end='')
                node = node.next
            print('%s]' % node.value)

    def append(self, value):
        """
        表尾添加节点
        :return:
        """
        node = Node(value)
        pre = self.tail.pre
        # 两点之间进行双双链接
        pre.next = node
        node.pre = pre
        node.next = self.tail
        self.tail.pre = node
        return node

    def get(self, index):
        """
        获取节点
        :param index:
        :return:
        """
        if index < 0 or index > self.length:
            print('Index错误,索引越界')
            return None
        else:
            node = self.head.next
            while index:
                node = node.next
                index -= 1
            return node

    def insert(self, index, value):
        """
        插入
        :param index:
        :param value:
        :return:
        """
        if index < 0 or index > self.length:
            print('Index 错误, 索引越界')
        next_node = self.get(index)
        # 开始插入
        node = Node(value)
        pre_node = next_node.pre

        pre_node.next = node
        node.pre = pre_node
        node.next = next_node
        next_node.pre = node
        return node

    def delete(self, index):
        """
        删除节点
        :param index:
        :return:
        """
        node = self.get(index)
        if node:
            node.pre.next = node.next
            node.next.pre = node.pre
            return True
        else:
            return False

    def reverse(self):
        """
        反转链表
        :return:
        1.node.next --> node.pre
          node.pre --> node.next
        2.head.next --> None
          tail.pre --> None
        3.head-->tail
        tail-->head
        """
        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)

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







if __name__ == '__main__':
    l = DoublyLinkedList()

    # 测试在表尾添加节点
    l.append(3)
    l.append(4)
    l.append(5)
    l.print()

    # 测试get
    i = 0
    print('第', i, '个元素为: ', l.get(i).value)

    # 测试索引插入
    print('索引插入...')
    l.insert(1, 7)
    l.insert(0, 8)
    l.print()

    # 测试删除节点
    print('删除节点...')
    l.delete(0)
    l.delete(3)
    l.print()

    # 测试反转
    print('反转...')
    l.reverse()
    l.print()

    # 测试清空
    print('清空...')
    l.clear()
    l.print()

    # 测试长度
    print('链表长度为: ', l.length)

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

程序员必知的算法和数据结构:用这种方法理解链表,更易懂

一个单链表包括一系列节点(Nodes), 每个节点包括对后继节点的引用。通常,链表最后一个节点是null,这样表明链表终止了。

1050
来自专栏烂笔头

Python标准库笔记(2) — re模块

目录[-] re模块提供了一系列功能强大的正则表达式(regular expression)工具,它们允许你快速检查给定字符串是否与给定的模式匹配(matc...

3574
来自专栏积累沉淀

Python快速学习第一天

第一天: Python是一种解释型的、面向对象的、带有动态语义的高级程序设计语言 一、运行Python: 1、 在交互式环境下,直接输入Python进入Pyth...

2085
来自专栏抠抠空间

re模块(正则表达式)

一、什么是正则表达式 正则就是用一些具有特殊含义的符号组合到一起(称为正则表达式)来描述字符或者字符串的方法。或者说:正则就是用来描述一类事物的规则。(在Pyt...

3136
来自专栏desperate633

深入理解javascript中的继承机制(4)多继承寄生式继承借用构造函数借用构造函数并且复制原型以上

我们知道多继承是面向对象的语言中比较纠结的一个问题,有好处也存在缺陷。这方面我们不多讨论。就javascript而言,要实现多继承是比较简单的,因为javasc...

821
来自专栏desperate633

深入理解Java中的final、finally和finalizefinalfinallyfinalize

如果final修饰的是一个基本类型,就表示这个变量被赋予的值是不可变的,即它是个常量;如果final修饰的是一个对象,就表示这个变量被赋予的引用是不可变的,这里...

853
来自专栏calmound

Javascript数组

定义    定义空数组       var arr = new Array();       var arr = [];    定义一个包含1,2,3的数组  ...

3456
来自专栏北京马哥教育

Python变量类型全书

? 糖豆贴心提醒,本文阅读时间6分钟 一、Python 变量类型简介 1、Python中变量的特点: 我们知道,在Python中,变量有如下的特点: (1)...

2497
来自专栏应兆康的专栏

Python 实现单向循环链表

循环链表的概念 1.什么是循环链表   所谓的循环链表就是让单向链表的首尾相连,组成一个环状。 2.循环链表的典型应用   约瑟夫环问题。 3.实现循环链表的重...

4126
来自专栏彭湖湾的编程世界

【数据结构】实现字典API:有序数组和无序链表

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

3285

扫码关注云+社区

领取腾讯云代金券