iis服务器助手广告广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > Python >线性结构 数组与链表
  • 669

0
分享到

线性结构 数组与链表

数组线性链表 2023-01-31 08:01:06 669人浏览 独家记忆

Python 官方文档：入门教程 => 点击学习

摘要

线性结构 数组与链表 线性结构 线性数据结构有两端，有时被称为左右，某些情况被称为前后。你也可以称为顶部和底部，名字都不重要。将两个线性数据结构区分开的方法是添加和移除项的方式，特别是添加和移除项的位置。例如一些结构允许从一端添加项，另

线性结构 数组与链表

线性结构

线性数据结构有两端，有时被称为左右，某些情况被称为前后。你也可以称为顶部和底部，名字都不重要。将两个线性数据结构区分开的方法是添加和移除项的方式，特别是添加和移除项的位置。例如一些结构允许从一端添加项，另一些允许从另一端移除项。

数组或列表

数组(Array)是编程界最常见的数据结构，有些编程语言被称作位列表(List)。几乎所有编程语言都原生内置数组类型，只是形式向略有不同，因为数组是最简单的内存数据结构。

数组的定义是：一个存储元素的线性集合(Collection)，元素可以通过索引(Index)来任意存取，索引通常是数字，用来计算元素之间存储位置的偏移量。

链表

数组的缺点：要存储多个元素，数组(或列表)可能是最常见的数据结构。但是数组不总是组织数据的最佳结构。在大多数编程语言中，数组的大小是固定的，所以当数组被填满时，再要加入新的元素会非常困难。并且从数组起点或中间插入或移除元素的成本很高，因为需要将数组中的其他元素向前后平移。

链表(Linked list)中的元素在内存中不是连续存放的。链表是由一组节点(Node)组成的集合，每个节点由元素本身和一个指向下一个元素的引用(也被称作链接或指针)组成。相对于数组，链表的好处在于，添加或移除元素的时候不需要移动其他元素。

链表的种类

单向链表(Singly linked list)：是最基本的链表，每个节点一个引用，指向下一个节点。单向链表的第一个节点称为头节点(head node)，最后一个节点称为尾节点(tail node)，尾节点的引用为空（None），不指向下一个节点。

双向链表(Doubly linked list)和单向链表的区别在于，在链表中的节点引用是双向的，一个指向下一个元素，一个指向上一个元素。

循环链表(Circular linked list)和单向链表类似，节点类型都一样。唯一的区别是 ，链表的尾节点引用指向头节点。

双向循环链表：类似于双向链表，尾节点的后置引用指向头节点，头节点的前置引用指向尾节点。

单向链表的操作

方法 操作
append 向链表尾部添加一个元素
insert 在链表的指定位置插入一个元素
pop 从链表特定位置删除并返回元素
remove 从链表中删除给定的元素
find 返回元素的索引
iter 迭代链表元素
size 获取链表大小
clear 清空链表

python实现单向链表

# python3
class node:
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def append(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1

    def insert(self, index, value):
        if 0 <= index <= self.size:
            node = Node(value)
            current = self.head
            previous = Node(next=current)
            count = 0
            while count < index:
                previous = current
                current = current.next
                count += 1
            previous.next = node
            node.next = current
            if previous.value is None:
                self.head = node
            if node.next is None:
                self.tail = node
            self.size += 1
            return True
        else:
            return False

    def pop(self, index):
        if 0 <= index <= self.size and self.head is not None:
            current = self.head
            previous = Node(next=current)
            count = 0
            while count < index:
                previous = current
                current = current.next
                count += 1
            previous.next = current.next
            if previous.value is None:
                self.head = current.next
            if current.next is None:
                self.tail = previous
            self.size -= 1
            return current.value
        else:
            return None

    def remove(self, item):
        found = False
        current = self.head
        previous = Node(next=current)
        index = 0
        while not found and current is not None:
            if current.value == item:
                found = True
            else:
                previous = current
                current = current.next
            index += 1
        if found:
            previous.next = current.next
            if previous.value is None:
                self.head = current.next
            if current.next is None:
                self.tail = previous
            self.size -= 1
            return index
        else:
            return -1

    def find(self, item):
        current = self.head
        count = 0
        while current is not None:
            if current.value == item:
                return count
            else:
                current = current.next
                count += 1
        return -1
        
    def iter(self):
        current = self.head
        while current is not None:
            yield current.value
            current = current.next

    def size(self):
        return self.size

    def clear(self):
        self.head = None
        self.tail = None
        self.size = 0

    def is_empty(self):
        return self.size == 0
        
    def __len__(self):
        return self.size()

    def __iter__(self):
        iter self.iter()

    def __getitem__(self, index):
        return self.find(index)

    def __contains__(self, item):
        return self.find(item) != -1

javascript实现单向链表

// es6
class Node {
    constructor(value=null, next=null) {
        this.value = value;
        this.next = next;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    append(value) {
        let node = new Node(value);
        if (this.head === null) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = temp;
            this.tail = temp;
        }
        this.size += 1;
    }
    insert(index, value) {
        if (0 <= index <= this.size) {
            let node = new Node(value);
            let current = this.head;
            let previous = new Node(next=current);
            let count = 0;
            while (count < index) {
                previous = current;
                current = current.next;
                count += 1;
            }
            previous.next = node
            node.next = current
            if (previous.value === null) {
                this.head = node;
            }
            if (node.next === null) {
                this.tail = node;
            }
            this.size += 1
            return true;
        } else {
            return false;
        }
    }
    pop(index) {
        if (0 <= index <= self.size && this.head === null) {
            let current = this.head;
            let previous = new Node(next=current);
            let count = 0;
            while (count < index) {
                previous = current;
                current = current.next;
                count += 1;
            }
            previous.next = current.next;
            if (previous.value === null) {
                this.head = current.next;
            }
            if (current.next === null) {
                this.tail = previous;
            }
            this.size -= 1;
            return current.value;
        } else {
            return null;
        }
    }
    remove(item) {
        let found = false;
        let current = this.head;
        let previous = new Node(next=current);
        let index = 0;
        while (! found && current !== null) {
            if (current.value === item) {
                found = true;
            } else {
                previous = current;
                current = current.next;
            }
            index += 1
        }
        if (found) {
            previous.next = current.next;
            if (previous.value === null) {
                this.head = current.next;
            }
            if (current.next === null) {
                this.tail = previous;
            }
            this.size -= 1;
            return index;
        } else {
            return -1;
        }
    }
    find(item) {
        let current = this.head;
        let count = 0;
        while (current !== null) {
            if (current.value === item) {
                return count;
            } else {
                current = current.next;
                count += 1;
            }
        }
        return -1;
    }
    iter() {
        let current = this.head;
        while (current !== null) {
            yield current.value;
            current = current.next;
        }
    }
    size() {
        return this.size;
    }
    clear() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    isEmpty() {
        return this.size === 0;
    }
}
您可能感兴趣的文档:
点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: 线性结构 数组与链表

本文链接: https://www.lsjlt.com/news/192511.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档
去做题
猜你喜欢
  • 线性结构 数组与链表
    线性结构 数组与链表 线性结构 线性数据结构有两端，有时被称为左右，某些情况被称为前后。你也可以称为顶部和底部，名字都不重要。将两个线性数据结构区分开的方法是添加和移除项的方式，特别是添加和移除项的位置。例如一些结构允许从一端添加项，另...
    99+
    2023-01-31
    数组 线性 链表
  • web开发中数据结构线性结构链表是怎样的
    这篇文章给大家介绍web开发中数据结构线性结构链表是怎样的，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。一、前言我们今天要讲解的 链表 不一样，链表是我们数据结构学习的一个重点，也有可...
    99+
    2022-10-19
  • C语言数据结构之线性表的链式存储结构
    1.什么是线性表的链式存储结构 —链表 存储结点：包括元素本身的信息，还有元素之间的关系逻辑的信息 这个结点有：数据域和指针域 一个指针域：指向后继结点， 单链表 二个指针域： 指向...
    99+
    2022-11-12
  • java数据结构基础:单链表与双向链表
    目录单链表：实现思路：代码实现：双向链表：实现思路：代码实现：总结单链表： 每个数据是以节点的形式存在的 每个节点分为数据域和指针域 数据域中保存该节点的数据 指针域中保存指向下一个...
    99+
    2022-11-12
  • 52.【Java 数据结构——线性表】
    线性表 1.什么是线性表2.线性表的定义:3.线性表图解:4.线性表的长度:5.线性表的顺序储存结构：5.1定义:5.2顺序储存结构的插入元素:5.3线性表的顺序结构的删除元素:5.4线性表顺...
    99+
    2023-10-05
    数据结构 算法 链表
  • 如何理解C语言数据结构中线性表的链式存储结构
    如何理解C语言数据结构中线性表的链式存储结构，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。1.什么是线性表的链式存储结构 —链表存储结点：包括元素本身的信息，还有元素之间的关系...
    99+
    2023-06-21
  • 【数据结构-链表-01】反转链表
    💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,...
    99+
    2023-08-30
    算法
  • Python数据结构与算法之链表,无序链表详解
    目录我们首先来构造节点。节点（Node）的类构建完毕后，接下来我们开始构建整个链表（LinkList）的类。那么我们还需要一个方法来判断链表头的指向。接下来我们构建链表节点的添加方法...
    99+
    2022-11-13
  • 数据结构——链表(java)
    文章目录 链表1. 基本介绍1.1 定义1.2 链表分类3.不带头非循环单链表CURD4.不带头非循环双向链表CURD 链表 1. 基本介绍 1.1 定义 链表是一种物理存储结构...
    99+
    2023-10-02
    数据结构 链表 java
  • 数据结构（Java实现）LinkedList与链表（上）
    链表 逻辑结构 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。 ...
    99+
    2023-08-30
    数据结构 java 链表
  • java数据结构基础:线性表
    目录前言需求分析编码add方法getIndex方法pop方法insert方法getAll全部代码总结前言 其实线性表在生活中和栈的结构差不多。昨天总结了一篇单链表，也是线性表的一种。...
    99+
    2022-11-12
  • python数据结构之链表
    '''' 链表的实现，单向链表 ''' '''建立节点''' class jd:     def __init__(self,data):         self.data = data         self.next = None...
    99+
    2023-01-31
    数据结构 链表 python
  • 数据结构——链表（python版）
    一、链表简介 链表是一种在存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现。链表是由一系列的结点组成，结点可以在运行时动态生成。每个结点包含两部分：数据域与指针域。...
    99+
    2023-08-31
    链表 数据结构 python
  • java数据结构中单链表与双向链表的实现方法
    这篇文章主要介绍“java数据结构中单链表与双向链表的实现方法”，在日常操作中，相信很多人在java数据结构中单链表与双向链表的实现方法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”java数据结构中单链表与...
    99+
    2023-06-20
  • 九个动画组图轮播总结全栈数据结构数组链表
    目录一、概念1、栈的定义2、栈顶3、栈底二、接口1、可写接口1）数据入栈2）数据出栈3）清空栈2、只读接口1）获取栈顶数据2）获取栈元素个数3）栈的判空三、栈的顺序表实现1、数据结构...
    99+
    2022-11-12
  • Node.js环境下JavaScript实现单链表与双链表结构
    单链表（LinkedList）的javascript实现 npmjs相关库： complex-list、smart-list、singly-linked-list 编程思路： add方法用于将元素追加...
    99+
    2022-06-04
    链表 结构 环境
  • C语言编程数据结构线性表之顺序表和链表原理分析
    目录线性表的定义和特点线性结构的特点线性表顺序存储顺序表的元素类型定义顺序表的增删查改初始化顺序表扩容顺序表尾插法增加元素头插法任意位置删除任意位置添加线性表的链式存储数据域与指针域...
    99+
    2022-11-12
  • 线性结构 队列与栈
    线性结构 队列与栈 栈 栈(Stack)是一种遵循先进后出(LIFO)原则的有序列表，新添加或待删除的元素都保存在栈的一端，这一端被称作为栈顶，另一端被称作为栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。 栈的操作 方法 操作 ...
    99+
    2023-01-31
    队列 线性 结构
  • Redis数据结构之链表与字典的使用
    今天我们来聊一聊Redis中的链表与字典，具体如下： 链表 关于链表的基础概念其实你在学习Redis之前一定积累了不少，所以本文将默认你已经掌握了链表相关的基础知识，而Redis的链...
    99+
    2022-11-12
  • C语言数据结构与算法之链表(一)
    目录引言链表的相关思考链表结点结构建立链表实现插入操作完整代码引言 在存储一大波数的时候，我们通常使用的是数组，但是数组有时候又会显得不够灵活，比如下面这个例子： 有一串已经排序好的...
    99+
    2022-11-12
软考高级职称资格查询
iis服务器助手广告
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作