开发者社区> IT辰柒_Java> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

【数据结构与算法】LinkedList与链表(上)

简介: 【数据结构与算法】LinkedList与链表(上)
+关注继续查看

✨hello,进来的小伙伴们,你们好耶!✨

🍊🍊系列专栏:【数据结构与算法】

🌯🌯本篇内容:初始LinkedList与链表,链表的概念,结构,基本实现,详细全面介绍!

🍼🍼作者简介:一名大三在读的科班Java编程小白,我很平凡,学会努力!

🍬🍬码云存放仓库gitee:https://gitee.com/king-zhou-of-java/java-se.git

一、ArrayList的缺陷

通过上篇博客的学习,我们可以通过ArrayList的源码了解到,ArrayList底层使用数组来存储元素。

   public class ArrayList<E> extends AbstractList<E>

       implements List<E>, RandomAccess, Cloneable, java.io.Serializable

   {

    // ...

    // 默认容量是10

     private static final int DEFAULT_CAPACITY = 10;

     //...

     

     // 数组:用来存储元素

     transient Object[] elementData; // non-private to simplify nested class access

     

     // 有效元素个数

     private int size;

     public ArrayList(int initialCapacity) {

       if (initialCapacity > 0) {

         this.elementData = new Object[initialCapacity];

      } else if (initialCapacity == 0) {

         this.elementData = EMPTY_ELEMENTDATA;

      } else {

         throw new IllegalArgumentException("Illegal Capacity: "+

                          initialCapacity);

      }

    }

因为其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低。因此:java集合中又引入了LinkedList,即链表结构。

二、链表

1、链表的概念及结构

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

即我们可以通俗的理解为比如火车的车厢,没有给这些车厢连接起来,他们只是普通的车厢,互相之间没有任何联系,通过任意一节车厢我们无法确定下一节车厢,那么给他们连接起来组成一列火车的车厢,那么就可以是看做一种链表的结构。

image.jpeg

那么在实际的应用中,链表的结构也是多样的。

1.带头或者不带头。

2.单向或双向。

3.循环或非循环。

那么这些组合起来就有8种链表结构,那么我们需要重点掌握的就2种:

无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据

结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

53f6eee4ef7c4b869c75630da60d0aca-1.jpeg

无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表 。

f625816ff49943599cc024302dd9fc22-1.png

2、链表的实现

接下来我将模拟链表的功能实现,借助我们的idea工具来演示!

具体的实现细节都在我的代码注释中标明,大家有不懂的可以评论区或者私信我都可以的!

1.首先我们新建一个包LinkedList。

15086b1851bc46ffb6d2654435be56e0-1.png


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构与算法(3)——链表
链表以及python中链表相关操作
17 0
手撕数据结构与算法-链表
链表也是线性表中的一种,数组是线性表中的顺序结构,而这次说的链表是线性表的链式存储结构,它在内存中是非连续、非顺序性的数据结构,由若干个节点组成。它每个节点中都会存储数据和下一个节点的地址,存储数据的叫做数据域,存储地址的叫做指针域。指针分为前驱指针、后继指针,分别用来记录前一个节点和后一个节点的位置。
10 0
数据结构与算法(3)链表
为什么要讲链表呢?这是因为java中有很多集合类底层都是通过链表来实现的。而且面试的时候,链表的实现是经常考的一个知识点。所以这篇文章的重点在于,如何使用代码去实现这些数据结构。但是这篇文章我不打算直接上来就讲链表,而是先从线性表开始。按照惯例先给出这篇文章的大致脉络吧。 首先,是对数据结构中线性表,做一个回顾。还讲了其两大存储结构,顺序存储结构和链式存储结构。 接下来,重点讲各种链表的介绍,以及常用方法和特点 最后,对java中使用链表的集合类,进行一个介绍。 当然,还有一些常见的面试题。
31 0
数据结构与算法——跳表
前面说到了二分查找,并且它是基于顺序表结构的,即数组,如果直接用于链表,时间复杂度会比较的高,是 O(logn),一般我们不会这样做。那么有没有基于链表的二分查找呢?答案就是今天说到的跳跃链表。
25 0
数据结构与算法——单链表练习
前面的文章说到了一种很基础的数据结构——链表:数据结构与算法——链表,今天就来看看关于单链表的几种常见的操作,技术笔试的时候很大概率能够遇到其中的一些。多练习一下,对我们理解链表有很大的帮助,也能够提升我们的编码能力。 废话不多说,这几个练习题是: • 单链表反转 • 合并两个有序链表 • 检测链表中的环 • 删除链表倒数第 k 个节点 • 找到链表的中间节点
51 0
数据结构与算法-链表(下)
数据结构与算法-链表
52 0
数据结构和算法之链表 | 链表介绍(难度级别:简单)
数据结构和算法之链表 | 链表介绍(难度级别:简单)
116 0
数据结构与算法(三) 线性表之双向链表
 掌握了单链表的结构和实现方法后,再来看双向链表,其实就是在每个节点上添加一个指向其前驱节点的指针,这样就可以实现链表的双向遍历,提高了访问效率。  下面是几个方法的实现: 首先依旧是节点的结构 template struct Node{ ...
830 0
经典博客---《数据结构与算法》
1. http://www.cnblogs.com/JCSU/category/377626.html   2.非常不错的博客。 http://www.nowamagic.net/librarys/veda/detail/2241 微信公众号: 猿人谷 如果您认为阅读这篇博客让您有些收获,不妨点击一下右下角的【推荐】 如果您希望与我交流互动,欢迎关注微信公众号 本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。
597 0
+关注
IT辰柒_Java
攀登者!
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载