Java教程

Linked List类

本文主要是介绍Linked List类,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Java中的LinkedList类实现了List接口和Deque接口,是一种链表类型的数据结构,支持高效的插入和删除操作,同时也实现了Deque接口,使得LinkedList类也具有队列的特性。LinkedList类的底层实现的数据结构是一个双端的链表。
LinkedList类中有一个内部私有类Node,这个类就代表双端链表的节点Node。这个类有三个属性,分别是前驱节点,本节点的值,后继节点。

LinkedList 是以双向链表实现,链表无容量限制(但是双向链表本身需要消耗额外的链表指针空间来操作),其内部主要成员为 first 和 last 两个 Node 节点,在每次修改列表时用来指引当前双向链表的首尾部位,所以 LinkedList 不仅仅实现了 List 接口,还实现了 Deque 双端队列接口(该接口是 Queue 队列的子接口),故 LinkedList 自动具备双端队列的特性,当我们使用下标方式调用列表的 get(index)、set(index, e) 方法时需要遍历链表将指针移动到位进行访问(会判断 index 是否大于链表长度的一半决定是首部遍历还是尾部遍历,访问的复杂度为 O(N/2)),无法像 ArrayList 那样进行随机访问。(如果i>数组大小的一半,会从末尾移起),只有在链表两头的操作(譬如 add()、addFirst()、removeLast() 或用在 iterator() 上的 remove() 操作)才不需要进行遍历寻找定位。

 

欢迎大家批评指正,指出问题,谢谢!

这篇关于Linked List类的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!