java集合之LinkedList集合、LinkedList和ArrayList的一些区别

曾经终败给现在 2022-05-25 00:34 158阅读 0赞

补充  
[线程安全Collections.synchronizedList][Collections.synchronizedList]  
LinkedList和ArrayList都是线程不安全的，但是可以使用Collections.synchronizedList(list);来返回一个线程安全的集合。

List<String> list = new ArrayList<String>();
    List<String> list1 = Collections.synchronizedList(list);

使用返回的集合的方法都是线程安全的，注意：只针对它的原子方法是线程安全的，如果非原子方法是不安全的.  
**参考链接**  
[线程安全Collections.synchronizedList][Collections.synchronizedList]

源码是这样的

public static <T> List<T> synchronizedList(List<T> list) {
            return (list instanceof RandomAccess ?
                    new SynchronizedRandomAccessList<>(list) :
                    new SynchronizedList<>(list));
        }

--------------------

在学习LinkedList之前先了解其他几个名词，就是栈、队列、双向队列。

**栈**  
栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)，同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。  
栈的特点：先进后出、后进先出  
![20161127093301536][]

**栈的参考链接**  
[java数据结构与算法之栈（Stack）设计与实现][java_Stack]  
[Java数据结构和算法（四）——栈][Java]

**栈的方法**  
peek(),返回栈顶元素,未出栈  
pop(),出栈,返回栈顶元素,同时从栈中移除该元素

**队列**  
队列是一种特殊的线性表，其插入和删除的操作分别在表的两端进行，队列的特点就是先进先出(First In First Out)。我们把向队列中插入元素的过程称为入队(Enqueue)，删除元素的过程称为出队(Dequeue)并把允许入队的一端称为队尾，允许出的的一端称为队头，没有任何元素的队列则称为空队。

![20161203180332139][]

队列的参考链接  
[java数据结构与算法之（Queue）队列设计与实现][java_Queue]

**双向队列**  
双向队列就是在队列的基础扩展了，可以在队头和队尾实现入队和出队的操作。  
[Java 数据结构之Deque(双向队列)][Java _Deque]  
[一个用Java实现的双向队列，可以分别在头尾插入和删除节点][Java 1]

开始看LinkedList之前先看下LinkedList的继承和实现关系

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。  
LinkedList 实现 List 接口，能对它进行队列操作。  
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。  
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。  
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。

LinkedList源码分析JDK1.7（复制下面的连接里面的）  
[【Java集合源码剖析】LinkedList源码剖析][Java_LinkedList]  
[Java集合之LinkedList源码分析][Java_LinkedList 1]  
[LinkedList基本用法][LinkedList]

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
       //实现Serilizable接口时，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。
        transient int size = 0;
        //指向首节点
        transient Node<E> first;
        //指向最后一个节点
        transient Node<E> last;
        //构建一个空列表
        public LinkedList() {
        }
        //构建一个包含集合c的列表
        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }
       //将节点值为e的节点作为首节点
        private void linkFirst(E e) {
            final Node<E> f = first;
            //构建一个prev值为null,next为f,节点值为e的节点
            final Node<E> newNode = new Node<>(null, e, f);
            //将newNode作为首节点
            first = newNode;
            //如果newNode后面没有节点就将newNode作为最后一个节点
            if (f == null)
                last = newNode;
            //否则就将newNode赋给其prev
            else
                f.prev = newNode;
            //列表长度加一
            size++;
            modCount++;
        }
        //将节点值为e的节点作为最后一个节点
        void linkLast(E e) {
            final Node<E> l = last;
          //构建一个prev值为l,next为null,节点值为e的节点
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
        //在非空节点succ之前插入节点e
        void linkBefore(E e, Node<E> succ) {
            final Node<E> pred = succ.prev;
            //将succ前面的节点和succ作为其prev和next
            final Node<E> newNode = new Node<>(pred, e, succ);
            //然后将newNode作为succ的prev
            succ.prev = newNode; 
            //如果原来succ是首节点，则将newNode设置为首节点
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            size++;
            modCount++;
        }
         //释放非空的首节点f
        private E unlinkFirst(Node<E> f) {
            final E element = f.item;
            final Node<E> next = f.next;
            f.item = null;
            f.next = null; // help GC
            //将first节点后面的节点设为首节点
            first = next;
            if (next == null)
                last = null;
            else
                next.prev = null;
            size--;
            modCount++;
            return element;
        }
         //释放非空的尾节点l
           private E unlinkLast(Node<E> l) {
            final E element = l.item;
            final Node<E> prev = l.prev;
            l.item = null;
            l.prev = null; // help GC
            last = prev;
            if (prev == null)
                first = null;
            else
                prev.next = null;
            size--;
            modCount++;
            return element;
        }
        //删除非空节点x
        E unlink(Node<E> x) 
        {
            final E element = x.item;
            final Node<E> next = x.next;    //x后面的节点
            final Node<E> prev = x.prev;    //x前面的节点
    
            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;
        }
        //返回列表首节点元素值
        public E getFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return f.item;
        }
        //返列表尾节点元素值
        public E getLast() {
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return l.item;
        }
        //移除首节点
        public E removeFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }
       //删除尾节点
        public E removeLast() {
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return unlinkLast(l);
        }
      //在列表首部插入节点e
        public void addFirst(E e) {
            linkFirst(e);
        }
        //在列表尾部插入节点e
        public void addLast(E e) {
            linkLast(e);
        }
       //判断列表中是否包含有元素o
        public boolean contains(Object o) {
            return indexOf(o) != -1;
        }
        //返回列表长度大小
        public int size() {
            return size;
        }
        //在列表尾部插入元素
        public boolean add(E e) {
            linkLast(e);
            return true;
        }
        //删除元素为o的节点
        public boolean remove(Object o) 
        {    
            if (o == 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;
        }
       //将集合c中所有元素添加到列表的尾部
        public boolean addAll(Collection<? extends E> c) {
            return addAll(size, c);
        }
       //从指定的位置index开始，将集合c中的元素插入到列表中
        public boolean addAll(int index, Collection<? extends E> c) {
            //首先判断插入位置的合法性
            checkPositionIndex(index);
            Object[] a = c.toArray();
            int numNew = a.length;
            if (numNew == 0)
                return false;
            Node<E> pred, succ;
            if (index == size) {//说明在列表尾部插入集合元素
                succ = null;
                pred = last;
            } 
            else {  //否则，找到index所在的节点
                succ = node(index);
                pred = succ.prev;
            }
            for (Object o : a) {
                @SuppressWarnings("unchecked") E e = (E) o;
                Node<E> newNode = new Node<>(pred, e, null);
                if (pred == null)
                    first = newNode;
                else
                    pred.next = newNode;
                pred = newNode;
            }
            if (succ == null) {
                last = pred;
            } else {
                pred.next = succ;
                succ.prev = pred;
            }
            size += numNew;
            modCount++;
            return true;
        }
        //删除列表中所有节点
        public void clear() {
            for (Node<E> x = first; x != null; )  
            {
                Node<E> next = x.next;
                x.item = null;
                x.next = null;
                x.prev = null;
                x = next;
            }
            first = last = null;
            size = 0;
            modCount++;
        }
        //获取指定索引位置节点的元素值
        public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
        //替换指定索引位置节点的元素值
        public E set(int index, E element) {
            checkElementIndex(index);
            Node<E> x = node(index);
            E oldVal = x.item;
            x.item = element;
            return oldVal;
        }
        //在指定索引位置之前插入元素e
        public void add(int index, E element) {
            checkPositionIndex(index);   
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
        //删除指定位置的元素
        public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
        //判断指定索引位置的元素是否存在
        private boolean isElementIndex(int index) {
            return index >= 0 && index < size;
        }
        private boolean isPositionIndex(int index) {
            return index >= 0 && index <= size;
        }
        //构建 IndexOutOfBoundsException详细信息
        private String outOfBoundsMsg(int index) {
            return "Index: "+index+", Size: "+size;
        }
        private void checkElementIndex(int index) {
            if (!isElementIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        private void checkPositionIndex(int index) {
            if (!isPositionIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        //返回指定索引位置的节点
        Node<E> node(int index) {
            //此处是一个小技巧，当index<size/2时，从列表前半部分开始，否则从后半部分开始
            if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }//返回列表中第一次出现o的位置，若不存在则返回-1
        public int indexOf(Object o) {
            int index = 0;
            if (o == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null)
                        return index;
                    index++;
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item))
                        return index;
                    index++;
                }
            }
            return -1;
        }
        //逆向搜索，返回第一出现o的位置，不存在则返回-1
        public int lastIndexOf(Object o) {
            int index = size;
            if (o == null) {
                for (Node<E> x = last; x != null; x = x.prev) {
                    index--;
                    if (x.item == null)
                        return index;
                }
            } else {
                for (Node<E> x = last; x != null; x = x.prev) {
                    index--;
                    if (o.equals(x.item))
                        return index;
                }
            }
            return -1;
        }
       //获取列表首节点元素值
        public E peek() {
            final Node<E> f = first;
            return (f == null) ? null : f.item;
        }
    
        //获取列表首节点元素值，若为空则抛异常
        public E element() {
            return getFirst();
        }
       //检索首节点，若空则返回null,不为空则返回其元素值并删除首节点
        public E poll() {
            final Node<E> f = first;
            return (f == null) ? null : unlinkFirst(f);
        }
        //检索首节点，若空则抛异常,不为空则返回其元素值并删除首节点
        public E remove() {
            return removeFirst();
        }
       //在列表尾部增加节点e
        public boolean offer(E e) {
            return add(e);
        }
       //在列表首部插入节点e
        public boolean offerFirst(E e) {
            addFirst(e);
            return true;
        }
      //在列表尾部插入节点e
        public boolean offerLast(E e) {
            addLast(e);
            return true;
        }
        public E peekFirst() {
            final Node<E> f = first;
            return (f == null) ? null : f.item;
         }
      //获取列表尾节点元素值
        public E peekLast() {
            final Node<E> l = last;
            return (l == null) ? null : l.item;
        }
        public E pollFirst() {
            final Node<E> f = first;
            return (f == null) ? null : unlinkFirst(f);
        }
        public E pollLast() {
            final Node<E> l = last;
            return (l == null) ? null : unlinkLast(l);
        }
       //入栈
        public void push(E e)
        {
            addFirst(e);
        }
        //出栈
        public E pop() {
            return removeFirst();
        }
        //删除列表中第一出现o的节点
        public boolean removeFirstOccurrence(Object o) {
            return remove(o);
        }
        //逆向搜索，删除第一次出现o的节点
        public boolean removeLastOccurrence(Object o) {
            if (o == null) {
                for (Node<E> x = last; x != null; x = x.prev) {
                    if (x.item == null) {
                        unlink(x);
                        return true;
                    }
                }
            } else {
                for (Node<E> x = last; x != null; x = x.prev) {
                    if (o.equals(x.item)) {
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }

LinkedList的源码还是比较简单，就是链表前后相连，做处理的时候考虑到各种情况就好~~~  
**LinkedList的一些特点**  
1、也是非线程安全的  
2、可以用于栈、队列、双向队列的数据结构中去。  
3、使用链表形式，没有ArrayList里面的扩容之说。  
4、添加数据在尾部快，如果需要添加到指定位置复杂还是0(n),可根据规则做一定的优化。  
5、没有下标概念，查询数据需要遍历列表，可根据情况做一定的优化。  
6、允许null元素存在，对元素是null做不同的处理。

**LinkedList和ArrayList的一些区别**  
[Java中ArrayList和LinkedList区别][Java_ArrayList_LinkedList]

[Collections.synchronizedList]: http://huffmans.iteye.com/blog/1774752
[20161127093301536]: /images/20220525/c98b3b7f3caf4ff59d0e4a906ae1c003.png
[java_Stack]: https://blog.csdn.net/javazejian/article/details/53362993
[Java]: https://www.cnblogs.com/ysocean/p/7911910.html
[20161203180332139]: /images/20220525/f5bdd8ffbf82478389bf4ee0d32a3a89.png
[java_Queue]: https://blog.csdn.net/javazejian/article/details/53375004
[Java _Deque]: https://blog.csdn.net/top_code/article/details/8650729
[Java 1]: https://blog.csdn.net/sesiria/article/details/52586467
[Java_LinkedList]: https://blog.csdn.net/ns_code/article/details/35787253
[Java_LinkedList 1]: https://www.cnblogs.com/xujian2014/p/4630785.html
[LinkedList]: https://blog.csdn.net/i_lovefish/article/details/8042883
[Java_ArrayList_LinkedList]: http://pengcqu.iteye.com/blog/502676