基于python实现双向链表
作者:旺旺小小超 发布时间:2022-02-17 04:06:44
标签:python,双向链表
在一些面试或者力扣题中都要求用双向链表来实现,下面是基于python的双向链表实现。
一、构建链表节点
class Node:
def __init__(self, key, value):
"""
初始化方法
:param key:
:param value:
"""
self.key = key
self.value = value
self.prev = None
self.next = None
def __str__(self):
val = '{%s: %s}' % (self.key, self.value)
return val
def __repr__(self):
val = '{%s: %s}' % (self.key, self.value)
return val
除了一些节点的基础属性外还有__str__方法用于自定义print(node)的字符串描述(类似Java的toString()),__repr__用于自定义直接调用Node类时的字符串描述
二、实现链表类
具体逻辑主要包括头部添加、尾部添加、头部删除、尾部删除和任意节点的删除,所有对双向链表的操作都是基于这几个方法实现的,具体流程都写在注释中了
class DoubleLinkedList:
def __init__(self, capacity=0xffffffff):
"""
双向链表
:param capacity: 链表容量 初始化为int的最大值2^32-1
:return:
"""
self.capacity = capacity
self.size = 0
self.head = None
self.tail = None
def __add_head(self, node):
"""
向链表头部添加节点
头部节点不存在 新添加节点为头部和尾部节点
头部节点已存在 新添加的节点为新的头部节点
:param node: 要添加的节点
:return: 已添加的节点
"""
# 头部节点为空
if not self.head:
self.head = node
self.tail = node
self.head.next = None
self.tail.prev = None
# 头部节点不为空
else:
node.next = self.head
self.head.prev = node
self.head = node
self.head.prev = None
self.size += 1
return node
def __add_tail(self, node):
"""
向链表尾部添加节点
尾部节点不存在 新添加的节点为头部和尾部节点
尾部节点已存在 新添加的节点为新的尾部节点
:param node: 添加的节点
:return: 已添加的节点
"""
# 尾部节点为空
if not self.tail:
self.tail = node
self.head = node
self.head.next = None
self.tail.prev = None
# 尾部节点不为空
else:
node.prev = self.tail
self.tail.next = node
self.tail = node
self.tail.next = None
self.size += 1
return node
def __remove_head(self):
"""
删除头部节点
头部节点不存在 返回None
头部节点已存在 判断链表节点数量 删除头部节点
:return: 头部节点
"""
# 头部节点不存在
if not self.head:
return None
# 链表至少存在两个节点
head = self.head
if head.next:
head.next.prev = None
self.head = head.next
# 只存在头部节点
else:
self.head = self.tail = None
self.size -= 1
return head
def __remove_tail(self):
"""
删除尾部节点
尾部节点不存在 返回None
尾部节点已存在 判断链表节点数量 删除尾部节点
:return: 尾部节点
"""
# 尾部节点不存在
if not self.tail:
return None
# 链表至少存在两个节点
tail = self.tail
if tail.prev:
tail.prev.next = None
self.tail = tail.prev
# 只存在尾部节点
else:
self.head = self.tail = None
self.size -= 1
return tail
def __remove(self, node):
"""
删除任意节点
被删除的节点不存在 默认删除尾部节点
删除头部节点
删除尾部节点
删除其他节点
:param node: 被删除的节点
:return: 被删除的节点
"""
# 被删除的节点不存在
if not node:
node = self.tail
# 删除的是头部节点
if node == self.head:
self.__remove_head()
# 删除的是尾部节点
elif node == self.tail:
self.__remove_tail()
# 删除的既不是头部也不是尾部节点
else:
node.next.prev = node.prev
node.prev.next = node.next
self.size -= 1
return node
def pop(self):
"""
弹出头部节点
:return: 头部节点
"""
return self.__remove_head()
def append(self, node):
"""
添加尾部节点
:param node: 待追加的节点
:return: 尾部节点
"""
return self.__add_tail(node)
def append_front(self, node):
"""
添加头部节点
:param node: 待添加的节点
:return: 已添加的节点
"""
return self.__add_head(node)
def remove(self, node=None):
"""
删除任意节点
:param node: 待删除的节点
:return: 已删除的节点
"""
return self.__remove(node)
def print(self):
"""
打印当前链表
:return:
"""
node = self.head
line = ''
while node:
line += '%s' % node
node = node.next
if node:
line += '=>'
print(line)
三、测试逻辑
if __name__ == '__main__':
double_linked_list = DoubleLinkedList(10)
nodes = []
# 构建十个节点的双向列表
for i in range(10):
node_item = Node(i, i)
nodes.append(node_item)
double_linked_list.append(nodes[0])
double_linked_list.print()
double_linked_list.append(nodes[1])
double_linked_list.print()
double_linked_list.pop()
double_linked_list.print()
double_linked_list.append_front(nodes[2])
double_linked_list.print()
double_linked_list.append(nodes[3])
double_linked_list.print()
double_linked_list.remove(nodes[3])
double_linked_list.print()
double_linked_list.remove()
double_linked_list.print()
测试结果:
来源:https://blog.csdn.net/wang_xiaowang/article/details/105911411
0
投稿
猜你喜欢
- pygal的安装大家可以参阅:pip和pygal的安装实例教程线图:import pygalline_chart = pygal.Line(
- 一、分析数据源这里的数据源是指html网页?还是Aajx异步。对于爬虫初学者来说,可能不知道怎么判断,这里辰哥也手把手过一遍。提示:以下操作
- '************************************* '检测是否只包含英文和数
- 什么是 Python 中的 Lambda 函数今天我们来学习 Python 中的 lambda 函数,并探讨使用它的优点和局限性Let
- Server对象主要是给编程人员提供一些方便的对象和属性。(1)ScriptTimeout属性:<%Server.ScriptTime
- python提取照片坐标信息的代码如下所示:from PIL import Imagefrom PIL.ExifTags import TA
- 项目整体布局创建并进入项目文件夹:$ mkdir flask-tutorial$ cd flask-tutorial接下来按照 安装简介 设
- 过去有很多网页设计师喜欢将他们的网页效果图用table布局实现成网页,但是这样做会遇到一个比较麻烦的问题就是,后期调试和维护会相当的困难。现
- 具体特征如下: 1、通过模板实现俄文正常。 2、通过后台数据库生成的静态俄文信息,后台显示正常, 前台乱码。 3、英文正常。 和该主题相关的
- Cloudflare 有一项功能挺不错的,就是将页面上所有的邮箱地址都加密起来,防止机器人抓到然后干坏事。这项功能要在后台开启 email
- WMI是Windows系统的一大利器,Python的win32api库提供了对WMI的支持,安装win32api即可使用 WMI。本例通过W
- 本文实例为大家分享了selenium+python京东自动登录及秒杀的代码,供大家参考,具体内容如下运行环境:python 2.7pytho
- 有没有曾经为IE浏览器中长按钮莫名其妙的padding感到困扰?在分析解决方法之前,我们首先来看一下问题所在。在IE中,如果按钮文本比较长,
- 前言要想让手机app自动登录,也就是让app自己操作。所以在脚本中我们需要对app控件进行操作,那么我们需要获取控件的信息。可以使用..\a
- 本文实例讲述了Python面向对象之多态原理与用法。分享给大家供大家参考,具体如下:目标多态面向对象三大特性封装 根据 职责 将 属性 和
- 先废话几句,这第23篇教程一直没有翻译出来,直到今天我看到待审评论里面有这么一条超长的评论,结果一看,居然是这篇教程的翻译稿。
- 如下所示:import pandas as pd from pandas import * import numpy as np data
- 1.用一个栈【python中可以用List】就可以解决,时间和空间复杂度都是O(n)# -*- coding: utf8 -*-# 符号表S
- 引言在这篇文章中,我将介绍如何使用YOLOv5构建一个佩戴安全帽检测和识别系统。这个系统可以实时检测图像上人物是否有未佩戴安全帽,并及时进行
- 这篇文章主要介绍了如何基于Python制作有道翻译小工具,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的