`
wwt_cxy001
  • 浏览: 9913 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

程序员必须知道的数据结构:线性表与链表

阅读更多

既然我们这一节要说的是线性表与链表的内容,那么肯定要对数据结构的概念有一个认识。首先,数据结构一般分为逻辑结构、物理结构,逻辑结构指的是数据对象元素之间的相互关系,物理结构一般指的是数据的存储结构。逻辑结构主要包括集合结构、线性结构、树形结构、图形结构,物理结构主要有链式存储和线性存储。在数据结构的分析过程中,逻辑结构和物理结构是一种相辅相成的关系。
在这里插入图片描述

线性表的数据存储位置都是独立的、并且一个位置紧跟着下一个位置,在第 0 个位置上存储的数据是 a1、第一个位置上是 a2、以此类推,直到最后一个数据 an。假如说,要删除其中的一个数据 a2、那么紧接着 a3 就会移动到原来 a2 的位置、a4 就会移动到 a3 的位置,以至于最后 a2 之后的每一个数据都要向前移动一位,这也就使得线性存储的数据在删除的过程中效率会变得比较低。反之,线性存储结构存储数据时都是顺序存储的,没有指针对位置的指引操作,它的查询速度是相对比较快的。
在这里插入图片描述

和线性存储结构不同的是,链式存储结构可以在本身的数量中附加变量、利用附加变量指向前一个或者后一个数据,在进行插入、删除操作时只要改变数据的附加变量的指向就可以实现而不用改变前后数据的存储地址。比如:如果同样是删除 a2 数据的情况,在删除 a2 数据后 a1 的向后附加变量就会指向 a3、a3 的向前附加变量就会指向 a1,这样一来并没有改变 a2 数据以后的数据位置,只是改变了 a1、a3 的附加变量的数据位置指向。

在 Java 语言中,比较明显的线性表、链式表分别是 ArrayList、LinkedList,研究过 JDK 源码应该知道,这两种表分别都有的各自的添加、删除、查询方法,其两种表在实现这三种方法时也是截然不同的。下面我们分别拿出 ArrayList、LinkedList 的 add() 方法进行比较一下。注意:这里实例用的是 JDK1.8 源码展示。

// ArrayList 实现 add() 方法
publicbooleanadd(E e){
   
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}
// add() 方法没有指定添加的数据对象的位置
// 实现也比较简单,直接将数据对象赋值到数组中
// LinkedList 实现 add() 方法
publicvoidadd(int index, E element){
   
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
}
voidlinkBefore(E e, Node<E> succ){
   
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

本节就说到这里,以免大家视觉疲劳、源码部分有兴趣的猿童鞋可以自己深入研究。下一节我们看一下栈与队列的数据结构,记得关注后续更新、哈哈!
更多精彩关注微信公众号【老王说编程】>>>
在这里插入图片描述

分享到:
评论

相关推荐

    数据结构:栈(包含线性表)

    在这个主题中,我们将深入探讨一种特殊的数据结构——栈(Stack),以及它与线性表的关系。栈是一种后进先出(Last In, First Out,简称LIFO)的数据结构,这意味着最后插入的元素最先被移除。栈在许多算法和程序...

    线性表,链表,相关操作,含注解

    线性表和链表是数据结构中的基础概念,它们在计算机科学中扮演着至关重要的角色。线性表是一种逻辑上顺序存储的数据结构,其中的元素按照特定顺序排列,可以是顺序表(数组实现)或链表(链式结构实现)。链表则是...

    数据结构四次实验(二叉树,线性表,链表,综合实验)

    在本实验中,我们将深入探讨数据结构的基本概念,特别是二叉树、线性表和链表,以及如何通过编程实现这些数据结构的核心操作。实验的主要目标是熟练掌握这些数据结构的特性,理解它们的工作原理,并能运用到实际问题...

    数据结构实战--线性表的单链表实现

    总的来说,这个实战项目提供了对单链表这一基础数据结构的深入理解和实践经验,有助于提升程序员在数据结构和算法方面的技能。通过动手实践,学习者可以更好地理解数据结构的内在逻辑,这对于编写高效的代码和解决...

    数据结构之线性表教程3.zip

    线性表作为数据结构的一种基础类型,是理解和掌握其他复杂数据结构的基础。在这个“数据结构之线性表教程3.zip”压缩包中,很可能是对线性表的深入讲解和实践应用的资源集合。 线性表是一种一维数组结构,其中的...

    数据结构课程设计-线性表及应用.doc

    数据结构课程设计-线性表及应用 本资源的主要内容是关于线性表的基本操作和实现,包括单链表的建立、打印、查找、插入、删除等操作。下面是根据文件内容生成的知识点: 1. 线性表的定义:线性表是一种基本的数据...

    数据结构实验线性表及其应用.pdf

    数据结构是计算机科学中的核心概念,它涉及到如何高效地组织和管理数据,以便于执行各种操作,如查找、插入和删除。...同时,理解这些基本数据结构的内部工作原理和操作复杂度,是成为一名优秀的程序员的基础。

    数据结构-线性表、栈、队列

    JWArray和JWList库的实现为开发者提供了便利,它们封装了底层的内存管理和数据操作,使得程序员能够更加专注于业务逻辑,而无需关心数据结构的具体实现细节。这样的库在实际开发中非常有价值,可以提高代码的可读性...

    数据结构--线性表操作(C源代码)

    线性表是数据结构中最基础的一种,它由有限个相同类型元素构成的有序序列。本资源提供了线性表操作的C语言实现,包括源代码和可执行文件,以及一个简单的说明文档。 1. **线性表**: 线性表是由n(n≥0)个相同类型...

    数据结构中线性表的应用,约瑟夫环算法。便于数据结构的学习.zip

    线性表是数据结构的基础,它是由n(n≥0)个相同类型元素构成的有限序列,这些元素在逻辑上是连续的。线性表在实际应用中具有广泛的用途,如数组、链表、队列和栈等都是线性表的特例。本资料主要探讨了线性表在数据...

    《数据结构:C语言版》(严蔚敏)_datastructure_严蔚敏PDF_yanweimin_

    该书涵盖了线性表、栈、队列、链表、树、图、排序与查找等主要的数据结构类型。线性表是最基本的数据结构,包括顺序表和链表两种形式,它们在数组和指针的操作中得到体现。栈和队列是两种特殊的线性结构,栈是后进先...

    用链表实现线性表的各种操作(C语言)

    线性表是数据结构中最基础的一种结构,它是由n(n&gt;=0)个相同类型元素构成的有限序列。在计算机科学中,链表是实现线性表的一种常见方式,尤其在C语言中,由于没有内置的动态数组,链表成为了处理动态数据集合的重要...

    华科计算机数据结构上机实验

    华科计算机数据结构上机实验主要涵盖了两个重要的主题:线性表和链表的操作,以及二叉树的操作。这些知识点在计算机编程和算法设计中都有着广泛的应用。 1. **线性表**: 线性表是最基本的数据结构,它是由n(n≥0...

    程序员数据结构笔记

    在程序员数据结构的学习中,以下几个关键知识点不容忽视: 1. **数据结构的基本概念**:数据结构指的是数据的组织方式,它定义了数据之间的关系以及操作这些数据的方法。在学习数据结构时,我们需要理解对象的定义...

    程序员数据结构笔记 知识 能力 过程

    程序员在面对纷繁复杂的编程挑战时,数据结构的知识和能力是他们手中最锋利的武器。数据结构不仅是计算机科学的基石,更是程序员高效编程的保障。在深入理解数据结构的过程中,程序员需要关注知识的掌握、能力的提升...

    数据结构:第一章 绪论.ppt

    数据结构是计算机科学中至关重要的一个领域,它探讨了如何有效地组织和操作数据。在“数据结构:第一章 绪论.ppt...在实际编程中,数据结构的选择直接影响程序的性能和可维护性,因此是每位程序员必须掌握的核心技能。

    数据结构-对应严蔚敏-吴伟民编著的数据结构, 这个是用的链表实现的线性表(仅包含 含有头结点的单链表)

    在这个压缩包中,我们关注的是“线性表”的实现,特别是使用链表来构建这一基础数据结构。 线性表是一种抽象的数据类型,它由n(n≥0)个相同类型的元素按特定顺序排列组成。这些元素可以是数字、字符串、对象等。...

Global site tag (gtag.js) - Google Analytics