文档章节

Python线性表——单链表

o
 osc_gu9d45li
发布于 2019/04/05 12:55
字数 1803
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

1. 线性表简介

线性表是一种线性结构,它是由零个或多个数据元素构成的有限序列。线性表的特征是在一个序列中,除了头尾元素,每个元素都有且只有一个直接前驱,有且只有一个直接后继,而序列头元素没有直接前驱,序列尾元素没有直接后继。

数据结构中常见的线性结构有数组、单链表、双链表、循环链表等。线性表中的元素为某种相同的抽象数据类型。可以是C语言的内置类型或结构体,也可以是C++自定义类型。

2. 数组

数组在实际的物理内存上也是连续存储的,数组有上界和下界。C语言中定义一个数组:

数组下标是从0开始的,a[0]对应第一个元素。其中,a[0]称为数组a的下界,a[6]称为数组a的上届。超过这个范围的下标使用数组,将造成数组越界错误。 数组的特点是:数据连续,支持快速随机访问。 数组分为固定数组与动态数组。其中固定数组的大小必须在编译时就能够确认,动态数组允许在运行时申请数组内存。复杂点的数组是多维数组,多维数组实际上也是通过一维数组来实现的。在C语言中,可以通过malloc来分配动态数组,C++使用new。另外,C++的标准模板库提供了动态数组类型vector以及内置有固定数组类型array。

Python中list可以被认为是封装好的数组。

3. 单向链表

单向链表是链表的一种。链表由节点所构成,节点内含一个指向下一个节点的指针,节点依次链接成为链表。因此,链表这种数据结构通常在物理内存上是不连续的。链表的通常含有一个头节点,头节点不存放实际的值,它含有一个指针,指向存放元素的第一个节点。

show me the code

class Node():
    """
    单链表中的节点应该具有两个属性:val 和 next。
    val 是当前节点的值,
    next 是指向下一个节点的指针/引用。
    """

    def __init__(self, value):
        # 存放元素数据
        self.val = value
        # next是下一个节点的标识
        self.next = None

设计链表的实现

您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:valnextval 是当前节点的值,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 个节点。

show me the code

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Author    : Young
@Email     : hyc554@outlook.com
@site      : http://www.cnblogs.com/huang-yc/
@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://www.cnblogs.com/QG-whz/p/5170147.html

https://blog.csdn.net/weixin_39881922/article/details/80470896

https://leetcode-cn.com/explore/learn/card/linked-list/193/singly-linked-list/741/

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
python 数据结构一 之 线性表

python数据结构教程第一课 python的一些实用的数据结构,原理加上实例源码。 目录 一、顺序表的实现 二、链接表的实现 1.单链表 2.带尾指针的单链表 3.循环单链表 4.双链表 5.循环双链表 三、...

osc_nmgdty43
2018/09/04
1
0
用最容易的方式学会单链表(Python实现)

单链表与数组 在本博客中,我们介绍单链表这种数据结构,链表结构为基于数组的序列提供了另一种选择(例如Python列表)。 基于数组的序列也会有如下缺点: 一个动态数组的长度可能超过实际存...

osc_wna7tzts
04/16
4
0
python列表底层实现原理

Python 列表的数据结构是怎么样的? 书上说的是:列表实现可以是数组和链表。 顺序表是怎么回事?顺序表一般是数组。 列表是一个线性的集合,它允许用户在任何位置插入、删除、访问和替换元素...

osc_cesboqi4
2019/08/21
2
0
单链表的python实现

  首先说下线性表,线性表是一种最基本,最简单的数据结构,通俗点讲就是一维的存储数据的结构。   线性表分为顺序表和链接表: 顺序表示指的是用一组地址连续的存储单元依次存储线性表的...

osc_ve0sxjnb
2018/06/13
3
0
Python3数据结构与算法之线性表

在此开始记录数据结构与算法(基于Python的)学习,主要参考视频https://www.bilibili.com/video/av21540971/?p=1 线性表 线性表有两种存储结构:顺序存储结构与链式存储结构。 1 顺序表   ...

osc_r8q2esik
2019/02/27
2
0

没有更多内容

加载失败,请刷新页面

加载更多

平时使用的Lszrz到底是什么协议?说说Xmodem/Ymodem/Zmodem

XMODEM, YMODEM, and ZMODEM 由于平时使用rz/sz较多,r/s好理解,一个send一个receive。但是由不太清楚z是什么意思,故有此文。 sx/rx, sb/rb (b=batch)和sz/rz分别实现了xmodem,ymodem和z...

独钓渔
34分钟前
17
0
真正的强智能时代已经到来。道翰天琼认知智能机器人平台API大脑。

最近,我常说人工智能的寒冬快要来了,提醒业界要做好思想准备,但同时我也说:冬天来了,春天就不会远了…… 2019年6月我写了篇文章《深度学习的问题究竟在哪?》,说到深度学习的一个主要问...

jackli2020
43分钟前
24
0
什么是控制型人格,控制型人格的筛查测试

一、 什么是控制性人格 拥有控制型人格的人,他们会尽力的隐藏自己的意图,但是又会使用很微妙的方式来利用周围人的弱点,进而占取便宜时,使他们能够得到自己想要的东西。这类人的控制欲非常...

蛤蟆丸子
52分钟前
14
0
【Spring】Spring AOP 代理对象生成逻辑源码分析

1. spring aop案例(POJO注入) 1.0 被代理接口 TargetInterface /** * 被代理的接口 * @author Yang ZhiWei */public interface TargetInterface { void show(); String show......

ZeroneLove
今天
36
0
聊聊dubbo-go的gracefulShutdownFilter

序 本文主要研究一下dubbo-go的gracefulShutdownFilter gracefulShutdownFilter dubbo-go-v1.4.2/filter/filter_impl/graceful_shutdown_filter.go type gracefulShutdownFilter struct {......

go4it
今天
30
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部