LinkedList学习

xiaoxiao2021-02-28  16

我们还是看源码,来了解LinkedList。

添加结点

我们先看add(E e)方法

public LinkedList() {//这是没有参数的构造方法,什么都没有执行 } public boolean add(E e) { linkLast(e); //进入这个方法,根据方法名可以猜测是往后添加新添加的元素 return true; } void linkLast(E e) { final Node<E> l = last; //第一次添加last为null,l也为null。这个last会随着添加的结点往后移,总是指向最后一个结点 final Node<E> newNode = new Node<>(l, e, null);//这个就是存储元素的结点了,第一次其实prev和next都指向null last = newNode; //最后的结点指向含有新添加元素的结点(第一次添加元素其实last为null) if (l == null)//第一次进入这个分支 first = newNode;//first指向含有新添加元素的结点,其实第一次last和first指向的是同一个结点 else l.next = newNode;//后面的就是最后一个结点的next指向新添加的结点,而新结点的prev已经在Node的构造函数中指向了此时的last(就是还没有添加新结点的最后一个结点) size++; // 这个size就是统计结点的个数 modCount++; //又看到这个,说明LinkedList是线程不安全的。 } transient Node<E> last; private static class Node<E> { //这个为存储元素的结点内部类 E item; //元素 Node<E> next; //下一个结点 Node<E> prev; //前一个结点 //看到这里,所以可以得出LinkedList是基于双向链表的。 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; //这个next其实总是指向null,因为这个结点顺序添加后为最后一个结点(调用add(E e)方法) this.prev = prev; } }

所以加上这个,就清楚地知道linkedlist调用add(E e)方法,发生了什么。就是基本的双向链表往最后面加结点的实现。

查找结点

我们再看一下get(index)方法。

public E get(int index) { checkElementIndex(index);//检查下标是否合法,这里就用到了size变量 return node(index).item;//我们进入这个方法 } private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isElementIndex(int index) { return index >= 0 && index < size;//size在这 }

我们看一下node(index)这个方法。

Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) {//如果index小于结点个数/2 Node<E> x = first;//找到第一个结点 for (int i = 0; i < index; i++)//从第一个结点往第index个结点找(往后找) x = x.next; return x; } else { //否则 Node<E> x = last; //找到最后一个结点 for (int i = size - 1; i > index; i--) //从最后一个结点往第index个结点找(往前找), x = x.prev; return x; } }

这样就减少了一半的查找量。双向链表的好处体现出来了,即减少了一半的查找量。

插入结点

我们看一下add(index,E e)方法。

public void add(int index, E element) { checkPositionIndex(index);//检查index if (index == size) //如果index==size,即往最后一个结点的后面插,和add(E e)方法一样了 linkLast(element); else linkBefore(element, node(index));//否则进入这个方法,node(index)返回第index个结点 }

我们看一下linkBefore这个方法。

void linkBefore(E e, Node<E> succ) { // assert succ != null; //这个方法完全就是知道要插入位置的后一个结点和前一个结点,直接插就行。 final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ);//这里新结点的prev和next都已经指向了前面的和后面的结点 succ.prev = newNode;//原本index位置上的结点的prev指向新结点 if (pred == null)//如果要插入位置的prev为null,则表明新插入的结点将会是第一个结点, first = newNode;//first总是指向第一个结点 else pred.next = newNode;//否则前一个结点的next指向新结点, size++; modCount++; }

就是相当于一个双向链表的插入。

删除结点。remove(Object o)

public boolean remove(Object o) { if (o == null) { //说明linkedlist可以插入null for (Node<E> x = first; x != null; x = x.next) {//从前往后找 if (x.item == null) { //找到 unlink(x);// return true; } } } else {//和上面一样 for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }

我们看一下unlick(x)方法。

E unlink(Node<E> x) { //双向链表的删除 // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }

所以我们可以看到对于LinkedList是基于双向链表的,插入、删除都是很快的,但查找就没有ArrayList快了(是查找一半)。他也是非线程安全的,可以插入null。

转载请注明原文地址: https://www.6miu.com/read-2800046.html

最新回复(0)