Java集合类源代码之LinkedList

Java集合类源代码之linkedList

• Java集合类源代码之linkedList
• • linked list简介：
  • linkedList必备知识点总结：
  • • (一)ArrayList与linkedList的区别有哪些？
    • • 对于 ArrayList 来说：
      • • 1）get(int index)
        • 2）add(E e)
        • 3）add(int index, E element)
        • 4）remove(int index)
      • 对于对于 linkedList 来说：
      • • 1）get(int index)
        • 2）add(E e)
        • 3）add(int index, E element)
        • 4）remove(int index)
    • （二）linkedList作为队列使用
    • • 队列的基本方法
      • 演示：
      • .add()//添加元素
      • .poll()//删除队列头元素
      • .peek()//获取队列头元素，不删除
    • （三）linkedList作为栈使用
    • • 栈的基本方法
      • 演示：
      • .push() //将元素插入到栈顶
      • .pop() //取出栈顶的元素并删除栈顶的元素
      • .peek() //获取栈顶元素，不删除
    • （四）linkedList作为双端队列使用
    • • 双端队列的基本方法
      • 演示：
      • .addFirst() ; //在队列头部添加
      • .pollFirst() ; //删除头部第一个元素（等价于poll()）
      • .peekFirst() ; //获取头部第一个元素（等价于peek()）
      • .addLast() ; //在队列尾部添加（等价于add()）
      • .pollLast() ; // 删除并返回最后一个节点
      • .peekLast() ; //获取尾部第一个元素
  • 迭代器：
  • • 迭代器的构造方法
    • hasNext（） 判断是否有下一个数据
    • next（）读取下一个数据
    • hasPrevious（） 判断当前位置前面是否还有数据
    • previous（）获取上一个数据
  • 源码：
  • 总结

Java集合类源代码之linkedList

Java集合工具包位于Java.util包下，包含了很多常用的数据结构，如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分：List列表、Set集合、Map映射、迭代器（Iterator、Enumeration）、工具类（Arrays、Collections）。
Java集合框架图：

从上图中可以看出，集合类主要分为两大类：Collection和Map。

Collection是List、Set等集合高度抽象出来的接口，它包含了这些集合的基本操作，它主要又分为两大部分：List和Set。

今天我们说的Java集合类之 linkedList

linked list简介：

linkedList是基于 双向循环链表（从源码中可以很容易看出）实现的，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用。

linkedList同样是非线程安全的，只在单线程下适合使用。

linkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了Cloneable接口，能被克隆。

---

---

linkedList必备知识点总结： (一)ArrayList与linkedList的区别有哪些？

看这个之前大家可以先去看看ArrayList的源码总结
点这里可以到上到Arraylist的文章去
区别已经说过一次了 以防还有人不知道 那么贴一次。

家人们 来自阿里面试官的问题：好好听，虽然我讲得不好

ArrayList 内部使用的动态数组来存储元素，linkedList 内部使用的双向链表来存储元素，这也是 ArrayList 和 linkedList 最本质的区别。 对于 ArrayList 来说： 1）get(int index)

get(int index) 方法的时间复杂度为 O ( 1 ) ，因为是直接从底层数组根据下标获取的，和数组长度无关。这也是 ArrayList 的最大优点。

 // 获取index位置的元素值  
    public E get(int index) {  
        RangeCheck(index);  

        return (E) elementData[index];  
    }  

2）add(E e)

add(E e) 方法会默认将元素添加到数组末尾，但需要考虑到数组扩容的情况，如果不需要扩容，时间复杂度为 O ( 1 )。

//  将e 添加到ArrayList中  
    public boolean add(E e) {  
        ensureCapacity(size + 1);  // Increments modCount!!  
        elementData[size++] = e;  
        return true;  
    }  

    // 将e添加到ArrayList的指定位置  
    public void add(int index, E element) {  
        if (index > size || index < 0)  
            throw new IndexOutOfBoundsException(  
            "Index: "+index+", Size: "+size);  

        ensureCapacity(size+1);  // Increments modCount!!  
        System.arraycopy(elementData, index, elementData, index + 1,  
             size - index);  
        elementData[index] = element;  
        size++;  
    }  

但是 这个的话 需要考虑 是否超出容器的大小 看是否需要扩容 如果需要扩容的话，并且不是第一次（oldCapacity > 0）扩容的时候，内部执行的 Arrays.copyOf() 方法是耗时的关键，需要把原有数组中的元素复制到扩容后的新数组当中。

*这个点 我不太明白 因为我没看到我的源码，不过看一个大佬写的是如下源代码 *

 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

3）add(int index, E element)

add(int index, E element) 方法将新的元素插入到指定的位置，需要先通过遍历查找这个元素，然后再进行插入，所以时间复杂度为 O ( n )。

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
            elementData, index + 1,
            s - index);
    elementData[index] = element;
    size = s + 1;
}

4）remove(int index)

remove(int index) 方法将指定位置上的元素删除，考虑到需要复制底层数组，所以时间复杂度为 O ( n )

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}
private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

对于对于 linkedList 来说： 1）get(int index)

get(int index) 方法的时间复杂度为 O ( n ) ，因为需要循环遍历整个链表。

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

linkedList.Node node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        linkedList.Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        linkedList.Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

下标小于链表长度的一半时，从前往后遍历；否则从后往前遍历，这样从理论上说，就节省了一半的时间。

如果下标为 0 或者 list.size() - 1 的话，时间复杂度为 O ( 1 ) O(1)O(1)。这种情况下，可以使用 getFirst() 和 getLast() 方法。

public E getFirst() {
    final linkedList.Node f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

public E getLast() {
    final linkedList.Node l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

first 和 last 在链表中是直接存储的，所以时间复杂度为 O ( 1 ) 。

2）add(E e)

add(E e) 方法默认将元素添加到链表末尾，所以时间复杂度为 O ( 1 ) O(1)O(1)。

public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(E e) {
    final linkedList.Node l = last;
    final linkedList.Node newNode = new linkedList.Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

3）add(int index, E element)

add(int index, E element) 方法将新的元素插入到指定的位置，需要先通过遍历查找这个元素，然后再进行插入，所以时间复杂度为 O ( n )

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

如果下标为 0 或者 list.size() - 1 的话，时间复杂度为 O ( 1 ) 。这种情况下，可以使用 addFirst() 和 addLast() 方法。

public void addFirst(E e) {
    linkFirst(e);
}
private void linkFirst(E e) {
    final linkedList.Node f = first;
    final linkedList.Node newNode = new linkedList.Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

linkFirst() 只需要对 first 进行更新即可。

public void addLast(E e) {
    linkLast(e);
}

void linkLast(E e) {
    final linkedList.Node l = last;
    final linkedList.Node newNode = new linkedList.Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

linkLast() 只需要对 last 进行更新即可。

需要注意的是，有些文章里面说，linkedList 插入元素的时间复杂度近似 O ( 1 )，其实是有问题的，因为 add(int index, E element) 方法在插入元素的时候会调用 node(index) 查找元素，该方法之前我们之间已经确认过了，时间复杂度为 O ( n )，即便随后调用 linkBefore() 方法进行插入的时间复杂度为 O ( 1 )，总体上的时间复杂度仍然为 O ( n )才对。

void linkBefore(E e, linkedList.Node succ) {
    // assert succ != null;
    final linkedList.Node pred = succ.prev;
    final linkedList.Node newNode = new linkedList.Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

4）remove(int index)

remove(int index) 方法将指定位置上的元素删除，考虑到需要调用 node(index) 方法查找元素，所以时间复杂度为 O ( n )。

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(linkedList.Node x) {
    // assert x != null;
    final E element = x.item;
    final linkedList.Node next = x.next;
    final linkedList.Node 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;
}

需要注意

如果列表很大很大，ArrayList 和 linkedList 在内存的使用上也有所不同。linkedList的每个元素都有更多开销，因为要存储上一个和下一个元素的地址。ArrayList 没有这样的开销。
但是，ArrayList 占用的内存在声明的时候就已经确定了（默认大小为 10），不管实际上是否添加了元素，因为复杂对象的数组会通过null 来填充。linkedList 在声明的时候不需要指定大小，元素增加或者删除时大小随之改变。

另外，ArrayList 只能用作列表；linkedList 可以用作列表或者队列，因为它还实现了 Deque 接口。

---

（二）linkedList作为队列使用

开头就说了 因为linkedList是双向循环链表 所以它也可以当成队列，栈和双端队列来使用
首先我们先来说一下linkedList关于队列操作的源码。

队列的基本方法

//定义
linkedList queue = new linkedList();

//添加元素
queue.add(1);

//删除队列头元素
queue.poll();

//获取队列头元素，不删除
queue.peek();

演示：

首先定义就不说了 直接看源码：

.add()//添加元素

public boolean add(E e) {
        linkLast(e); //添加在队尾
        return true;
    }

.poll()//删除队列头元素

  // 删除并返回第一个节点
        // 若linkedList的大小为0,则返回null
        public E poll() {
            if (size == 0)
                return null;
            return removeFirst();
        }

.peek()//获取队列头元素，不删除

     // 返回第一个节点
        // 若linkedList的大小为0,则返回null
        public E peek() {
            if (size == 0)
                return null;
            return getFirst();
        }

（三）linkedList作为栈使用 栈的基本方法

//定义栈
linkedList stack = new linkedList();

//将元素插入到栈顶
stack.push(1)

//取出栈顶的元素并删除栈顶的元素
stack.pop()

//获取栈顶元素，不删除
stack.peek()

演示：

源码分析如下：

.push() //将元素插入到栈顶

 // 将e插入到双向链表开头
        public void push(E e) {
            addFirst(e);
        }

.pop() //取出栈顶的元素并删除栈顶的元素

// 删除并返回第一个节点
        public E pop() {
            return removeFirst();
        }

.peek() //获取栈顶元素，不删除

 // 返回第一个节点
        // 若linkedList的大小为0,则返回null
        public E peekFirst() {
            if (size == 0)
                return null;
            return getFirst();
        }

（四）linkedList作为双端队列使用 双端队列的基本方法

//定义
linkedList deque = new linkedList();

deque.addFirst();	//在队列头部添加
deque.pollFirst();	//删除头部第一个元素（等价于poll()）
deque.peekFirst();	//获取头部第一个元素（等价于peek()）

deque.addLast(1); 	//在队列尾部添加（等价于add()）
deque.pollLast();	//删除尾部第一个元素
deque.peekLast();	//获取尾部第一个元素

演示：

.addFirst() ; //在队列头部添加

// 将元素添加到linkedList的起始位置
        public void addFirst(E e) {
            addBefore(e, header.next);
        }

.pollFirst() ; //删除头部第一个元素（等价于poll()）

// 删除并返回第一个节点
        // 若linkedList的大小为0,则返回null
        public E pollFirst() {
            if (size == 0)
                return null;
            return removeFirst();
        }

.peekFirst() ; //获取头部第一个元素（等价于peek()）

          // 返回第一个节点
        // 若linkedList的大小为0,则返回null
        public E peekFirst() {
            if (size == 0)
                return null;
            return getFirst();
        }

.addLast() ; //在队列尾部添加（等价于add()）

  // 将元素添加到linkedList的结束位置
        public void addLast(E e) {
            addBefore(e, header);
        }

.pollLast() ; // 删除并返回最后一个节点

     // 删除并返回最后一个节点
        // 若linkedList的大小为0,则返回null
        public E pollLast() {
            if (size == 0)
                return null;
            return removeLast();
        }

.peekLast() ; //获取尾部第一个元素

        // 返回最后一个节点
        // 若linkedList的大小为0,则返回null
        public E peekLast() {
            if (size == 0)
                return null;
            return getLast();
        }

---

---

迭代器：

这里就不再分析 添加元素，删除元素，查找数组的源码了 上面多多少少都提到了 然后 最下面的源码 也有介绍这些源码

这里主要分析一下迭代

Java 中存在一个双向迭代器的接口：ListIterator，这个接口提供了向前和向后的迭代方法，如下所示：

迭代器----是一个对象，他的工作是遍历并选择序列中的对象，而客户端的程序员不必知道和关心该序列底层的结构。迭代器通常被称为‘轻量级对象’，创建他的代价小。

其实说白了 就是正序遍历，反向迭代无非就说逆序遍历数组

演示：

 public static void fun6() {
        List arraylist = new ArrayList();
        arraylist.add(1);
        arraylist.add(2);
        arraylist.add(3);
        arraylist.add(5);
        arraylist.add(0, 0);//在index=0的位置上插入10
        arraylist.add(4, 4);
        System.out.println("arraylist里的整数列表为：" + "n" + arraylist);

        //1,linkedList支持在两端插入和删除操作。
        linkedList