Python线性表种的单链表详解
作者:瑞士卷心菜??????? 发布时间:2022-03-02 07:36:58
1. 线性表简介
线性表是一种线性结构,它是由零个或多个数据元素构成的有限序列。线性表的特征是在一个序列中,除了头尾元素,每个元素都有且只有一个直接前驱,有且只有一个直接后继,而序列头元素没有直接前驱,序列尾元素没有直接后继。
数据结构中常见的线性结构有数组、单链表、双链表、循环链表等。线性表中的元素为某种相同的抽象数据类型。可以是C语言的内置类型或结构体,也可以是C++自定义类型。
2. 数组
数组在实际的物理内存上也是连续存储的,数组有上界和下界。C语言中定义一个数组:
数组下标是从0开始的,a[0]对应第一个元素。其中,a[0]称为数组a的下界,a[6]称为数组a的上届。超过这个范围的下标使用数组,将造成数组越界错误。
数组的特点是:数据连续,支持快速随机访问。
数组分为固定数组与动态数组。其中固定数组的大小必须在编译时就能够确认,动态数组允许在运行时申请数组内存。复杂点的数组是多维数组,多维数组实际上也是通过一维数组来实现的。在C语言中,可以通过malloc来分配动态数组,C++使用new。另外,C++的标准模板库提供了动态数组类型vector以及内置有固定数组类型array。
Python中list可以被认为是封装好的数组。
3. 单向链表
单向链表是链表的一种。链表由节点所构成,节点内含一个指向下一个节点的指针,节点依次链接成为链表。因此,链表这种数据结构通常在物理内存上是不连续的。链表的通常含有一个头节点,头节点不存放实际的值,它含有一个指针,指向存放元素的第一个节点。
class Node():
"""
单链表中的节点应该具有两个属性:val 和 next。
val 是当前节点的值,
next 是指向下一个节点的指针/引用。
"""
def __init__(self, value):
# 存放元素数据
self.val = value
# next是下一个节点的标识
self.next = None
设计链表的实现
您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val
和 next
。val
是当前节点的值,next
是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev
以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能:
get(index):获取链表中第
index
个节点的值。如果索引无效,则返回-1
。addAtHead(val):在链表的第一个元素之前添加一个值为
val
的节点。插入后,新节点将成为链表的第一个节点。
addAtTail(val):将值为
val
的节点追加到链表的最后一个元素。addAtIndex(index,val):在链表中的第
index
个节点之前添加值为val
的节点。如果index
等于链表的长度,则该节点将附加到链表的末尾。如果index
大于链表长度,则不会插入节点。deleteAtIndex(index):如果索引
index
有效,则删除链表中的第index
个节点。
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Author : Young
@File : linked_list2.py
@version : 1.0
@Time : 2019/4/5 11:06
Description about this file:
"""
class Node():
"""
单链表中的节点应该具有两个属性:val 和 next。
val 是当前节点的值,
next 是指向下一个节点的指针/引用。
"""
def __init__(self, value):
# 存放元素数据
self.val = value
# next是下一个节点的标识
self.next = None
class SingleLinkList():
def __init__(self, node=None):
# 头节点定义为私有变量
self._head = node
def is_empty(self):
# 判断链表是否为空
if self._head is None:
return True
else:
return False
def get(self, index: int) -> int:
"""
获取链表中第 index 个节点的值。如果索引无效,则返回-1
:param index: 索引值
:return:
"""
if self._head is None:
return -1
cur = self._head
for i in range(index):
if cur.next is None:
return -1
cur = cur.next
return cur.val
def length(self):
"""
cur游标,用来移动遍历节点
count用来计数
:return: 返回链表的长度
"""
cur = self._head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count
def travel(self):
"""
遍历整个链表
:return:
"""
cur = self._head
while cur is not None:
print(cur.elem, end=' ')
cur = cur.next
def add_at_head(self, val: int) -> None:
"""
在头部添加一个节点
:param val:
:return: None
"""
# 先创建一个保存item值的节点
node = Node(val)
# 判断链表是否为空
if self._head is None:
self._head = node
else:
# 将新节点的链接域next指向头节点,即_head指向的位置
node.next = self._head
# 将链表的头_head指向新节点
self._head = node
def add_at_tail(self, val: int) -> None or int:
"""
在尾部添加一个节点
:param item:
:return:
"""
node = Node(val)
# 若链表为空,直接将该节点作为链表的第一个元素
if self._head is None:
self._head = node
else:
cur = self._head
while cur.next is not None:
cur = cur.next
cur.next = node
def add_at_index(self, index: int, val: int) -> None:
"""
在指定位置pos添加节点
pos从0开始
:param index:
:param val:
:return:
"""
# 若指定位置pos为第一个元素之前,则执行头部插入
if index <= 0:
self.add_at_head(val)
# 若指定位置超过链表尾部,则执行尾部插入
elif index >= self.length():
self.add_at_tail(val)
# 找到指定位置
else:
# pre用来指向指定位置pos的前一个位置pos-1,初始从头节点开始移动到指定位置
pre = self._head
count = 0
node = Node(val)
# 在目标节点的前一位停下
while count < (index - 1):
count += 1
pre = pre.next
# 先将新节点node的next指向插入位置的节点
node.next = pre.next
# 将插入位置的前一个节点的next指向新节点
pre.next = node
def delete_at_index(self, index: int) -> None or int:
"""
如果索引 index 有效,则删除链表中的第 index 个节点。
:param index: 对应的索引值
:return: -1表示为异常
"""
pre = None
cur = self._head
if index is 0:
self._head = None
for i in range(index):
if cur.next is None:
# raise IndexError("越界")
return -1
pre = cur
cur = pre.next
else:
pre.next = cur.next
def search(self, val: int) -> True or False:
"""
查找节点是否存在
:param val: 节点的val值
:return:
"""
cur = self._head
while cur is not None:
if cur.val == val:
return True
else:
cur = cur.next
return False
if __name__ == '__main__':
obj = SingleLinkList()
obj.add_at_head(1)
obj.add_at_tail(3)
obj.add_at_index(1, 2)
obj.travel()
obj.delete_at_index(1)
obj.travel()
链表与顺序表的对比
链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活。
链表与顺序表的各种操作复杂度如下所示:
操作 | 链表 | 顺序表 |
访问元素 | O(n) | O(1) |
在头部插入/删除 | O(1) | O(n) |
在尾部插入/删除 | O(n) | O(1) |
在中间插入/删除 | O(n) | O(n) |
来源:https://blog.51cto.com/u_15452495/5583977
猜你喜欢
- 函数是一种仅在调用时运行的代码块。可以将数据(称为参数)传递到函数中。函数可以把数据作为结果返回。创建函数在 Python 中,使用 def
- 1、需求当工作在UNIX Shell下时,我们想使用常见的通配符模式(即:.py,Dat[0-9].csv等)来对文本做匹配。2、解决方案f
- 一个不错的二级联动下拉菜单源码,您一定会用得到的。运行代码:<html><head><title>Lis
- 相信大家在日常学习或者是阅读英文文章的过程中,难免会出现几个不认识的单词,或者想快速翻译某段英文的意思。今天,利用Python爬虫等知识,教
- 首先获取ip:<% userip=Request.ServerVariables(&qu
- 使用一个遵循buffer protocol的对象就可以和numpy交互了.这个buffer_protocol要有哪些东西呢? 要有如下接口:
- 设置部分:首先网页登录QQ邮箱设置一些待会儿会用到的参数:首先开启POP3/SMTP和IMAP/SMTP服务,然后生成授权码,然后复制到代码
- 介绍本文将介绍基于OpenCV实现视频的循环播放。有以下三个步骤:首先设置一个frame的设置参数frame_counter,值为0在读帧时
- 打包下载Pain.php <?php class Pain { public $var=array(); public $tpl=ar
- 本文实例讲述了Flask框架模板渲染操作。分享给大家供大家参考,具体如下:from flask import render_template
- 首先,这片文章纯粹是我的个人经验之谈,适用于我常见的环境及项目中。个人建议,数据库字符集尽量使用utf8(HTML页面对应的是utf-8),
- 在某些编程语言中,例如 C/C++、C#、PHP、Java、JavaScript 等等,do-while 是一种基本的循环结构。它的核心语义
- 上次介绍了Access 导入 MSSQL 2000/2005 数据库工具,不过,在使用这个工具时还是有一些地方需要注意的,我把整个导入过程记
- 微信小程序作为一种轻量级的应用形式,在移动互联网领域取得了极大的成功。作为 Python 开发者,如何在微信小程序的开发中发挥 Python
- 一、什么是进程进程是执行中的程序,是资源分配的最小单位:操作系统以进程为单位分配存储空间,进程拥有独立地址空间、内存、数据栈等操作系统管理所
- 在网页中,我们经常需要引用大量的javascript和css文件,在加上许多javascript库都包含debug版和经过压缩的releas
- ORM 江湖曾几何时,程序员因为惧怕SQL而在开发的时候小心翼翼的写着sql,心中总是少不了恐慌,万一不小心sql语句出错,搞坏了数据库怎么
- 什么是迭代(iteration)呢?给定一个list或者tuple,通过for循环来遍历这个list或者tuple、这种遍历就是迭代(ite
- Unsafe code是一种绕过go类型安全和内存安全检查的Go代码。大多数情况,unsafe code是和指针相关的。但是要记住使用uns
- 在计算机普及的现代设计领域,文字的设计的工作很大一部分由计算机代替人脑完成了(很多平面设计软件中都有制作艺术汉字的引导,以及提供了数十上百种