LinkedList底层结构

LinkedList底层实现了双向链表和双向队列特点可以添加任意元素，包括null,元素可以重复线程不安全，没有实现同步

LinkedList底层操作机制

LinkedList底层维护了一个双向链表LinkedList中维护了两个属性first和last分别指向首结点和尾结点每个结点（Node 对象），里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个结点，最终实现双向链表所以LinkedList的元素的增加和删除，不是通过数组完成的，相对来说效率较高模拟一个简单的双向链表

<code>@SuppressWarnings({ -- -->"all"})

public class Journey {

public static void main(String[] args) {

//模拟一个简单的双向链表

Node life = new Node("life");

Node is = new Node("is");

Node journey = new Node("a journey");

//各个结点相连，形成双向链表life is a journey

life.next = is;

is.next = journey;

journey.pre = is;

is.pre = life;

//让first引用指向jack,其就是双向链表的头结点

Node first = life;

//让last引用指向journey,其就是双向链表的尾结点

Node last = journey;

//演示，从头到尾遍历链表

while(true){

if(first==null){

break;

}

//输出first,

System.out.println(first);

first = first.next;

}

/**

* 输出

* Node name=life

* Node name=is

* Node name=a journey

*/

System.out.println("==========演示链表添加数据==========");

//演示下链表添加数据/对象是多么方便

//要求：在 life 和 is 之间添加个 definitely

//life definitely is a journey

Node definitely = new Node("definitely");

definitely.next = is;

definitely.pre = life;

life.next = definitely;

is.pre = definitely;

//让first指针重新指向头结点life

first = life;

while (true){

if(first==null){

break;

}

System.out.println(first);

first = first.next;

}

}

}

//定义一个Node 类，表示双向链表的一个结点

class Node{

public Object item;

public Node next;

public Node pre;

public Node(Object name){

this.item = name;

}

public String toString(){

return "Node name="+item;

}

}

LinkedList的增删改查

<code>@SuppressWarnings({ -- -->"all"})

public class Journey {

public static void main(String[] args) {

LinkedList list = new LinkedList();

//添加结点，加了0 1 2

for (int i = 0; i <= 2; i++) {

list.add(i);

}

//演示删除结点

System.out.println(list);//[0, 1, 2]

list.remove();//删除了0

//此时默认删除第一个元素0，输出此时的list空间状态

System.out.println(list);//[1, 2]

list.add("kerwin");

System.out.println(list);//[1, 2, kerwin]

list.remove(1);//删除1号索引元素，即2

System.out.println(list);//[1, kerwin]

//修改某个结点

list.set(1,"fun");//修改1索引处的元素为fun

System.out.println(list);//[1, fun]

//得到某个结点对象

list.add("Dopamine");

System.out.println(list.get(2));//Dopamine

System.out.println(list.getFirst());//1

System.out.println(list.getLast());//Dopamine

System.out.println("==================================================");

//实现遍历--迭代器

//因为LinkedList是实现了List的接口的，所以也可以使用迭代器遍历

Iterator iterator = list.iterator();

//要想起来快捷生成的方式哟， itit

while(iterator.hasNext()){ //这里要联想到迭代器的结构哈，先判断有没有下个元素

Object obj = iterator.next();

System.out.println(obj);

}

/**

* 输出

* 1

* fun

* Dopamine

*/

//实现遍历--增强for

for(Object o: list){

System.out.println("els->"+o);

}

/**

* 输出

* els->1

* els->fun

* els->Dopamine

*/

//实现遍历--最normal的for循环

for (int i = 0; i < list.size(); i++) {

System.out.println("normal-For->"+list.get(i));

}

/**

*输出

* normal-For->1

* normal-For->fun

* normal-For->Dopamine

*/

}

}

对应的各个方法的源码剖析

//增方法的源码剖析 add

//深入LinkedList的add方法，可知

//传入一个数进去后，先自动装箱，然后，执行add方法，源码如下：

public boolean add(E e) {

linkLast(e);

return true;

}

//继续深入linkLast方法，可得知其内部具体实现，先了解下Node类的具体内容，再往下看linkLast函数

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;

}

}

void linkLast(E e) {

final Node<E> l = last;//起初last为null

final Node<E> newNode = new Node<>(l, e, null);//创建一个新结点，

//prev为null,element就是此时的元素，next也置为null

last = newNode;//laast指向新建结点

if (l == null)

first = newNode;//如果首结点为空的话，first就指向新节点，使之为首结点

else

l.next = newNode;//否则首结点之后才紧跟新建结点

size++;

modCount++;

}

这时候，你会发现，加了两个元素之后，first指向第一个结点，而last指向第二个结点，这不正合心意？？

<code>//删方法的源码剖析 remove

public E remove() { -- -->

return removeFirst();

}

public E removeFirst() {

final Node<E> f = first;

if (f == null)//如果为空，还删啥？抛异常lou

throw new NoSuchElementException();

return unlinkFirst(f);//不为空，则开始操作

}

private E unlinkFirst(Node<E> f) {

// assert f == first && f != null;

final E element = f.item;

final Node<E> next = f.next;

f.item = null;//将第一个元素置空

f.next = null; // help GC

first = next;//first移动到原先头结点的next,也就是移动到了原先的第二个结点处

if (next == null)//假如原先只有一个结点，那么next==null,

//也就谈不上断掉下一个结点指向自己的prev了

last = null;

else

next.prev = null;//倘若原先的结点不止一个，

//那么就需要把第二个结点指向自己的prev也断开

size--;

modCount++;

return element;

}

ArrayList和LinkedList比较

如何选择ArrayList和LinkedList?

如果我们改查的操作多，选择ArrayList如果我们增删的操作多，选择LinkedList一般来说，程序中，大部分是查询，因此大多数情况下，会选择ArrayList在一个项目中，根据业务灵活选择，也可能这样，有可能一个模块用的是ArrayList,另一个模块使用的是LinkedList