学习啦 > 知识大全 > 知识百科 > 百科知识 > java什么是链表

java什么是链表

时间: 欧东艳656 分享

java什么是链表

学习啦在线学习网   链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

  链表(Chain本文所说链表均为单向链表,以下均简称单向链表)实际上是由节点(Node)组成的,一个链表拥有不定数量的节点。而向外暴露的只有一个头节点(Head),我们对链表的所有操作,都是直接或者间接地通过其头节点来进行的。

  节点(Node)是由一个需要储存的对象及对下一个节点的引用组成的。也就是说,节点拥有两个成员:储存的对象、对下一个节点的引用。

学习啦在线学习网   这样说可能大家不是很明白,我贴一张图大家可能更容易理解。

  那么大家可能清除了,为什么说有了头节点就可以操作所有节点。因为有着不断的引用嘛!

  那么在链表里的属性大概就只有两个了:头节点和节点数量。当然,根据需要,我们通常需要更多的属性。

学习啦在线学习网   简单的链表可以写为下面的样子:

  1 package myChain;

  2

  3 /**

  4 * (单向)链表

  5 *

  6 * @author Johness

  7 */

学习啦在线学习网   8 public class PersonChain {

  9 private PersonChainNode head; // 头节点

学习啦在线学习网   10 private int size; // 链表的实体(即节点的数量)

学习啦在线学习网   11 private int modCount; // 链表被操作的次数(备用)

  12

  13 /**

学习啦在线学习网   14 * 获得链表中节点数量

  15 *

学习啦在线学习网   16 * @return 链表中节点数

  17 */

学习啦在线学习网   18 public int getSize() {

  19 return this.size;

  20 }

  21

  22 /**

  23 * 添加节点的一般方法

  24 *

学习啦在线学习网   25 * @param p

  26 * 添加到链表节点的对象 由于实现细节,作为唯一标识,同一个编号的Person只能添加一次

  27 */

  28 public void addNode(Person p) {

  29 if (!contains(p.personNo)) { // 如果链表中没有该对象,则准备添加

学习啦在线学习网   30 if (head != null) { // 如果有头节点,则添加新节点作为头节点

学习啦在线学习网   31 head = new PersonChainNode((myChain.Person) p, head);

  32 size++;

  33 modCount++;

  34 } else { // 如果没有头节点,则添加对象作为头节点

学习啦在线学习网   35 head = new PersonChainNode((myChain.Person) p, null);

学习啦在线学习网   36 size++;

  37 modCount++;

  38 }

  39 }

  40 }

  41 }

java什么是链表

  以上的代码就是一般链表的骨架了。拥有两个重要属性。

245839