JAVA数据结构——集合之LinkedList-白红宇

JAVA数据结构——集合之LinkedList

阅读量：5089 次

发布时间：2019-06-13

本文共 5695 字，大约阅读时间需要 18 分钟。

LinkedList与ArrayList同继承自List接口，其与ArrayList的本质区别即是，ArrayList内置了一个数组，而LinkedList则内置了一个链表，其余所有的区别均衍生自两者的本质区别。

LinkedList与ArrayList的主要区别：

LinkedList内置链表，ArrayList内置数组

因为链表和数组的差异，在执行add方法时，一旦ArrayList的空间不足会引起整个ArrayList的拷贝，效率较低，而LinkedList理论上是没有大小限制的

因为链表和数组的差异，在执行插入时，ArrayList的会引起部分空间拷贝（拷贝数据的多少取决于插入元素的位置），LinkedList则会执行遍历操作

其他差异，也基本由于结构的不同导致，随时补充

常用方法：

内部节点结构

1     private static class Node
      
        { 2         E item; 3         Node
       
         next; 4         Node
        
          prev; 5  6         Node(Node
         
           prev, E element, Node
          
            next) { 7             this.item = element; 8             this.next = next; 9             this.prev = prev;10         }11     }

private static class Node

数据结构

1     transient int size = 0; 2  3     /** 4      * Pointer to first node. 5      * Invariant: (first == null && last == null) || 6      *            (first.prev == null && first.item != null) 7      */ 8     transient Node
      
        first; 9 10     /**11      * Pointer to last node.12      * Invariant: (first == null && last == null) ||13      *            (last.next == null && last.item != null)14      */15     transient Node
       
         last;

结构变量

构造方法，LinkedList的默认构造方法为空，仅仅构建对象。非默认构造方法如下，

1     /** 2      * 以参数集合构建新的LinkedList，构建过程调用addAll实现 3      */ 4     public LinkedList(Collection
       c) { 5         this(); 6         addAll(c); 7     } 8  9     /**10      * 调用11      */12     public boolean addAll(Collection
       c) {13         return addAll(size, c);14     }15 16     /**17      * Inserts all of the elements in the specified collection into this18      * list, starting at the specified position.  Shifts the element19      * currently at that position (if any) and any subsequent elements to20      * the right (increases their indices).  The new elements will appear21      * in the list in the order that they are returned by the22      * specified collection's iterator.23      *24      * @param index index at which to insert the first element25      *              from the specified collection26      * @param c collection containing elements to be added to this list27      * @return {
     @code true} if this list changed as a result of the call28      * @throws IndexOutOfBoundsException {
     @inheritDoc}29      * @throws NullPointerException if the specified collection is null30      */31     public boolean addAll(int index, Collection
       c) {32         checkPositionIndex(index);33 34         Object[] a = c.toArray();35         int numNew = a.length;36         if (numNew == 0)37             return false;38 39         Node
      
        pred, succ;40         if (index == size) {41             succ = null;42             pred = last;43         } else {44             succ = node(index);45             pred = succ.prev;46         }47 48         for (Object o : a) {49             @SuppressWarnings("unchecked") E e = (E) o;50             Node
       
         newNode = new Node<>(pred, e, null);51             if (pred == null)52                 first = newNode;53             else54                 pred.next = newNode;55             pred = newNode;56         }57 58         if (succ == null) {59             last = pred;60         } else {61             pred.next = succ;62             succ.prev = pred;63         }64 65         size += numNew;66         modCount++;67         return true;68     }

public LinkedList(Collection<? extends E> c)

add(E e)方法，将e插入到链表的最尾的一个位置

1     /** 2      * Appends the specified element to the end of this list. 3      * 4      * This method is equivalent to {
     @link #addLast}. 5      * 6      * @param e element to be appended to this list 7      * @return {
     @code true} (as specified by {
     @link Collection#add}) 8      */ 9     public boolean add(E e) {10         linkLast(e);11         return true;12     }13 14     /**15      * 将元素插入到链表的尾部16      */17     void linkLast(E e) {18         final Node
       
         l = last;19         final Node
        
          newNode = new Node<>(l, e, null);20         last = newNode;21         if (l == null)22             first = newNode;23         else24             l.next = newNode;25         size++;26         modCount++;27     }

public boolean add(E e)

add(int index, E e)方法，将e插入到链表指定的index位置节点的前面

1     /** 2      * Inserts the specified element at the specified position in this list. 3      * Shifts the element currently at that position (if any) and any 4      * subsequent elements to the right (adds one to their indices). 5      * 6      * @param index index at which the specified element is to be inserted 7      * @param element element to be inserted 8      * @throws IndexOutOfBoundsException {
     @inheritDoc} 9      */10     public void add(int index, E element) {11         checkPositionIndex(index);12 13         if (index == size)14             linkLast(element);15         else16             linkBefore(element, node(index));17     }18 19     /**20      * Inserts element e before non-null Node succ.21      */22     void linkBefore(E e, Node
      
        succ) {23         // assert succ != null;24         final Node
       
         pred = succ.prev;25         final Node
        
          newNode = new Node<>(pred, e, succ);26         succ.prev = newNode;27         if (pred == null)28             first = newNode;29         else30             pred.next = newNode;31         size++;32         modCount++;33     }

public void add(int index, E element)

更多的操作均是基于链表的形式去操作的，搞清楚LinkedList的数据结构，对LinkedList的常用方法也就不陌生了。

转载于:https://www.cnblogs.com/qq455988971/p/7993080.html

你可能感兴趣的文章