一点一点看JDK源码(六)java.util.LinkedList前篇之链表概要

时间:2024-01-03 08:35:32

一点一点看JDK源码(六)java.util.LinkedList前篇之链表概要

liuyuhang原创,未经允许禁止转载

本文举例使用的是JDK8的API

目录:一点一点看JDK源码(〇)

1.什么是链表 

  链表是一种常见的数据结构,属于一种线性表。

  虽说链表是线性表,但是其储存的方式并非是线性的,而是节点(Node)方式存储的。

  每一个节点都含有一个指针,指向下一个节点。

  同时每一个节点都存有自身的数据信息。

  

  链表有点像衣服的拉链,是一个扣一个的,每两个之间都有一个间隔,要想获取某个位置的数据,

  必须逐个获取下一个节点。

  由此,链表的数据添加,默认是添加在该链的末尾的,并不需要获得该链表的所有数据,不需要知道

  链表的长度,也不需要获取链表的全部索引之类的东西。

  因此链表中的数据创建和尾插入效率是极高的,又因为没有一个获取全部索引的方式,因此在链表

  中要查询某些内容,必须一个一个寻找,难以获得某个位置的信息,查询较慢

  虽然说链表是一环扣一环的,但是首节点可以获得次节点信息,依次递归能够获得整个链表的所有信息。

  所以,实际上链表是一种递归结构,首节点实际上存有所有节点的信息了。

  不放图了,自行百度或百科!!

2.链表的构成要素

  根据链表的定义模式,链表的构成要素的本质,是节点(Node)的设计。对于链表的所有特性,都是基于

  Node本身或对Node的操作而形成的。

  Node的构成模式简单说有几种:

    2.1.Node含有数据变量,下一个节点的指针;

    2.2.Node含有数据变量,下一个节点的指针,上一个节点的指针;

    2.3.Node含有数据变量,下一个节点的指针,上一个节点的指针;最后一个节点的指针指向首节点;

    2.4.Node含有数据变量,下一个节点的指针,上一个节点的指针;自身唯一的序号(inde)或索引(hash)

  以上列举的四种方式中,特性是有所变化的。

    2.1.所指本质上是一个单向链表

    2.2.所指本质上是一个双向链表

    2.3.所指本质上是一个环形链表(首尾相接的噬身之蛇的感觉),可以是自身的结构,可以是插入数据时构成。

    2.4.所指本质上是一个降低创建效率,提高查询效率的链表数组,或链表hash

  同时,根据链表的指针定义方式,指针数量,指针标准的不同,可以有诸多的性质。

  如线性链表,非线性链表。

  树形链表,图性链表。

  单向链表,双向链表,环形链表。

3.链表的操作构成

  链表虽然是一种数据结构,本质上也是容器,作为容器,必定有需要一般容器性操作。如:

    创建,新增,插入,删除,修改,查询,清空,转换,排序,遍历等基础操作。

  又因为链表的自身特性,可以有一些特性操作。如:

    获取首元素,获取尾元素。

    获取上一个元素,获取下一个元素。

    弹出首元素,弹出尾元素。

    同时也可以用一些自定义的方式来获取链表元素,如节点分组获取,如跳跃式获取等,看脑洞有多大了!

4.java的链表实现java.util.LinkedList

  下面列举一些java中LinkedList的一些特性。

  • LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
  • LinkedList 实现 List 接口,能对它进行队列操作。
  • LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。
  • LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
  • LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
  • LinkedList 是非同步的。

关于java中LinkedList的设计,下篇在更!

自己手写了个链表,代码比较少,可以看下

算法是什么(二)手写个链表(java)

以上!