字节跳动 整数转换 微服务 memory jaxb vue实例 bootstrap后台管理系统模板 河南普通话考试报名官网 jq选择第一个子元素 oracle查看数据库状态 android富文本框架 bootstrap文件上传样式 oracle数据库版本 git登陆命令 java获取字符串 pythonapi pythoninput python类与对象 python图形界面开发 java新特性 filejava java编程学习 java编程课程 java课程 java文档 java数组删除 java文件重命名 ie模拟器 rendercontrol oxm 战地联盟辅助 millenium 谷歌地球用不了 经典雅黑 小程序游戏源码 r330不能识别墨盒 pr时间轴 透视网格工具怎么取消 s10截屏 超过响应缓冲区限制
当前位置: 首页 > 学习教程  > 编程语言

LinkedList

2020/8/11 20:57:32 文章标签:

#1、linkedList源码解析

(1)、有源码可以看出,linkedList继承了 AbstractSequentialList,实现了List、Deque、Cloneable、java.io.Serializable等接口。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 实现 List 接口,能对它进行队列操作。
LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些骨干性函数。降低了List接口的复杂度。这些接口都是随机访问List的,LinkedList是双向链表;既然它继承于AbstractSequentialList,就相当于已经实现了“get(int index)这些接口”。

(2)、LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList的构造方法是一个空方法,此时指针变量first和last的初始值都为null。

transient Node<E> first;
	transient Node<E> last;
	public LinkedList() { 
	}

(3)链表节点静态类。可以看出这是一个双向链表节点,item是用来存放节点值,next是尾指针指向下一个节点,prev是头指针指向前一个节点。

private static class Node<E> {
	        E item;
	        Node<E> next;
	        Node<E> prev;
	
	        Node(Node<E> prev, E element, Node<E> next) {
	            this.item = element;
	            this.next = next;
	            this.prev = prev;
	        }
	    }

(4)插入数据

public boolean add(E e) {
	   linkLast(e);
	      return true; 
	}
	void linkLast(E e) {
	        final Node<E> l = last;
	        final Node<E> newNode = new Node<>(l, e, null);
	        last = newNode;
	        if (l == null)
	            first = newNode;
	        else
	            l.next = newNode;
	        size++;
	        modCount++;
	    }

初次调用add方法时,如果此时链表没有节点,last指针必定为空的,因此指针l也为空,接着通过new Node<>(l, e, null)创造第一个节点,让指针last、first都指向这个节点。此时整个链表只有一个节点。
  当再次调用add方法时,l指向lsat指向的节点(也就是第一个节点)。再通过new Node<>(l, e, null)创造第二个节点(传入l已经有值了,此时Node里面的prev指针指向了l)。last重新指向第二个节点newNode。因为l不为空,则使l的尾指针next指向newNode,完成两个节点互相关联。后续只要往链表添加数据,就会按此步骤逐个的添加节点完成双向绑定,形成一个双向链表
(5)、总结
LinkedList的底层是一个双向链表结构,在进行查找操作的时候需要花费非常非常多的时间来遍历整个链表(哪怕只遍历一半),这就是LinkedList在查找效率不如ArrayList快的原因。但是由于其链表结构的特殊性,在插入、删除数据的时候,只需要修改链表节点的前后指针就可以完成操作,其的效率远远高于ArrayList。


本文链接: http://www.dtmao.cc/news_show_100444.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?