java实现linklist_Java中LinkedList实现原理
数据结构
LinkedList是基于链表结构实现，所以在LinkedList类中包含了first和last两个指针(类型为Node)。Node中包含了对prev节点、next节点的引⽤，这样就构成了双向的链表。
1  　private static class Node{
2 E item;
3 Nodenext;
4 Nodeprev;5
6 Node(Node prev, E element, Nodenext) {
7 this.item =element;
=next;
9 this.prev =prev;10 }11 }
存储
1.add(E e)⽅法
该⽅法⾸先声明⼀个新Node l，将链表的最后⼀个Node赋值给l，然后将新的Node即newNode覆盖last(或者说让last指向newNode)，最后将l的next指针指向newNode。
1  　//Appends the specified element to the end of this list.
2 public booleanadd(E e) {
3 linkLast(e);
4 return true;
5 }
6 /**
7 * Links e as last element.8 */
9 voidlinkLast(E e) {10 final Node l =last;11 final Node newNode = new Node<>(l, e, null);12 last =newNode;13 if (l ==
null)14 first =newNode;15 else
=newNode;17 size++;18 modCount++;19 }
2.add(int index, E element)
该⽅法是在指定的index位置插⼊新元素。如果index位置正好等于size，则调⽤linkLast(element)将其插⼊到末尾；否则调⽤
linkBefore(element, node(index))⽅法进⾏插⼊。
linkBefore中的node(index)是返回指定位置的元素。
1  　public void add(intindex, E element) {
2 checkPositionIndex(index);
3 if (index ==size)
4 linkLast(element);
5 else
6 linkBefore(element, node(index));
7 }
8 /**
9 * Returns the (non-null) Node at the specified element index.10 */
11 Node node(intindex) {12 //assert isElementIndex(index);13 //如果要取元素的位置是整个list⼀半的左半边，那么从list的头开始向后遍历，遍历⾄要取元素的位置
14 if (index < (size >> 1)) {15 Node x =first;16 for (int i = 0; i < index; i++)17 x =x.next;18 returnx;19 }20 //否则从list⼀半的右半边开始寻，也就是从尾部开始向前遍历，遍历⾄要取元素的位置
21 else{22 Node x =last;23 for (int i = size - 1; i > index; i--)24 x =x.prev;25 returnx;26 }27 }
删除
删除列表中指定位置的元素，⾸先检测该位置是否在该列表中存在，然后解除该元素前、后指向的元素。
1  　public E remove(intindex) {
2 checkElementIndex(index);
3 returnunlink(node(index));
4 }
5 E unlink(Nodex) {
6 //assert x != null;
7 final E element =x.item;8 final Node next =x.next;9 final Node prev =x.prev;10
11 if (prev == null) {12 first =next;13 } else{ =next;15 x.prev = null;16 }17
18 if (next == null) {19 last =prev;20 } else{21 next.prev =prev; = null;23 }24
25 x.item = null;26 size--;27 modCount++;28 returnelement;29 }
获取
<(int index)
获取指定位置元素的值。同样⾸先判断传⼊位置是否越界，如果超过list的size，抛出IndexOutBoundsException异常，然后node()⽅法进⾏左半边或右半边遍历获取，add(int index, E element)中有提到，不再赘述。
java中index是什么意思
1 public E get(intindex) {
2 checkElementIndex(index);
3 returnnode(index).item;
4 }
first、last是LinkedList的两个属性，判空后直接返回。
1 /**
2 * Returns the first element in this list.
3 *
4 *@returnthe first element in this list
5 *@throwsNoSuchElementException if this list is empty
6 */
7 publicE getFirst() {8 final Node f =first;9 if (f == null)10 throw newNoSuchElementException();11 returnf.item;12 }13
14 /**
15 * Returns the last element in this list.16 *17 *@returnthe last element in this list18 *@throwsNoSuchElementException if this list is empty19 */
20 publicE getLast() {21 final Node l =last;22 if (l == null)23 throw newNoSuchElementException();24 returnl.item;25 }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。