数据结构之LinkedList底层实现和原理详解 |
您所在的位置：网站首页 › xbox360s版体感游戏怎么玩 › 数据结构之LinkedList底层实现和原理详解 |
数据结构之LinkedList底层实现和原理详解
|
[[420549]]
前言
日常开发中，集合是我们经常用到的一种数据结构，当然，集合也并不是一种，也没有所谓的最好的集合，只有最适合的; 当然作为高级程序员，我们不仅仅要会用，还要了解其中的原理; 今天我们就来聊聊LinkedList底层实现和原理 一、LinkedList介绍 public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable { //长度 transient int size = 0; //指向头结点 transient Node first; //指向尾结点 transient Node last; } 1、LinkedList概述LinkedList同时实现了List接口和Deque对口，也就是收它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(stack); 这样看来，linkedList简直就是无敌的，当你需要使用栈或者队列时，可以考虑用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类(只是一个接口的名字); 关于栈或队列，现在首选是ArrayDeque，它有着比LinkedList(当作栈或队列使用时)更好的性能; LinkedList的实现方式决定了所有跟下表有关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized)，如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装
继承关系 java.lang.Object java.util.AbstractCollection java.util.AbstractList java.util.AbstractSequentialList java.util.LinkedList实现接口 Serializable, Cloneable, Iterable, Collection, Deque, List, Queue基本属性 transient int size = 0; //LinkedList中存放的元素个数 transient Node first; //头节点 transient Node last; //尾节点 Collection 接口：Collection接口是所有集合类的根节点，Collection表示一种规则，所有实现了Collection接口的类遵循这种规则继承的类与实现的接口 List 接口：List是Collection的子接口，它是一个元素有序(按照插入的顺序维护元素顺序)、可重复、可以为null的集合 AbstractCollection 类：Collection接口的骨架实现类，最小化实现了Collection接口所需要实现的工作量 AbstractList 类：List接口的骨架实现类，最小化实现了List接口所需要实现的工作量 Cloneable 接口：实现了该接口的类可以显示的调用Object.clone()方法，合法的对该类实例进行字段复制，如果没有实现Cloneable接口的实例上调用Obejct.clone()方法，会抛出CloneNotSupportException异常。正常情况下，实现了Cloneable接口的类会以公共方法重写Object.clone() Serializable 接口：实现了该接口标示了类可以被序列化和反序列化，具体的 查询序列化详解 Deque 接口：Deque定义了一个线性Collection，支持在两端插入和删除元素，Deque实际是“double ended queue(双端队列)”的简称，大多数Deque接口的实现都不会限制元素的数量，但是这个队列既支持有容量限制的实现，也支持没有容量限制的实现，比如LinkedList就是有容量限制的实现,其最大的容量为Integer.MAX_VALUE AbstractSequentialList 类：提供了List接口的骨干实现，最大限度地减少了实现受“连续访问”数据存储(如链表)支持的此接口所需的工作，对于随机访问数据(如数组)，应该优先使用 AbstractList，而不是使用AbstractSequentailList类 二、底层源码分析LinkedList是通过双向链表去实现的，既然是链表实现那么它的随机访问效率比ArrayList要低，顺序访问的效率要比较的高。每个节点都有一个前驱(之前前面节点的指针)和一个后继(指向后面节点的指针) 效果如下图：
源码标注如下： public class LinkedListextends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable { transient int size = 0; //LinkedList中存放的元素个数 transient Node first; //头节点 transient Node last; //尾节点 //构造方法，创建一个空的列表 public LinkedList() { } //将一个指定的集合添加到LinkedList中，先完成初始化，在调用添加操作 public LinkedList(Collection |
【本文地址】
今日新闻 |
推荐新闻 |