当前位置: 365bet官网 > 365bet开户 >

链表与LinkedList
作者:admin
发布日期:2019-11-19

       

  它是链式存储的线性表,简称链表。链表由多个链表元素组成,这些元素称为节点。结点之间通过逻辑连接,形成链式存储结构。存储结点的内存单元,可以是连续的也可以是不连续的。逻辑连接与物理存储次序没有关系。

  还是多说说概念上的东西,来说说链表的分类,从内存角度出发:链表可以分为静态链表和动态链表,从链表存储方式的角度出发:链表可以分为单链表,双链表以及循环链表。

  :把线性表的元素放在数组中,不管物理上是不是连续存放的,它们之间的逻辑关系来连接,数组单位存放链表结点,结点的链域指向下一个元素的位置,也就是下一个元素所在的数组单元的下标。既然需要数组来实现,那么数组的长度是不能预支的。

  :克服了静态链表的缺点。它动态地为节点分配存储单元。当有节点插入时,系统动态地为结点分配空间。在结点删除时,应该及时释放相应存储单元,以防止内存泄露。

  循环链表由单链表演化而来。单链表的最后一个结点的链域指向NULL,而循环链表的建立,不要专门的头结点,让最后一个结点的链域指向链表结点。它与单链表的区别:

  区别一:链表的建立。单链表需要创建一个头结点,专门存放第一个结点的地址。单链表的链域指向NULL。而循环链表的建立,不要专门的头结点,让最后一个结点的链域指向链表的头结点。

  由于我们SIngleLinkedList类中维护了一个指向FirstNode的引用,所以在表头插入节点是很容易的。

  双向链表相比与单链表的优势在于它同时支持高效的正向及反向遍历,并且可以方便的在链表尾部删除结点(单链表可以方便的在尾部插入结点,但不支持高效的表尾删除操作)。

  由于其链式存储的特性,链表不具备良好的空间局部性,也就是说,链表是一种缓存不友好的数据结构。

  java 中LinkedList中的源码中添加删除方法如我在上面写的双链表中的添加删除方法基本一致。

  LinkedList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了Cloneable接口,能被克隆。

上一篇:年轻的我们在焦虑什么?
下一篇:没有了