底层是由节点(静态内部类)来进行存储元素的，底层内存不连续，不需要扩容增删元素效率较高，查询元素效率较低
LinkedList类中有一个内部私有类Node，这个类就代表双端链表的节点Node。这个类有三个属性，分别是前驱节点，本节点的值，后继结点。
源码中的实现是这样的。
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; } }
注意这个节点的初始化方法，给定三个参数，分别前驱节点，本节点的值，后继结点。这个方法将在LinkedList的实现中多次调用。
下图是LinkedList内部结构的可视化，能够帮我们更好的理解LinkedList内部的结构。
1 public class A { 2 3 public static void main(String[] args) { 4 ListLinked l=new ListLinked(); 5 l.add("hsdu"); 6 l.add("u"); 7 l.add("du"); 8 System.out.println(l); 9 10 } 11 12 } 13 class ListLinked 14 { 15 //元素个数/节点数 16 int size=0; 17 //头节点 -----表示第一个节点 18 Node first; 19 //尾部点------表示最后一个节点 20 Node last; 21 //节点-------内部类 22 class Node 23 { 24 //存储的元素 25 String item; 26 //上一个节点 27 Node prev; 28 //下一个节点 29 Node next; 30 //有参构造 31 public Node(String item,Node prev,Node next) //元素赋值 32 { 33 this.item=item; 34 this.prev=prev; 35 this.next=next; 36 } 37 } 38 //添加 39 public void add(String str) 40 { 41 //创建一个新节点 42 Node node=new Node(str, null, null); 43 //判断添加元素的位置 44 if(size==0)//表明添加的是第一个节点 45 { 46 //头节点指向新节点 47 this.first=node; 48 //尾节点指向新节点 49 this.last=node; 50 } 51 else //尾部节点 52 { 53 //原尾节点的last指向新节点 54 this.last.next=node; 55 //新节点的上一个指向原尾节点 56 node.prev=this.last; 57 //尾节点指向新节点 58 this.last=node; 59 } 60 61 size++; 62 } 63 //插入 64 public void insert(int index,String str) 65 { 66 //判断下边是否越界 67 if(index<0||index>size) 68 { 69 throw new IllegalArgumentException("index+"+index); 70 } 71 72 73 //判断插入节点的位置 74 //插入的节点位置是头节点且size为0 75 //在尾部进行添加节点 76 if(index==size) {//尾部添加 77 add(str); 78 //结束方法保证size不会添加两次 79 return; 80 } 81 //新节点 82 Node node=new Node(str, null, null); 83 //判断插入头节点但是已经有了头节点 84 //size 不为0 85 if(index==0) 86 { 87 //原头节点的上一个指向新节点 88 this.first.prev=node; 89 //新节点的下一个指向原头节点 90 node.next=this.first; 91 //头节点指向新节点 92 this.first=node; 93 } 94 else { //表明在中间插入 95 //获取指定下标的节点 96 Node no=this.first; 97 for(int i=0;i<index;i++) 98 { 99 no=no.next; 100 } 101 //最后会找到第index的节点no 102 //插入在no之前 103 no.prev.next=node; //no前面的节点的next指向新节点 104 node.prev=no; //新节点的next指向no 105 no.prev=node; //no的prev指向新节点 106 node.next=no; //新节点的next指向no 107 } 108 size++; 109 } 110 //下标越界问题 111 public void out(int index) 112 { 113 //判断下边是否越界 114 if(index<0||index>=size) 115 { 116 throw new IllegalArgumentException("index+"+index); 117 } 118 119 } 120 //根据下标找到节点 121 public Node getNode(int index) 122 { 123 Node n=this.first; 124 for(int i=0;i<index;i++) 125 { 126 n=n.next; 127 } 128 return n; 129 } 130 //删除----根据下标 131 public void remove(int index) 132 { 133 //下标越界问题 134 out(index); 135 //判断删除节点的位置 136 if(index==0) 137 { 138 //头节点指向原头节点的下一个节点 139 this.first=this.first.next; 140 //原头节点的下一个节点的上一个为null 141 this.first.prev=null; 142 } 143 else if(index==size-1) {//尾部节点删除 144 //原尾节点的上一个节点的下一个为null 145 this.last.prev.next=null; 146 //尾节点指向原尾节点的上一个节点 147 this.last=this.last.prev; 148 } 149 else {//删除中间节点 150 //根据下标找到指定节点 151 Node n= getNode(index); 152 //n节点的上一个节点的下一个指向no节点的下一个节点 153 n.prev.next=n.next; 154 n.next.prev=n.prev; 155 156 } 157 size--; 158 } 159 //根据指定元素进行删除 160 public void remove(String str) 161 { 162 int i=indexOf(str); 163 if(i!=-1) 164 { 165 remove(i); 166 } 167 } 168 //找到元素第一次出现的坐标 169 public int indexOf(String str) { 170 //遍历节点找出满足要求的节点 171 Node no=this.first; 172 for(int i=0;i<size;i++) 173 { 174 //把每个节点的元素和参数作比较 175 if(str==no.item||str!=null&&str.equals(no.item)) 176 { 177 return i; 178 179 } 180 no=no.next; 181 } 182 return -1; 183 184 } 185 @Override 186 public String toString() { 187 Node no=this.first; 188 //创建对象 189 StringBuilder sb=new StringBuilder("["); 190 //拼接节点里的元素 191 for(int i=0;i<size;i++) 192 { 193 sb.append(no.item+", "); 194 no=no.next; 195 } 196 String s=sb.toString(); 197 if(size>0) 198 { 199 s=s.substring(0, s.length()-2); 200 } 201 return s+"]"; 202 } 203 }
原文：https://www.cnblogs.com/xuwangqi/p/11214116.html
