LinkedList学习

LinkedList的全面说明

1.LinkedList底层实现了双向链表和双端队列特点

2.可以添加任意元素(元素可以重复)，包括null

3.线程不安全，没有实现同步

LinkedList的底层操作机制

1.Linkedlist底层维护了一个双向链表

2.LinkedList中维护了两个属性first和last分别指向 首节点 和 尾结点

3.每个节点（Node对象），里面又维护了prev，next，item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表。

4.所以LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高

package List_.LinkedList_;

import java.util.Iterator;
import java.util.LinkedList;
@SuppressWarnings({"all"})
public class LinkedList_ {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        System.out.println("linkedList=" + linkedList);
//演示一个删除结点的
        linkedList.remove(); // 这里默认删除的是第一个结点
//linkedList.remove(2);
        System.out.println("linkedList=" + linkedList);
//修改某个结点对象
        linkedList.set(1, 999);
        System.out.println("linkedList=" + linkedList);
//得到某个结点对象
//get(1) 是得到双向链表的第二个对象
        Object o = linkedList.get(1);
        System.out.println(o);//999
//因为 LinkedList 是 实现了 List 接口, 遍历方式
        System.out.println("===LinkeList 遍历迭代器====");
        Iterator iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            Object next = iterator.next();
            System.out.println("next=" + next);
        }
        System.out.println("===LinkeList 遍历增强 for====");
        for (Object o1 : linkedList) {
            System.out.println("o1=" + o1);
        }
        System.out.println("===LinkeList 遍历普通 for====");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
//源码阅读.
/* 1. LinkedList linkedList = new LinkedList();
        public LinkedList() {}
        2. 这时 linkeList 的属性 first = null
        3. 执行 添加
        public boolean add(E e) {
            linkLast(e);
            return true;
        }
        4.将新的结点，加入到双向链表的最后
        void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
*/
        
/*
    读源码 linkedList.remove(); // 这里默认删除的是第一个结点
    1. 执行 removeFirst
        public E remove() {
            return removeFirst();
        }
    2. 执行
        public E removeFirst() {
            final Node<E> f = first;
            if (f == null)
            throw new NoSuchElementException();
            return unlinkFirst(f);
        }
    3. 执行 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;
            if (next == null)
                last = null;
            else
                next.prev = null;
            size--;
            modCount++;
            return element;
        }
*/
    }
}

ArrayList和LinkedList比较

ArrayList和LinkedList比较：

	底层结构	增删的效率	改查的效率
ArrayList	可变数组	较低，数组扩容	较高
LinkedList	双向链表	较高，通过链表追加	较低

如何选择ArrayList和LinkedList：

1.如果改查的操作多，选择ArrayList

2.如果增删的操作多，选择LinkedList