精华内容
参与话题
问答
  • LinkList详解

    万次阅读 2018-04-27 15:22:26
    一、源码解析1、 LinkedList类定义2、LinkedList数据结构原理3、私有属性4、构造方法5、元素添加add()及原理6、删除数据remove()7、数据获取get()8、数据复制clone()与toArray()9、遍历数据:Iterator()二、ListItr...

     

    一、源码解析
    1、 LinkedList类定义
    2、LinkedList数据结构原理
    3、私有属性
    4、构造方法
    5、元素添加add()及原理
    6、删除数据remove()
    7、数据获取get()
    8、数据复制clone()与toArray()
    9、遍历数据:Iterator()
    二、ListItr

     

     

    一、源码解析

        1、 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 是非同步的。

     

    为什么要继承自AbstractSequentialList ?

    AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些骨干性函数。降低了List接口的复杂度。这些接口都是随机访问List的,LinkedList是双向链表;既然它继承于AbstractSequentialList,就相当于已经实现了“get(int index)这些接口”。

    此外,我们若需要通过AbstractSequentialList自己实现一个列表,只需要扩展此类,并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表,则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。

     

    LinkedList的类图关系:

     

    2、LinkedList数据结构原理

     

    LinkedList底层的数据结构是基于双向循环链表的,且头结点中不存放数据,如下:

     

    既然是双向链表,那么必定存在一种数据结构——我们可以称之为节点,节点实例保存业务数据,前一个节点的位置信息和后一个节点位置信息,如下图所示:

       3、私有属性

     LinkedList中之定义了两个属性:

     

    1 private transient Entry<E> header = new Entry<E>(null, null, null);
    2 private transient int size = 0;

     

    header是双向链表的头节点,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量: previous, next, element。其中,previous是该节点的上一个节点,next是该节点的下一个节点,element是该节点所包含的值。 
      size是双向链表中节点实例的个数。

    首先来了解节点类Entry类的代码。

     

    复制代码
    1 private static class Entry<E> {
     2    E element;
     3     Entry<E> next;
     4     Entry<E> previous;
     5 
     6     Entry(E element, Entry<E> next, Entry<E> previous) {
     7         this.element = element;
     8         this.next = next;
     9         this.previous = previous;
    10    }
    11 }
    复制代码

     

    节点类很简单,element存放业务数据,previous与next分别存放前后节点的信息(在数据结构中我们通常称之为前后节点的指针)。

        LinkedList的构造方法:

     

    复制代码
    1 public LinkedList() {
    2     header.next = header.previous = header;
    3 }
    4 public LinkedList(Collection<? extends E> c) {
    5     this();
    6    addAll(c);
    7 }
    复制代码

     

    4、构造方法

    LinkedList提供了两个构造方法。

    第一个构造方法不接受参数,将header实例的previous和next全部指向header实例(注意,这个是一个双向循环链表,如果不是循环链表,空链表的情况应该是header节点的前一节点和后一节点均为null),这样整个链表其实就只有header一个节点,用于表示一个空的链表。

     

    执行完构造函数后,header实例自身形成一个闭环,如下图所示:

     

    第二个构造方法接收一个Collection参数c,调用第一个构造方法构造一个空的链表,之后通过addAll将c中的元素全部添加到链表中。

     

     5、元素添加

    复制代码
     1 public boolean addAll(Collection<? extends E> c) {
     2     return addAll(size, c);
     3 }
     4 // index参数指定collection中插入的第一个元素的位置
      5 public boolean addAll(int index, Collection<? extends E> c) {
     6     // 插入位置超过了链表的长度或小于0,报IndexOutOfBoundsException异常
      7     if (index < 0 || index > size)
     8         throw new IndexOutOfBoundsException("Index: "+index+
      9                                                 ", Size: "+size);
    10     Object[] a = c.toArray();
    11    int numNew = a.length;
    12    // 若需要插入的节点个数为0则返回false,表示没有插入元素
    13     if (numNew==0)
    14         return false;
    15     modCount++;//否则,插入对象,链表修改次数加1
    16     // 保存index处的节点。插入位置如果是size,则在头结点前面插入,否则在获取index处的节点插入
    17     Entry<E> successor = (index==size ? header : entry(index));
    18     // 获取前一个节点,插入时需要修改这个节点的next引用
    19     Entry<E> predecessor = successor.previous;
    20     // 按顺序将a数组中的第一个元素插入到index处,将之后的元素插在这个元素后面
    21     for (int i=0; i<numNew; i++) {
    22         // 结合Entry的构造方法,这条语句是插入操作,相当于C语言中链表中插入节点并修改指针
    23         Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
    24         // 插入节点后将前一节点的next指向当前节点,相当于修改前一节点的next指针
    25         predecessor.next = e;
    26         // 相当于C语言中成功插入元素后将指针向后移动一个位置以实现循环的功能
    27         predecessor = e;
    28   }
    29     // 插入元素前index处的元素链接到插入的Collection的最后一个节点
    30     successor.previous = predecessor;
    31     // 修改size
    32     size += numNew;
    33     return true;
    34 }
    复制代码

     

     

    构造方法中的调用了addAll(Collection<? extends E> c)方法,而在addAll(Collection<? extends E> c)方法中仅仅是将size当做index参数调用了addAll(int index,Collection<? extends E> c)方法。

     

     

    复制代码
    1 private Entry<E> entry(int index) {
     2         if (index < 0 || index >= size)
     3             throw new IndexOutOfBoundsException("Index: "+index+
     4                                                 ", Size: "+size);
     5         Entry<E> e = header;
     6         // 根据这个判断决定从哪个方向遍历这个链表
     7         if (index < (size >> 1)) {
     8             for (int i = 0; i <= index; i++)
     9                 e = e.next;
    10         } else {
    11             // 可以通过header节点向前遍历,说明这个一个循环双向链表,header的previous指向链表的最后一个节点,这也验证了构造方法中对于header节点的前后节点均指向自己的解释
    12             for (int i = size; i > index; i--)
    13                 e = e.previous;
    14        }
    15         return e;
    16     }
    复制代码

     

     

     

    下面说明双向链表添加元素的原理:

    添加数据:add()

    复制代码
         // 将元素(E)添加到LinkedList中
         public boolean add(E e) {
             // 将节点(节点数据是e)添加到表头(header)之前。
             // 即,将节点添加到双向链表的末端。
             addBefore(e, header);
             return true;
         }
    
         public void add(int index, E element) {
             addBefore(element, (index==size ? header : entry(index)));
         }
        
        private Entry<E> addBefore(E e, Entry<E> entry) {
             Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
             newEntry.previous.next = newEntry;
             newEntry.next.previous = newEntry;
             size++;
             modCount++;
             return newEntry;
        }
    复制代码

     

    addBefore(E e,Entry<E> entry)方法是个私有方法,所以无法在外部程序中调用(当然,这是一般情况,你可以通过反射上面的还是能调用到的)。

    addBefore(E e,Entry<E> entry)先通过Entry的构造方法创建e的节点newEntry(包含了将其下一个节点设置为entry,上一个节点设置为entry.previous的操作,相当于修改newEntry的“指针”),之后修改插入位置后newEntry的前一节点的next引用和后一节点的previous引用,使链表节点间的引用关系保持正确。之后修改和size大小和记录modCount,然后返回新插入的节点。

    下面分解“添加第一个数据”的步骤:

    第一步:初始化后LinkedList实例的情况:

    第二步:初始化一个预添加的Entry实例(newEntry)。

    Entry newEntry = newEntry(e, entry, entry.previous);

     

     

    第三步:调整新加入节点和头结点(header)的前后指针。

    newEntry.previous.next = newEntry;

    newEntry.previous即header,newEntry.previous.next即header的next指向newEntry实例。在上图中应该是“4号线”指向newEntry。

    newEntry.next.previous = newEntry;

    newEntry.next即header,newEntry.next.previous即header的previous指向newEntry实例。在上图中应该是“3号线”指向newEntry。

    调整后如下图所示:

    图——加入第一个节点后LinkedList示意图

    下面分解“添加第二个数据”的步骤:

    第一步:新建节点。

    图——添加第二个节点

    第二步:调整新节点和头结点的前后指针信息。

    图——调整前后指针信息

    添加后续数据情况和上述一致,LinkedList实例是没有容量限制的。

     

    总结,addBefore(E e,Entry<E> entry)实现在entry之前插入由e构造的新节点。而add(E e)实现在header节点之前插入由e构造的新节点。为了便于理解,下面给出插入节点的示意图。

    复制代码
     public void addFirst(E e) {
         addBefore(e, header.next);
     }
    
     public void addLast(E e) {
         addBefore(e, header);
     }
    复制代码

     看上面的示意图,结合addBefore(E e,Entry<E> entry)方法,很容易理解addFrist(E e)只需实现在header元素的下一个元素之前插入,即示意图中的一号之前。addLast(E e)只需在实现在header节点前(因为是循环链表,所以header的前一个节点就是链表的最后一个节点)插入节点(插入后在2号节点之后)。

     

        清除数据clear()

    复制代码
     1 public void clear() {
     2     Entry<E> e = header.next;
     3     // e可以理解为一个移动的“指针”,因为是循环链表,所以回到header的时候说明已经没有节点了
     4      while (e != header) {
     5        // 保留e的下一个节点的引用
     6         Entry<E> next = e.next;
     7         // 解除节点e对前后节点的引用
     8         e.next = e.previous = null;
     9         // 将节点e的内容置空
    10         e.element = null;
    11         // 将e移动到下一个节点
    12         e = next;
    13  }
    14     // 将header构造成一个循环链表,同构造方法构造一个空的LinkedList
    15     header.next = header.previous = header;
    16     // 修改size
    17     size = 0;
    18     modCount++;
    19 }
    复制代码

     

       数据包含 contains(Object o)

    复制代码
     public boolean contains(Object o) {
         return indexOf(o) != -1;
     }
     // 从前向后查找,返回“值为对象(o)的节点对应的索引”  不存在就返回-1 
     public int indexOf(Object o) {
          int index = 0;
          if (o==null) {
              for (Entry e = header.next; e != header; e = e.next) {
                  if (e.element==null)
                      return index;
                  index++;
             }
          } else {
             for (Entry e = header.next; e != header; e = e.next) {
                 if (o.equals(e.element))
                     return index;
                 index++;
            }
        }
         return -1;
     }
    复制代码

    indexOf(Object o)判断o链表中是否存在节点的element和o相等,若相等则返回该节点在链表中的索引位置,若不存在则放回-1。

    contains(Object o)方法通过判断indexOf(Object o)方法返回的值是否是-1来判断链表中是否包含对象o。

     

    6、删除数据remove()

    几个remove方法最终都是调用了一个私有方法:remove(Entry<E> e),只是其他简单逻辑上的区别。下面分析remove(Entry<E> e)方法。

     

    复制代码
     1 private E remove(Entry<E> e) {
     2     if (e == header)
     3         throw new NoSuchElementException();
     4     // 保留将被移除的节点e的内容
     5     E result = e.element;
     6    // 将前一节点的next引用赋值为e的下一节点
     7     e.previous.next = e.next;
     8    // 将e的下一节点的previous赋值为e的上一节点
     9     e.next.previous = e.previous;
    10    // 上面两条语句的执行已经导致了无法在链表中访问到e节点,而下面解除了e节点对前后节点的引用
    11    e.next = e.previous = null;
    12   // 将被移除的节点的内容设为null
    13   e.element = null;
    14   // 修改size大小
    15   size--;
    16   modCount++;
    17   // 返回移除节点e的内容
    18   return result;
    19 }
    复制代码

     

    由于删除了某一节点因此调整相应节点的前后指针信息,如下:

    e.previous.next = e.next;//预删除节点的前一节点的后指针指向预删除节点的后一个节点。 

    e.next.previous = e.previous;//预删除节点的后一节点的前指针指向预删除节点的前一个节点。 

    清空预删除节点:

    e.next = e.previous = null;

    e.element = null;

    交给gc完成资源回收,删除操作结束。

    与ArrayList比较而言,LinkedList的删除动作不需要“移动”很多数据,从而效率更高。

     

    7、数据获取get()

    Get(int)方法的实现在remove(int)中已经涉及过了。首先判断位置信息是否合法(大于等于0,小于当前LinkedList实例的Size),然后遍历到具体位置,获得节点的业务数据(element)并返回。

    注意:为了提高效率,需要根据获取的位置判断是从头还是从尾开始遍历。

    复制代码
    // 获取双向链表中指定位置的节点    
        private Entry<E> entry(int index) {    
            if (index < 0 || index >= size)    
                throw new IndexOutOfBoundsException("Index: "+index+    
                                                    ", Size: "+size);    
            Entry<E> e = header;    
            // 获取index处的节点。    
            // 若index < 双向链表长度的1/2,则从前先后查找;    
            // 否则,从后向前查找。    
            if (index < (size >> 1)) {    
                for (int i = 0; i <= index; i++)    
                    e = e.next;    
            } else {    
                for (int i = size; i > index; i--)    
                    e = e.previous;    
            }    
            return e;    
        }
    复制代码

    注意细节:位运算与直接做除法的区别。先将index与长度size的一半比较,如果index<size/2,就只从位置0往后遍历到位置index处,而如果index>size/2,就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历

     

    8、数据复制clone()与toArray()

    clone()

    复制代码
     1 public Object clone() {
     2     LinkedList<E> clone = null;
     3     try {
     4         clone = (LinkedList<E>) super.clone();
     5     } catch (CloneNotSupportedException e) {
     6         throw new InternalError();
     7    }
     8     clone.header = new Entry<E>(null, null, null);
     9     clone.header.next = clone.header.previous = clone.header;
    10     clone.size = 0;
    11     clone.modCount = 0;
    12     for (Entry<E> e = header.next; e != header; e = e.next)
    13        clone.add(e.element);
    14     return clone;
    15 }
    复制代码

     调用父类的clone()方法初始化对象链表clone,将clone构造成一个空的双向循环链表,之后将header的下一个节点开始将逐个节点添加到clone中。最后返回克隆的clone对象。

        toArray()

    复制代码
    1 public Object[] toArray() {
    2     Object[] result = new Object[size];
    3     int i = 0;
    4     for (Entry<E> e = header.next; e != header; e = e.next)
    5         result[i++] = e.element;
    6     return result;
    7 }
    复制代码

    创建大小和LinkedList相等的数组result,遍历链表,将每个节点的元素element复制到数组中,返回数组。

        toArray(T[] a)

    复制代码
     1 public <T> T[] toArray(T[] a) {
     2     if (a.length < size)
     3         a = (T[])java.lang.reflect.Array.newInstance(
     4                                a.getClass().getComponentType(), size);
     5     int i = 0;
     6     Object[] result = a;
     7     for (Entry<E> e = header.next; e != header; e = e.next)
     8         result[i++] = e.element;
     9     if (a.length > size)
    10         a[size] = null;
    11     return a;
    12 }
    复制代码

    先判断出入的数组a的大小是否足够,若大小不够则拓展。这里用到了发射的方法,重新实例化了一个大小为size的数组。之后将数组a赋值给数组result,遍历链表向result中添加的元素。最后判断数组a的长度是否大于size,若大于则将size位置的内容设置为null。返回a。

        从代码中可以看出,数组a的length小于等于size时,a中所有元素被覆盖,被拓展来的空间存储的内容都是null;若数组a的length的length大于size,则0至size-1位置的内容被覆盖,size位置的元素被设置为null,size之后的元素不变。

        为什么不直接对数组a进行操作,要将a赋值给result数组之后对result数组进行操作?

     

    9、遍历数据:Iterator()

        LinkedList的Iterator

        除了Entry,LinkedList还有一个内部类:ListItr。

        ListItr实现了ListIterator接口,可知它是一个迭代器,通过它可以遍历修改LinkedList。

        在LinkedList中提供了获取ListItr对象的方法:listIterator(int index)。

     

    1 public ListIterator<E> listIterator(int index) {
    2     return new ListItr(index);
    3 }

     

    该方法只是简单的返回了一个ListItr对象。

        LinkedList中还有通过集成获得的listIterator()方法,该方法只是调用了listIterator(int index)并且传入0。

    二、ListItr

        下面详细分析ListItr。

     

    复制代码
      1 private class ListItr implements ListIterator<E> {
      2 // 最近一次返回的节点,也是当前持有的节点
      3     private Entry<E> lastReturned = header;
      4     // 对下一个元素的引用
      5     private Entry<E> next;
      6     // 下一个节点的index
      7     private int nextIndex;
      8     private int expectedModCount = modCount;
      9     // 构造方法,接收一个index参数,返回一个ListItr对象
     10     ListItr(int index) {
     11         // 如果index小于0或大于size,抛出IndexOutOfBoundsException异常
     12         if (index < 0 || index > size)
     13         throw new IndexOutOfBoundsException("Index: "+index+
     14                             ", Size: "+size);
     15         // 判断遍历方向
     16         if (index < (size >> 1)) {
     17         // next赋值为第一个节点
     18         next = header.next;
     19         // 获取指定位置的节点
     20         for (nextIndex=0; nextIndex<index; nextIndex++)
     21             next = next.next;
     22         } else {
     23 // else中的处理和if块中的处理一致,只是遍历方向不同
     24         next = header;
     25         for (nextIndex=size; nextIndex>index; nextIndex--)
     26             next = next.previous;
     27        }
     28    }
     29     // 根据nextIndex是否等于size判断时候还有下一个节点(也可以理解为是否遍历完了LinkedList)
     30     public boolean hasNext() {
     31         return nextIndex != size;
     32    }
     33     // 获取下一个元素
     34     public E next() {
     35        checkForComodification();
     36         // 如果nextIndex==size,则已经遍历完链表,即没有下一个节点了(实际上是有的,因为是循环链表,任何一个节点都会有上一个和下一个节点,这里的没有下一个节点只是说所有节点都已经遍历完了)
     37         if (nextIndex == size)
     38         throw new NoSuchElementException();
     39         // 设置最近一次返回的节点为next节点
     40         lastReturned = next;
     41         // 将next“向后移动一位”
     42         next = next.next;
     43         // index计数加1
     44         nextIndex++;
     45         // 返回lastReturned的元素
     46         return lastReturned.element;
     47    }
     48 
     49     public boolean hasPrevious() {
     50         return nextIndex != 0;
     51    }
     52     // 返回上一个节点,和next()方法相似
     53     public E previous() {
     54         if (nextIndex == 0)
     55         throw new NoSuchElementException();
     56 
     57         lastReturned = next = next.previous;
     58         nextIndex--;
     59        checkForComodification();
     60         return lastReturned.element;
     61    }
     62 
     63     public int nextIndex() {
     64         return nextIndex;
     65    }
     66 
     67     public int previousIndex() {
     68         return nextIndex-1;
     69    }
     70     // 移除当前Iterator持有的节点
     71     public void remove() {
     72            checkForComodification();
     73             Entry<E> lastNext = lastReturned.next;
     74             try {
     75                 LinkedList.this.remove(lastReturned);
     76             } catch (NoSuchElementException e) {
     77                 throw new IllegalStateException();
     78            }
     79         if (next==lastReturned)
     80                 next = lastNext;
     81             else
     82         nextIndex--;
     83         lastReturned = header;
     84         expectedModCount++;
     85    }
     86     // 修改当前节点的内容
     87     public void set(E e) {
     88         if (lastReturned == header)
     89         throw new IllegalStateException();
     90        checkForComodification();
     91         lastReturned.element = e;
     92    }
     93     // 在当前持有节点后面插入新节点
     94     public void add(E e) {
     95        checkForComodification();
     96         // 将最近一次返回节点修改为header
     97         lastReturned = header;
     98        addBefore(e, next);
     99         nextIndex++;
    100         expectedModCount++;
    101    }
    102     // 判断expectedModCount和modCount是否一致,以确保通过ListItr的修改操作正确的反映在LinkedList中
    103     final void checkForComodification() {
    104         if (modCount != expectedModCount)
    105         throw new ConcurrentModificationException();
    106    }
    107 }
    复制代码

     

    下面是一个ListItr的使用实例。

     

    复制代码
     1 LinkedList<String> list = new LinkedList<String>();
     2         list.add("First");
     3         list.add("Second");
     4         list.add("Thrid");
     5        System.out.println(list);
     6         ListIterator<String> itr = list.listIterator();
     7         while (itr.hasNext()) {
     8            System.out.println(itr.next());
     9        }
    10         try {
    11             System.out.println(itr.next());// throw Exception
    12         } catch (Exception e) {
    13             // TODO: handle exception
    14        }
    15         itr = list.listIterator();
    16        System.out.println(list);
    17        System.out.println(itr.next());
    18         itr.add("new node1");
    19        System.out.println(list);
    20         itr.add("new node2");
    21        System.out.println(list);
    22        System.out.println(itr.next());
    23         itr.set("modify node");
    24        System.out.println(list);
    25        itr.remove();
    26         System.out.println(list);
    复制代码

     

    复制代码
     1 结果:
     2 [First, Second, Thrid]
     3 First
     4 Second
     5 Thrid
     6 [First, Second, Thrid]
     7 First
     8 [First, new node1, Second, Thrid]
     9 [First, new node1, new node2, Second, Thrid]
    10 Second
    11 [First, new node1, new node2, modify node, Thrid]
    12 [First, new node1, new node2, Thrid]
    复制代码

    LinkedList还有一个提供Iterator的方法:descendingIterator()。该方法返回一个DescendingIterator对象。DescendingIterator是LinkedList的一个内部类。

     

    1 public Iterator<E> descendingIterator() {
    2    return new DescendingIterator();
    3 }

     

    下面分析详细分析DescendingIterator类。

     

    复制代码
     1 private class DescendingIterator implements Iterator {
     2    // 获取ListItr对象
     3 final ListItr itr = new ListItr(size());
     4 // hasNext其实是调用了itr的hasPrevious方法
     5    public boolean hasNext() {
     6        return itr.hasPrevious();
     7    }
     8 // next()其实是调用了itr的previous方法
     9    public E next() {
    10        return itr.previous();
    11    }
    12    public void remove() {
    13        itr.remove();
    14    }
    15 }
    复制代码

     

    从类名和上面的代码可以看出这是一个反向的Iterator,代码很简单,都是调用的ListItr类中的方法。

    展开全文
  • 链表中LinkList L与LinkList *L的区别

    千次阅读 多人点赞 2017-10-30 21:32:41
    链表中LinkList L与LinkList *L的区别 1 2 3 4 typedef struct Node{ int elem; struct node * next; }node,*LinkList;   对于...

    链表中LinkList L与LinkList *L的区别

    1
    2
    3
    4
    typedef struct Node{
    int elem;
    struct node * next;
    }node,*LinkList;

      

    对于LinkList L: L是指向定义的node结构体的指针,可以用->运算符来访问结构体成员,即L->elem,而(*L)就是个Node型的结构体了,可以用点运算符访问该结构体成员,即(*L).elem;

    对于LinkList *L:L是指向定义的Node结构体指针的指针,所以(*L)是指向Node结构体的指针,可以用->运算符来访问结构体成员,即(*L)->elem,当然,(**L)就是Node型结构体了,所以可以用点运算符来访问结构体成员,即(**L).elem;

    在链表操作中,我们常常要用链表变量作物函数的参数,这时,用LinkList L还是LinkList *L就很值得考虑深究了,一个用不好,函数就会出现逻辑错误,其准则是:
    如果函数会改变指针L的值,而你希望函数结束调用后保存L的值,那你就要用LinkList *L,这样,向函数传递的就是指针的地址,结束调用后,自然就可以去改变指针的值;
    而如果函数只会修改指针所指向的内容,而不会更改指针的值,那么用LinkList L就行了;

    下面说个具体实例吧!

    复制代码
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef int ElemType;
    typedef struct Node{
     ElemType elem;
     struct Node * next;
    }Node, * LinkList;
    复制代码

     

    //初始化链表,函数调用完毕后,L会指向一个空的链表,即会改变指针的值,所以要用*L

    void InitList(LinkList *L)
    {
     *L = (LinkList)malloc(sizeof(Node));
     (*L)->next = NULL;
    }

     

    //清空链表L,使L重新变为空链表,函数调用完后不会改变指针L的值,只会改变指针L所指向的内容(即L->next的值)

    void ClearList(LinkList L)
    {
     LinkList p;
     while(p = L->next)
      free(p);
    }

     

    //销毁链表L,释放链表L申请的内存,使L的值重新变为NULL,所以会改变L的值,得用*L

    复制代码
     1 void DestroyList(LinkList *L)
     2 {
     3  LinkList p;
     4  while(p = (*L)->next )
     5   free(p);
     6  free(*L);
     7  *L = NULL;
     8 }
     9 
    10 void main()
    11 {
    12  LinkList L = NULL;
    13  InitList(&L);
    14  ClearList(L);
    15  DestroyList(&L);
    16 }
    复制代码

     

    展开全文
  • 引用传递和值传递以及链表中的LinkList L、LinkList *L、LinkList &L1 函数参数传递的两种方式为值传递和引用传递 1.传值方式传参 c语言是按值传递的,在函数中被传递的参数的本身(实参)是不能被修改的!参数...

    引用传递和值传递以及链表中的LinkList L、LinkList *L、LinkList &L1

    函数参数传递的两种方式为值传递和引用传递

    1.传值方式传参

    c语言是按值传递的,在函数中被传递的参数的本身(实参)是不能被修改的!参数x传进去的时候会被复制了一份copy,此后的修改都是在临时变量copy上,出了函数体copy被销毁,x还是原来的x,根本就没有被修改过,所以对变量x的修改无效。

    如果想要修改传入的参数,有两种方法:

    ①传地址,传入x的地址,也就是将指向x的指针作为参数进行传递,【指针参数传递本质上是值传递,它所传递的是一个地址值】int f(int *x); f(&x); 指针传进去被复制了一份copy,x的指针的copy指向的内容也是x,对指针的copy的修改也就是修改了x的内容。 对于①来讲,在函数中如果传递的是指针,那么只能修改指针指向的内容,不能修改指针本身;如果想要修改指针本身,要么在再加一级指针,要么用引用&。

    ②引用传参 ,引用传参往往要比值传参高效,因为它是直接将x作为参数传入进去,而少了对x进行复制这部分的开销,既然传入进去的是x,那么对x的修改肯定也生效。

    2.引用方式传参

    引用可以被理解为变量的一个别名,但这依旧是原变量,如果在函数内对该变量进行修改的话,在外部该变量也会相应被修改。一定要先有原变量,才能有原变量的别名,故引用一定要赋初值,写成int &a=一个已存在的值的形式。

    int a=11; int &b=a; b=9 在这时输出a的值发现a=9。

    【比如:我的名字叫王**,别名叫王哥,我在函数里传入的参数为王哥,在函数内部我修改了王哥的体重,那么在调用函数时,王**的体重也被修改了。】

    引用声明后使用方式和原变量一样(用指针的话要加一个取值的操作)

    3.通过一段代码运行进一步理解传指针(包括二级指针)和传指针的引用

    ①函数传递的是指针变量的值——即该指针所指向的变量的地址,只能改变指针所指向变量的值,而不能改变指针本身的值。

    #include<cstdio>
    #include<stdlib.h>
    typedef struct LNode{
    	int data;
    	struct LNode *next;
    }LNode,*LinkList;
    void CreateList(LNode *header){
    	header=(LNode*)malloc(sizeof(LNode));
    	header->data=11;
    	header->next=NULL;
    }
    int main(){
    	LinkList head=NULL;
    	CreateList(head);
    	if(head!=NULL){
    		printf("%d\n",head->data);//什么都没有输出 
    	}
    	free(head);
    	return 0;
    }
    

    ②传递指针的地址,便可以修改指针本身的内容

    #include<cstdio>
    #include<stdlib.h>
    typedef struct LNode{
    	int data;
    	struct LNode *next;
    }LNode,*LinkList;
     
    //初始化链表,函数调用完毕后,L会指向一个空的链表,即会改变指针的值,所以要用**header
    //**header不仅能修改指针所指向变量的值,也能够修改指针本身的内容 
    void CreateList(LNode **header){ //(LinkList *header)
    	(*header)=(LNode*)malloc(sizeof(LNode));//(LinkList)malloc(sizeof(LNode));
    	(*header)->data=11;
    	(*header)->next=NULL;
    }
    int main(){
    	LinkList head=NULL;
    	CreateList(&head);//传递指针本身的地址 
    	if(head!=NULL){
    		printf("%d\n",head->data);//11 
    	}
    	free(head);
    	return 0;
    }
    

    ③(LinkList &header)这里的header其实是传入指针head的别名

    #include<cstdio>
    #include<stdlib.h>
    typedef struct LNode{
    	int data;
    	struct LNode *next;
    }LNode,*LinkList;
    //header其实是传入指针head的别名
    void CreateList(LinkList &header){ //参数也可写成(LNode *&header)
    	header=(LNode*)malloc(sizeof(LNode));//(LinkList)malloc(sizeof(LNode));
    	header->data=11;
    	header->next=NULL;
    }
    int main(){
    	LinkList head=NULL;
    	CreateList(head); 
    	if(head!=NULL){
    		printf("%d\n",head->data);//11 
    	}
    	free(head);
    	return 0;
    }
    

    4.总结

    其实指针类型和基本类型(比如int)来说,并没有本质上的差别。示例 :int x;LNode *L; (LNode为结构体)

    在传值方式传参时,对于基本类型:函数参数为int x,调用函数传入x;对于指针:函数参数为LNode *,调用函数时传入L
    在地址传递时,对于基本类型:函数参数为int *x,调用函数传入&x;对于指针:函数参数为LNode **,调用函数时传入&L。    
    在引用方式传参,对于基本类型:函数参数为int  &x,调用函数传入x;对于指针:函数参数为LNode* &L(或LinkList &L ),调用函数时传入&L。   
    

    当你传值时,只可以引用值而不可以改变值,但传值引用时,可以改变值; 当你传指针时,只可以改变指针所指的内容,不可以改变指针本身,但传指针引用时,即可以改变指针所指的内容,又可以改变指针本身

    →补充注意点:

    ①在定义函数时函数括号中的变量名成为形式参数,简称形参或虚拟参数;在主调函数中调用一个函数时,该函数括号中的参数名称为实际参数,简称实参,实参可以是常量、变量或表达式。

    ②C语言中实参和形参之间的额数据传递是单向的“值传递”,单向传递,只能由实参传给形参,反之不能。

    ③被调用函数的形参只有函数被调用时才会临时分配存储单元,一旦调用结束占用的内存便会被释放。

    ④”按值传递“中包括值传递和指针传递(指针传递参数本质上是值传递的方式,它所传递的是一个地址值),传递的都是实参的一个拷贝;虽然指针传递可以通过改变地址值来改变指针所指向的变量的值,但是不能改变指针本身的值。

    ⑤对于指针的引用类似于二级指针,但是也有一定的区别:无论你传值还是传指针,函数都会生成一个临时变量, 但传引用时,不会生成临时变量,不进行返回值copy等,速度快。

    ⑥关于引用传递和指针传递(本质是值【地址值】传递):

    · 相同点:都是地址的概念

    指针指向一块内存,它的内容是所指内存的地址;而引用则是某块内存的别名。

    · 不同点:

    指针是一个实体(也可以理解为替身);引用只是一个别名(本体的另一个名字)
    引用只能在定义时被初始化一次,之后不可改变;指针可以修改;
    引用不能为空;指针可以为空;
    sizeof 引用,得到的是所指向变量的大小;sizeof 指针,得到的是指针的大小;
    指针 ++,意义为 指针的地址自增;引用++则是 所指变量自增;
    引用是类型安全的,引用过程会进行类型检查;指针不会进行安全检查;
    


    1. 作者:Mongo_girl
      来源:CSDN
      原文:https://blog.csdn.net/m0_37345402/article/details/86622609 ↩︎

    展开全文
  • Linklist详解

    千次阅读 2018-04-27 19:12:52
    一.LinkList概述LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList 实现 List 接口,能进行队列操作。LinkedList 实现Deque接口,即能将...

    一.LinkList概述

    • LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈队列双端队列进行操作。
    • LinkedList 实现 List 接口,能进行队列操作。
    • LinkedList 实现Deque接口,即能将LinkedList当作双端队列使用。
    • LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。 
      -LinkedList 实现java.io.Serializable接口,这意味着LinkedList**支持序列化**,能通过序列化去传输。 
      LinkedList 是非同步的。
    • ArrayList底层是由数组支持,而LinkedList是由双向链表实现的,其中的每个对象包含数据的同时还包含指向链表中前一个与后一个元素的引用。

    二.LinkList的继承关系

    LinkList继承关系 
    public class LinkedList extends AbstractSequentialList 
    implements ListDequeCloneableSerializable

    三.LinkedList与Collection关系

    LinkedList与Collection 
    LinkedList的本质是双向链表。 
    LinkedList继承于AbstractSequentialList,并且实现了Dequeue接口。 
    LinkedList包含两个重要的成员:header 和 size。 
      header是双向链表的表头,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量: previous, next, element。其中,previous是该节点的上一个节点,next是该节点的下一个节点,element是该节点所包含的值。 
      size是双向链表中节点的个数。

    四.LinkList遍历方式

    • 迭代器遍历 
      “` 
      Iterator iterator = linkedList.iterator(); 
      while(iterator.hasNext()){ 
      iterator.next(); 
      }
    - for循环get()遍历
    
    • 1
    • 2

    for(int i = 0; i < linkedList.size(); i++){ 
    linkedList.get(i); 
    }

    - Foreach循环遍历
    
    • 1
    • 2

    for(Integer i : linkedList);

    
    -通过pollFirst()或pollLast()遍历
    
    • 1
    • 2
    • 3

    while(linkedList.size() != 0){ 
    linkedList.pollFirst(); 
    }

    
    -通过removeFirst()或removeLast()遍历
    
    • 1
    • 2
    • 3

    while(linkedList.size() != 0){ 
    linkedList.removeFirst(); 
    }

    
    - 效率测试
        测试以上几种遍历方式的效率,部分代码如下:
    
    
    • 1
    • 2
    • 3
    • 4
    • 5

    /**************** 遍历操作 **************
    System.out.println(“—————————————–”); 
    linkedList.clear(); 
    for(int i = 0; i < 100000; i++){ 
    linkedList.add(i); 

    // 迭代器遍历 
    long start = System.currentTimeMillis(); 
    Iterator iterator = linkedList.iterator(); 
    while(iterator.hasNext()){ 
    iterator.next(); 

    long end = System.currentTimeMillis(); 
    System.out.println(“Iterator:” + (end - start) +” ms”);

    // 顺序遍历(随机遍历) 
    start = System.currentTimeMillis(); 
    for(int i = 0; i < linkedList.size(); i++){ 
    linkedList.get(i); 

    end = System.currentTimeMillis(); 
    System.out.println(“for:” + (end - start) +” ms”);

    // 另一种for循环遍历 
    start = System.currentTimeMillis(); 
    for(Integer i : linkedList); 
    end = System.currentTimeMillis(); 
    System.out.println(“for2:” + (end - start) +” ms”);

    // 通过pollFirst()或pollLast()来遍历LinkedList 
    LinkedList temp1 = new LinkedList<>(); 
    temp1.addAll(linkedList); 
    start = System.currentTimeMillis(); 
    while(temp1.size() != 0){ 
    temp1.pollFirst(); 

    end = System.currentTimeMillis(); 
    System.out.println(“pollFirst()或pollLast():” + (end - start) +” ms”);

    // 通过removeFirst()或removeLast()来遍历LinkedList 
    LinkedList temp2 = new LinkedList<>(); 
    temp2.addAll(linkedList); 
    start = System.currentTimeMillis(); 
    while(temp2.size() != 0){ 
    temp2.removeFirst(); 

    end = System.currentTimeMillis(); 
    System.out.println(“removeFirst()或removeLast():” + (end - start) +” ms”);

    输出:
    
    • 1
    • 2

    Iterator:17 ms 
    for:8419 ms 
    for2:12 ms 
    pollFirst()或pollLast():12 ms 
    removeFirst()或removeLast():10 ms

    由测试结果可以看出,遍历LinkedList时,使用removeFirst()或removeLast()效率最高,而for循环get()效率最低,应避免使用这种方式进行。应当注意的是,使用pollFirst()或pollLast()或removeFirst()或removeLast()遍历时,会删除原始数据,若只单纯的读取,应当选用第一种或第三种方式。

    五.LinkList之API

    // Collection中定义的API  
    boolean             add(E object)//添加一个数组对象  
    boolean             addAll(Collection<? extends E> collection)//添加一个包含Collection的对象  
    void              clear()//清空  
    boolean             contains(Object object)//包含  
    boolean             containsAll(Collection<?> collection)  
    boolean             equals(Object object)//判等  
    int               hashCode()  
    boolean             isEmpty()//判空  
    Iterator<E>             iterator()  
    boolean             remove(Object object)//删除  
    boolean             removeAll(Collection<?> collection)  
    boolean             retainAll(Collection<?> collection)  
    int               size()  
    <T> T[]             toArray(T[] array)  
    Object[]             toArray()  
    // AbstractCollection中定义的API  
    void              add(int location, E object)  
    boolean             addAll(int location, Collection<? extends E> collection)  
    E                get(int location)//获取某个元素值  
    int               indexOf(Object object)  
    int               lastIndexOf(Object object)  
    ListIterator<E>             listIterator(int location)  
    ListIterator<E>             listIterator()  
    E                remove(int location)  
    E                set(int location, E object)  
    List<E>             subList(int start, int end)  
    // ArrayList新增的API  
    Object             clone()//  
    void              ensureCapacity(int minimumCapacity)//保证容量不小于元素个数  
    void              trimToSize()  
    void              removeRange(int fromIndex, int toIndex)  
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    六.LinkList源码解析

    为了更了解LinkedList的原理,下面对LinkedList源码代码作出分析。 
    在阅读源码之前,我们先对LinkedList的整体实现进行大致说明: 
    LinkedList实际上是通过双向链表去实现的。既然是双向链表,那么它的顺序访问会非常高效,而随机访问效率比较低。 
    既然LinkedList是通过双向链表的,但是它也实现了List接口{也就是说,它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”}。LinkedList是如何实现List的这些接口的,如何将“双向链表和索引值联系起来的”? 
    实际原理非常简单,它就是通过一个计数索引值来实现的。例如,当我们调用get(int location)时,首先会比较“location”和“双向链表长度的1/2”;若前者大,则从链表头开始往后查找,直到location位置;否则,从链表末尾开始先前查找,直到location位置。 
    这就是“双线链表和索引值联系起来”的方法。 
    好了,接下来开始阅读源码(只要理解双向链表,那么LinkedList的源码很容易理解的)。

    package java.util;
    
    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
        // 链表的表头,表头不包含任何数据。Entry是个链表类数据结构。
        private transient Entry<E> header = new Entry<E>(null, null, null);
    
        // LinkedList中元素个数
        private transient int size = 0;
    
        // 默认构造函数:创建一个空的链表
        public LinkedList() {
            header.next = header.previous = header;
        }
    
        // 包含“集合”的构造函数:创建一个包含“集合”的LinkedList
        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }
    
        // 获取LinkedList的第一个元素
        public E getFirst() {
            if (size==0)
                throw new NoSuchElementException();
    
            // 链表的表头header中不包含数据。
            // 这里返回header所指下一个节点所包含的数据。
            return header.next.element;
        }
    
        // 获取LinkedList的最后一个元素
        public E getLast()  {
            if (size==0)
                throw new NoSuchElementException();
    
            // 由于LinkedList是双向链表;而表头header不包含数据。
            // 因而,这里返回表头header的前一个节点所包含的数据。
            return header.previous.element;
        }
    
        // 删除LinkedList的第一个元素
        public E removeFirst() {
            return remove(header.next);
        }
    
        // 删除LinkedList的最后一个元素
        public E removeLast() {
            return remove(header.previous);
        }
    
        // 将元素添加到LinkedList的起始位置
        public void addFirst(E e) {
            addBefore(e, header.next);
        }
    
        // 将元素添加到LinkedList的结束位置
        public void addLast(E e) {
            addBefore(e, header);
        }
    
        // 判断LinkedList是否包含元素(o)
        public boolean contains(Object o) {
            return indexOf(o) != -1;
        }
    
        // 返回LinkedList的大小
        public int size() {
            return size;
        }
    
        // 将元素(E)添加到LinkedList中
        public boolean add(E e) {
            // 将节点(节点数据是e)添加到表头(header)之前。
            // 即,将节点添加到双向链表的末端。
            addBefore(e, header);
            return true;
        }
    
        // 从LinkedList中删除元素(o)
        // 从链表开始查找,如存在元素(o)则删除该元素并返回true;
        // 否则,返回false。
        public boolean remove(Object o) {
            if (o==null) {
                // 若o为null的删除情况
                for (Entry<E> e = header.next; e != header; e = e.next) {
                    if (e.element==null) {
                        remove(e);
                        return true;
                    }
                }
            } else {
                // 若o不为null的删除情况
                for (Entry<E> e = header.next; e != header; e = e.next) {
                    if (o.equals(e.element)) {
                        remove(e);
                        return true;
                    }
                }
            }
            return false;
        }
    
        // 将“集合(c)”添加到LinkedList中。
        // 实际上,是从双向链表的末尾开始,将“集合(c)”添加到双向链表中。
        public boolean addAll(Collection<? extends E> c) {
            return addAll(size, c);
        }
    
        // 从双向链表的index开始,将“集合(c)”添加到双向链表中。
        public boolean addAll(int index, Collection<? extends E> c) {
            if (index < 0 || index > size)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+size);
            Object[] a = c.toArray();
            // 获取集合的长度
            int numNew = a.length;
            if (numNew==0)
                return false;
            modCount++;
    
            // 设置“当前要插入节点的后一个节点”
            Entry<E> successor = (index==size ? header : entry(index));
            // 设置“当前要插入节点的前一个节点”
            Entry<E> predecessor = successor.previous;
            // 将集合(c)全部插入双向链表中
            for (int i=0; i<numNew; i++) {
                Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
                predecessor.next = e;
                predecessor = e;
            }
            successor.previous = predecessor;
    
            // 调整LinkedList的实际大小
            size += numNew;
            return true;
        }
    
        // 清空双向链表
        public void clear() {
            Entry<E> e = header.next;
            // 从表头开始,逐个向后遍历;对遍历到的节点执行一下操作:
            // (01) 设置前一个节点为null 
            // (02) 设置当前节点的内容为null 
            // (03) 设置后一个节点为“新的当前节点”
            while (e != header) {
                Entry<E> next = e.next;
                e.next = e.previous = null;
                e.element = null;
                e = next;
            }
            header.next = header.previous = header;
            // 设置大小为0
            size = 0;
            modCount++;
        }
    
        // 返回LinkedList指定位置的元素
        public E get(int index) {
            return entry(index).element;
        }
    
        // 设置index位置对应的节点的值为element
        public E set(int index, E element) {
            Entry<E> e = entry(index);
            E oldVal = e.element;
            e.element = element;
            return oldVal;
        }
    
        // 在index前添加节点,且节点的值为element
        public void add(int index, E element) {
            addBefore(element, (index==size ? header : entry(index)));
        }
    
        // 删除index位置的节点
        public E remove(int index) {
            return remove(entry(index));
        }
    
        // 获取双向链表中指定位置的节点
        private Entry<E> entry(int index) {
            if (index < 0 || index >= size)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+size);
            Entry<E> e = header;
            // 获取index处的节点。
            // 若index < 双向链表长度的1/2,则从前先后查找;
            // 否则,从后向前查找。
            if (index < (size >> 1)) {
                for (int i = 0; i <= index; i++)
                    e = e.next;
            } else {
                for (int i = size; i > index; i--)
                    e = e.previous;
            }
            return e;
        }
    
        // 从前向后查找,返回“值为对象(o)的节点对应的索引”
        // 不存在就返回-1
        public int indexOf(Object o) {
            int index = 0;
            if (o==null) {
                for (Entry e = header.next; e != header; e = e.next) {
                    if (e.element==null)
                        return index;
                    index++;
                }
            } else {
                for (Entry e = header.next; e != header; e = e.next) {
                    if (o.equals(e.element))
                        return index;
                    index++;
                }
            }
            return -1;
        }
    
        // 从后向前查找,返回“值为对象(o)的节点对应的索引”
        // 不存在就返回-1
        public int lastIndexOf(Object o) {
            int index = size;
            if (o==null) {
                for (Entry e = header.previous; e != header; e = e.previous) {
                    index--;
                    if (e.element==null)
                        return index;
                }
            } else {
                for (Entry e = header.previous; e != header; e = e.previous) {
                    index--;
                    if (o.equals(e.element))
                        return index;
                }
            }
            return -1;
        }
    
        // 返回第一个节点
        // 若LinkedList的大小为0,则返回null
        public E peek() {
            if (size==0)
                return null;
            return getFirst();
        }
    
        // 返回第一个节点
        // 若LinkedList的大小为0,则抛出异常
        public E element() {
            return getFirst();
        }
    
        // 删除并返回第一个节点
        // 若LinkedList的大小为0,则返回null
        public E poll() {
            if (size==0)
                return null;
            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;
        }
    
        // 返回第一个节点
        // 若LinkedList的大小为0,则返回null
        public E peekFirst() {
            if (size==0)
                return null;
            return getFirst();
        }
    
        // 返回最后一个节点
        // 若LinkedList的大小为0,则返回null
        public E peekLast() {
            if (size==0)
                return null;
            return getLast();
        }
    
        // 删除并返回第一个节点
        // 若LinkedList的大小为0,则返回null
        public E pollFirst() {
            if (size==0)
                return null;
            return removeFirst();
        }
    
        // 删除并返回最后一个节点
        // 若LinkedList的大小为0,则返回null
        public E pollLast() {
            if (size==0)
                return null;
            return removeLast();
        }
    
        // 将e插入到双向链表开头
        public void push(E e) {
            addFirst(e);
        }
    
        // 删除并返回第一个节点
        public E pop() {
            return removeFirst();
        }
    
        // 从LinkedList开始向后查找,删除第一个值为元素(o)的节点
        // 从链表开始查找,如存在节点的值为元素(o)的节点,则删除该节点
        public boolean removeFirstOccurrence(Object o) {
            return remove(o);
        }
    
        // 从LinkedList末尾向前查找,删除第一个值为元素(o)的节点
        // 从链表开始查找,如存在节点的值为元素(o)的节点,则删除该节点
        public boolean removeLastOccurrence(Object o) {
            if (o==null) {
                for (Entry<E> e = header.previous; e != header; e = e.previous) {
                    if (e.element==null) {
                        remove(e);
                        return true;
                    }
                }
            } else {
                for (Entry<E> e = header.previous; e != header; e = e.previous) {
                    if (o.equals(e.element)) {
                        remove(e);
                        return true;
                    }
                }
            }
            return false;
        }
    
        // 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)
        public ListIterator<E> listIterator(int index) {
            return new ListItr(index);
        }
    
        // List迭代器
        private class ListItr implements ListIterator<E> {
            // 上一次返回的节点
            private Entry<E> lastReturned = header;
            // 下一个节点
            private Entry<E> next;
            // 下一个节点对应的索引值
            private int nextIndex;
            // 期望的改变计数。用来实现fail-fast机制。
            private int expectedModCount = modCount;
    
            // 构造函数。
            // 从index位置开始进行迭代
            ListItr(int index) {
                // index的有效性处理
                if (index < 0 || index > size)
                    throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
                // 若 “index 小于 ‘双向链表长度的一半’”,则从第一个元素开始往后查找;
                // 否则,从最后一个元素往前查找。
                if (index < (size >> 1)) {
                    next = header.next;
                    for (nextIndex=0; nextIndex<index; nextIndex++)
                        next = next.next;
                } else {
                    next = header;
                    for (nextIndex=size; nextIndex>index; nextIndex--)
                        next = next.previous;
                }
            }
    
            // 是否存在下一个元素
            public boolean hasNext() {
                // 通过元素索引是否等于“双向链表大小”来判断是否达到最后。
                return nextIndex != size;
            }
    
            // 获取下一个元素
            public E next() {
                checkForComodification();
                if (nextIndex == size)
                    throw new NoSuchElementException();
    
                lastReturned = next;
                // next指向链表的下一个元素
                next = next.next;
                nextIndex++;
                return lastReturned.element;
            }
    
            // 是否存在上一个元素
            public boolean hasPrevious() {
                // 通过元素索引是否等于0,来判断是否达到开头。
                return nextIndex != 0;
            }
    
            // 获取上一个元素
            public E previous() {
                if (nextIndex == 0)
                throw new NoSuchElementException();
    
                // next指向链表的上一个元素
                lastReturned = next = next.previous;
                nextIndex--;
                checkForComodification();
                return lastReturned.element;
            }
    
            // 获取下一个元素的索引
            public int nextIndex() {
                return nextIndex;
            }
    
            // 获取上一个元素的索引
            public int previousIndex() {
                return nextIndex-1;
            }
    
            // 删除当前元素。
            // 删除双向链表中的当前节点
            public void remove() {
                checkForComodification();
                Entry<E> lastNext = lastReturned.next;
                try {
                    LinkedList.this.remove(lastReturned);
                } catch (NoSuchElementException e) {
                    throw new IllegalStateException();
                }
                if (next==lastReturned)
                    next = lastNext;
                else
                    nextIndex--;
                lastReturned = header;
                expectedModCount++;
            }
    
            // 设置当前节点为e
            public void set(E e) {
                if (lastReturned == header)
                    throw new IllegalStateException();
                checkForComodification();
                lastReturned.element = e;
            }
    
            // 将e添加到当前节点的前面
            public void add(E e) {
                checkForComodification();
                lastReturned = header;
                addBefore(e, next);
                nextIndex++;
                expectedModCount++;
            }
    
            // 判断 “modCount和expectedModCount是否相等”,依次来实现fail-fast机制。
            final void checkForComodification() {
                if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            }
        }
    
        // 双向链表的节点所对应的数据结构。
        // 包含3部分:上一节点,下一节点,当前节点值。
        private static class Entry<E> {
            // 当前节点所包含的值
            E element;
            // 下一个节点
            Entry<E> next;
            // 上一个节点
            Entry<E> previous;
    
            /**
             * 链表节点的构造函数。
             * 参数说明:
             *   element  —— 节点所包含的数据
             *   next      —— 下一个节点
             *   previous —— 上一个节点
             */
            Entry(E element, Entry<E> next, Entry<E> previous) {
                this.element = element;
                this.next = next;
                this.previous = previous;
            }
        }
    
        // 将节点(节点数据是e)添加到entry节点之前。
        private Entry<E> addBefore(E e, Entry<E> entry) {
            // 新建节点newEntry,将newEntry插入到节点e之前;并且设置newEntry的数据是e
            Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
            newEntry.previous.next = newEntry;
            newEntry.next.previous = newEntry;
            // 修改LinkedList大小
            size++;
            // 修改LinkedList的修改统计数:用来实现fail-fast机制。
            modCount++;
            return newEntry;
        }
    
        // 将节点从链表中删除
        private E remove(Entry<E> e) {
            if (e == header)
                throw new NoSuchElementException();
    
            E result = e.element;
            e.previous.next = e.next;
            e.next.previous = e.previous;
            e.next = e.previous = null;
            e.element = null;
            size--;
            modCount++;
            return result;
        }
    
        // 反向迭代器
        public Iterator<E> descendingIterator() {
            return new DescendingIterator();
        }
    
        // 反向迭代器实现类。
        private class DescendingIterator implements Iterator {
            final ListItr itr = new ListItr(size());
            // 反向迭代器是否下一个元素。
            // 实际上是判断双向链表的当前节点是否达到开头
            public boolean hasNext() {
                return itr.hasPrevious();
            }
            // 反向迭代器获取下一个元素。
            // 实际上是获取双向链表的前一个节点
            public E next() {
                return itr.previous();
            }
            // 删除当前节点
            public void remove() {
                itr.remove();
            }
        }
    
    
        // 返回LinkedList的Object[]数组
        public Object[] toArray() {
        // 新建Object[]数组
        Object[] result = new Object[size];
            int i = 0;
            // 将链表中所有节点的数据都添加到Object[]数组中
            for (Entry<E> e = header.next; e != header; e = e.next)
                result[i++] = e.element;
        return result;
        }
    
        // 返回LinkedList的模板数组。所谓模板数组,即可以将T设为任意的数据类型
        public <T> T[] toArray(T[] a) {
            // 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)
            // 则新建一个T[]数组,T[]的大小为LinkedList大小,并将该T[]赋值给a。
            if (a.length < size)
                a = (T[])java.lang.reflect.Array.newInstance(
                                    a.getClass().getComponentType(), size);
            // 将链表中所有节点的数据都添加到数组a中
            int i = 0;
            Object[] result = a;
            for (Entry<E> e = header.next; e != header; e = e.next)
                result[i++] = e.element;
    
            if (a.length > size)
                a[size] = null;
    
            return a;
        }
    
    
        // 克隆函数。返回LinkedList的克隆对象。
        public Object clone() {
            LinkedList<E> clone = null;
            // 克隆一个LinkedList克隆对象
            try {
                clone = (LinkedList<E>) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new InternalError();
            }
    
            // 新建LinkedList表头节点
            clone.header = new Entry<E>(null, null, null);
            clone.header.next = clone.header.previous = clone.header;
            clone.size = 0;
            clone.modCount = 0;
    
            // 将链表中所有节点的数据都添加到克隆对象中
            for (Entry<E> e = header.next; e != header; e = e.next)
                clone.add(e.element);
    
            return clone;
        }
    
        // java.io.Serializable的写入函数
        // 将LinkedList的“容量,所有的元素值”都写入到输出流中
        private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
            // Write out any hidden serialization magic
            s.defaultWriteObject();
    
            // 写入“容量”
            s.writeInt(size);
    
            // 将链表中所有节点的数据都写入到输出流中
            for (Entry e = header.next; e != header; e = e.next)
                s.writeObject(e.element);
        }
    
        // java.io.Serializable的读取函数:根据写入方式反向读出
        // 先将LinkedList的“容量”读出,然后将“所有的元素值”读出
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            // Read in any hidden serialization magic
            s.defaultReadObject();
    
            // 从输入流中读取“容量”
            int size = s.readInt();
    
            // 新建链表表头节点
            header = new Entry<E>(null, null, null);
            header.next = header.previous = header;
    
            // 从输入流中将“所有的元素值”并逐个添加到链表中
            for (int i=0; i<size; i++)
                addBefore((E)s.readObject(), header);
        }
    }
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396
    • 397
    • 398
    • 399
    • 400
    • 401
    • 402
    • 403
    • 404
    • 405
    • 406
    • 407
    • 408
    • 409
    • 410
    • 411
    • 412
    • 413
    • 414
    • 415
    • 416
    • 417
    • 418
    • 419
    • 420
    • 421
    • 422
    • 423
    • 424
    • 425
    • 426
    • 427
    • 428
    • 429
    • 430
    • 431
    • 432
    • 433
    • 434
    • 435
    • 436
    • 437
    • 438
    • 439
    • 440
    • 441
    • 442
    • 443
    • 444
    • 445
    • 446
    • 447
    • 448
    • 449
    • 450
    • 451
    • 452
    • 453
    • 454
    • 455
    • 456
    • 457
    • 458
    • 459
    • 460
    • 461
    • 462
    • 463
    • 464
    • 465
    • 466
    • 467
    • 468
    • 469
    • 470
    • 471
    • 472
    • 473
    • 474
    • 475
    • 476
    • 477
    • 478
    • 479
    • 480
    • 481
    • 482
    • 483
    • 484
    • 485
    • 486
    • 487
    • 488
    • 489
    • 490
    • 491
    • 492
    • 493
    • 494
    • 495
    • 496
    • 497
    • 498
    • 499
    • 500
    • 501
    • 502
    • 503
    • 504
    • 505
    • 506
    • 507
    • 508
    • 509
    • 510
    • 511
    • 512
    • 513
    • 514
    • 515
    • 516
    • 517
    • 518
    • 519
    • 520
    • 521
    • 522
    • 523
    • 524
    • 525
    • 526
    • 527
    • 528
    • 529
    • 530
    • 531
    • 532
    • 533
    • 534
    • 535
    • 536
    • 537
    • 538
    • 539
    • 540
    • 541
    • 542
    • 543
    • 544
    • 545
    • 546
    • 547
    • 548
    • 549
    • 550
    • 551
    • 552
    • 553
    • 554
    • 555
    • 556
    • 557
    • 558
    • 559
    • 560
    • 561
    • 562
    • 563
    • 564
    • 565
    • 566
    • 567
    • 568
    • 569
    • 570
    • 571
    • 572
    • 573
    • 574
    • 575
    • 576
    • 577
    • 578
    • 579
    • 580
    • 581
    • 582
    • 583
    • 584
    • 585
    • 586
    • 587
    • 588
    • 589
    • 590
    • 591
    • 592
    • 593
    • 594
    • 595
    • 596
    • 597
    • 598
    • 599
    • 600
    • 601
    • 602
    • 603
    • 604
    • 605
    • 606
    • 607
    • 608
    • 609
    • 610
    • 611
    • 612
    • 613
    • 614
    • 615
    • 616
    • 617
    • 618
    • 619
    • 620
    • 621
    • 622
    • 623
    • 624
    • 625
    • 626
    • 627
    • 628
    • 629
    • 630
    • 631
    • 632
    • 633
    • 634
    • 635
    • 636
    • 637
    • 638

    总结: 
    1.LinkedList 实际上是通过双向链表去实现的。 
    它包含一个非常重要的内部类:Entry。Entry是双向链表节点所对应的数据结构,它包括的属性有:当前节点所包含的值,上一个节点,下一个节点。 
    2.从LinkedList的实现方式中可以发现,它不存在LinkedList容量不足的问题。 
    3.LinkedList的克隆函数,即是将全部元素克隆到一个新的LinkedList对象中。 
    4.LinkedList实现java.io.Serializable。当写入到输出流时,先写入“容量”,再依次写入“每一个节点保护的值”;当读出输入流时,先读取“容量”,再依次读取“每一个元素”。 
    5.由于LinkedList实现了Deque,而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式:一种形式在操作失败时抛出异常,另一种形式返回一个特殊值(null 或 false,具体取决于操作)。 
    总结起来如下表格:

           第一个元素(头部)                 最后一个元素(尾部)
            抛出异常        特殊值            抛出异常           特殊值
    插入    addFirst(e)    offerFirst(e)    addLast(e)        offerLast(e)
    移除    removeFirst()  pollFirst()      removeLast()      pollLast()
    检查    getFirst()     peekFirst()      getLast()         peekLast()
    • 1
    • 2
    • 3
    • 4
    • 5

    6.LinkedList可以作为FIFO(先进先出)的队列,作为FIFO的队列时,下表的方法等价:

    队列方法       等效方法
    add(e)        addLast(e)
    offer(e)      offerLast(e)
    remove()      removeFirst()
    poll()        pollFirst()
    element()     getFirst()
    peek()        peekFirst()
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    7.LinkedList可以作为LIFO(后进先出)的栈,作为LIFO的栈时,下表的方法等价:

    栈方法        等效方法
    push(e)      addFirst(e)
    pop()        removeFirst()
    peek()       peekFirst()
    • 1
    • 2
    • 3
    • 4

    8.无论如何,千万不要通过随机访问去遍历LinkedList!

    七.LinkedList示例

    import java.util.List;
      2 import java.util.Iterator;
      3 import java.util.LinkedList;
      4 import java.util.NoSuchElementException;
      5 
      6 /*
      7  * @desc LinkedList测试程序。
      8  *
      9  * @author skywang
     10  * @email  kuiwu-wang@163.com
     11  */
     12 public class LinkedListTest {
     13     public static void main(String[] args) {
     14         // 测试LinkedList的API
     15         testLinkedListAPIs() ;
     16 
     17         // 将LinkedList当作 LIFO(后进先出)的堆栈
     18         useLinkedListAsLIFO();
     19 
     20         // 将LinkedList当作 FIFO(先进先出)的队列
     21         useLinkedListAsFIFO();
     22     }
     23     
     24     /*
     25      * 测试LinkedList中部分API
     26      */
     27     private static void testLinkedListAPIs() {
     28         String val = null;
     29         //LinkedList llist;
     30         //llist.offer("10");
     31         // 新建一个LinkedList
     32         LinkedList llist = new LinkedList();
     33         //---- 添加操作 ----
     34         // 依次添加1,2,3
     35         llist.add("1");
     36         llist.add("2");
     37         llist.add("3");
     38 
     39         // 将“4”添加到第一个位置
     40         llist.add(1, "4");
     41         
     42 
     43         System.out.println("\nTest \"addFirst(), removeFirst(), getFirst()\"");
     44         // (01) 将“10”添加到第一个位置。  失败的话,抛出异常!
     45         llist.addFirst("10");
     46         System.out.println("llist:"+llist);
     47         // (02) 将第一个元素删除。        失败的话,抛出异常!
     48         System.out.println("llist.removeFirst():"+llist.removeFirst());
     49         System.out.println("llist:"+llist);
     50         // (03) 获取第一个元素。          失败的话,抛出异常!
     51         System.out.println("llist.getFirst():"+llist.getFirst());
     52 
     53 
     54         System.out.println("\nTest \"offerFirst(), pollFirst(), peekFirst()\"");
     55         // (01) 将“10”添加到第一个位置。  返回true。
     56         llist.offerFirst("10");
     57         System.out.println("llist:"+llist);
     58         // (02) 将第一个元素删除。        失败的话,返回null。
     59         System.out.println("llist.pollFirst():"+llist.pollFirst());
     60         System.out.println("llist:"+llist);
     61         // (03) 获取第一个元素。          失败的话,返回null。
     62         System.out.println("llist.peekFirst():"+llist.peekFirst());
     63     
     64 
     65         System.out.println("\nTest \"addLast(), removeLast(), getLast()\"");
     66         // (01) 将“20”添加到最后一个位置。  失败的话,抛出异常!
     67         llist.addLast("20");
     68         System.out.println("llist:"+llist);
     69         // (02) 将最后一个元素删除。        失败的话,抛出异常!
     70         System.out.println("llist.removeLast():"+llist.removeLast());
     71         System.out.println("llist:"+llist);
     72         // (03) 获取最后一个元素。          失败的话,抛出异常!
     73         System.out.println("llist.getLast():"+llist.getLast());
     74 
     75 
     76         System.out.println("\nTest \"offerLast(), pollLast(), peekLast()\"");
     77         // (01) 将“20”添加到第一个位置。  返回true。
     78         llist.offerLast("20");
     79         System.out.println("llist:"+llist);
     80         // (02) 将第一个元素删除。        失败的话,返回null。
     81         System.out.println("llist.pollLast():"+llist.pollLast());
     82         System.out.println("llist:"+llist);
     83         // (03) 获取第一个元素。          失败的话,返回null。
     84         System.out.println("llist.peekLast():"+llist.peekLast());
     85 
     86          
     87 
     88         // 将第3个元素设置300。不建议在LinkedList中使用此操作,因为效率低!
     89         llist.set(2, "300");
     90         // 获取第3个元素。不建议在LinkedList中使用此操作,因为效率低!
     91         System.out.println("\nget(3):"+llist.get(2));
     92 
     93 
     94         // ---- toArray(T[] a) ----
     95         // 将LinkedList转行为数组
     96         String[] arr = (String[])llist.toArray(new String[0]);
     97         for (String str:arr) 
     98             System.out.println("str:"+str);
     99 
    100         // 输出大小
    101         System.out.println("size:"+llist.size());
    102         // 清空LinkedList
    103         llist.clear();
    104         // 判断LinkedList是否为空
    105         System.out.println("isEmpty():"+llist.isEmpty()+"\n");
    106 
    107     }
    108 
    109     /**
    110      * 将LinkedList当作 LIFO(后进先出)的堆栈
    111      */
    112     private static void useLinkedListAsLIFO() {
    113         System.out.println("\nuseLinkedListAsLIFO");
    114         // 新建一个LinkedList
    115         LinkedList stack = new LinkedList();
    116 
    117         // 将1,2,3,4添加到堆栈中
    118         stack.push("1");
    119         stack.push("2");
    120         stack.push("3");
    121         stack.push("4");
    122         // 打印“栈”
    123         System.out.println("stack:"+stack);
    124 
    125         // 删除“栈顶元素”
    126         System.out.println("stack.pop():"+stack.pop());
    127         
    128         // 取出“栈顶元素”
    129         System.out.println("stack.peek():"+stack.peek());
    130 
    131         // 打印“栈”
    132         System.out.println("stack:"+stack);
    133     }
    134 
    135     /**
    136      * 将LinkedList当作 FIFO(先进先出)的队列
    137      */
    138     private static void useLinkedListAsFIFO() {
    139         System.out.println("\nuseLinkedListAsFIFO");
    140         // 新建一个LinkedList
    141         LinkedList queue = new LinkedList();
    142 
    143         // 将10,20,30,40添加到队列。每次都是插入到末尾
    144         queue.add("10");
    145         queue.add("20");
    146         queue.add("30");
    147         queue.add("40");
    148         // 打印“队列”
    149         System.out.println("queue:"+queue);
    150 
    151         // 删除(队列的第一个元素)
    152         System.out.println("queue.remove():"+queue.remove());
    153     
    154         // 读取(队列的第一个元素)
    155         System.out.println("queue.element():"+queue.element());
    156 
    157         // 打印“队列”
    158         System.out.println("queue:"+queue);
    159     }
    160 }
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160

    运行结果:

    Test "addFirst(), removeFirst(), getFirst()"
    llist:[10, 1, 4, 2, 3]
    llist.removeFirst():10
    llist:[1, 4, 2, 3]
    llist.getFirst():1
    
    Test "offerFirst(), pollFirst(), peekFirst()"
    llist:[10, 1, 4, 2, 3]
    llist.pollFirst():10
    llist:[1, 4, 2, 3]
    llist.peekFirst():1
    
    Test "addLast(), removeLast(), getLast()"
    llist:[1, 4, 2, 3, 20]
    llist.removeLast():20
    llist:[1, 4, 2, 3]
    llist.getLast():3
    
    Test "offerLast(), pollLast(), peekLast()"
    llist:[1, 4, 2, 3, 20]
    llist.pollLast():20
    llist:[1, 4, 2, 3]
    llist.peekLast():3
    
    get(3):300
    str:1
    str:4
    str:300
    str:3
    size:4
    isEmpty():true
    
    
    useLinkedListAsLIFO
    stack:[4, 3, 2, 1]
    stack.pop():4
    stack.peek():3
    stack:[3, 2, 1]
    
    useLinkedListAsFIFO
    queue:[10, 20, 30, 40]
    queue.remove():10
    queue.element():20
    queue:[20, 30, 40] 
    展开全文
  • LinkList的实现

    2012-09-25 15:17:36
    java模拟linklist双向链表的实现
  • ArrayList与LinkList对比

    万次阅读 多人点赞 2018-09-06 15:37:34
    前边两篇博文简要总结了一下ArrayList和LinkedList的用法以及源码。本文简要总结一下这二者的区别,这在面试中也是常常会问到的一个知识点。 先来看一下ArrayList和LinkedList的关系是怎样的: ...
  • 手写LinkList

    2018-10-17 13:15:11
    1. LinkList原理 LinkedList 和 ArrayList 一样,都实现了 List 接口,但其内部的数据结构有本质的不同。LinkedList 是基于链表实现的(通过名字也能区分开来),所以它的插入和删除操作比 ArrayList 更加高效。但...
  • LinkedList浅析

    万次阅读 2018-08-27 10:29:39
    LinkedList简介 LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能对它进行队列操作。 ...LinkedList 实现 Deque 接口,...
  • Java重要类之LinkList类详解

    万次阅读 2016-09-23 17:25:59
    一.LinkList概述 LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能进行队列操作。 LinkedList 实现Deque接口,即能将...
  • java中ArrayList 、LinkList区别

    万次阅读 多人点赞 2011-08-11 13:42:24
    1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。   2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。  3.对于新增和删除操作add和remove,
  • typedef struct node{ int data;...}NODE,*LinkList; //初始化链表 int LnitList(LinkList *L){ .................... } //判断链表是否为空 int ListEmpty(LinkList L){ _.................... }
  • LinkList *L , LinkList *&L 和 LinkList &*L 的区别

    千次阅读 多人点赞 2014-10-07 21:32:52
    首先来看看 LinkList *L 和 LinkList *&L,
  • LinkedList

    千次阅读 2016-04-15 10:04:50
    初识LinkedList 上一篇中讲解了ArrayList,本篇文章讲解一下LinkedList的实现。 LinkedList是基于链表实现的,所以先讲解一下什么是链表。链表原先是C/C++的概念,是一种线性的存储结构,意思是将要存储的数据存在一...
  • /* List 接口的实现 AarryList : 底层实现: 可变数组实现的,内部 通过数组拷贝实现根据内容可变长 优点 : 根据索引查询效率高 缺点 :错增加删除时效率低,因为要通过数组拷贝实现 应用场景: 存储耽搁数据,有序...
  • LinkList

    2020-02-13 15:01:55
    for顺序遍历耗时 > iterator迭代器遍历耗时 > 通过removeFirst()或removeLast()遍历耗时 > forach顺序遍历耗时 = 通过pollFirst()或pollLast()来遍历耗时。 import java.util.ArrayList;...
  • Java LinkedList基本用法

    万次阅读 多人点赞 2014-12-01 22:03:20
    LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用. LinkedList的构造函数如下 1. public LinkedList(): ——生成空的链表 2. public LinkedList(Collection col): 复制构造函数 1、...
  • List之LinkedList源码实现

    千次阅读 热门讨论 2018-09-02 16:25:15
    LinkedList是基于链表实现的,所以先讲解一下什么是链表。链表原先是C/C++的概念,是一种线性的存储结构,意思是将要存储的数据存在一个存储单元里面,这个存储单元里面除了存放有待存储的数据以外,还存储有其下一...
  • ArrayList和LinkedList区别及使用场景

    万次阅读 多人点赞 2018-09-07 18:51:40
    ArrayList和LinkedList区别及使用场景 1. LinkedList和ArrayList的差别主要来自于Array和LinkedList数据结构的不同。ArrayList是基于数组实现的,LinkedList是基于双链表实现的。另外LinkedList类不仅是List接口的...
  • LinkedList详解

    2019-02-21 21:22:43
    LinkedList是双向链表结构,链表数据结构的特点是每个元素分配的空间不必连续、插入和删除元素时速度非常快、但访问元素的速度较慢。 LinkedList继承了AbstractSequentialList&lt;E&gt;,实现了List&lt;...
  • ArrayList 和 LinkedList 的区别

    万次阅读 2019-05-05 16:07:45
    ArrayList 和 LinkedList 的区别 ArrayList基于动态数组实现的非线程安全的集合;LinkedList基于链表实现的非线程安全的集合。 对于随机index访问的get和set方法,一般ArrayList的速度要优于LinkedList。因为...
  • LinkedList基本用法

    万次阅读 多人点赞 2012-10-06 11:50:02
    LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用. LinkedList的构造函数如下 1. public LinkedList(): ——生成空的链表 2. public LinkedList(Collection col): 复制构造函数 1、...
  • 简述ArrayList、Vector与LinkedList的异同点  Collection类的继承图如下:   从图中可以看出,LinkedList与ArrayList、ArrayDeque这三者都实现了List接口.所有使用方式也很相似,主要区别在于因为实现方式的不同,...
  • JDK 1.8 LinkedList源码分析

    千次阅读 多人点赞 2017-01-16 12:07:20
    LinkedList是一个实现了List接口和Deque接口的双端链表。 有关索引的操作可能从链表头开始遍历到链表尾部,也可能从尾部遍历到链表头部,这取决于看索引更靠近哪一端。 LinkedList不是线程安全的,如果想使...
  • ArrayList和LinkedList对比

    2017-02-14 15:31:38
    1、ArrayList和LinkedList简介 2、ArrayList和LinkedList对比 3、List常见遍历方式性能比较
  • ArrayList和LinkedList的区别、优缺点以及应用场景

    万次阅读 多人点赞 2018-12-09 09:17:21
    ArrayList和LinkedList都是实现了List接口的容器类,用于存储一系列的对象引用。他们都可以对元素的增删改查进行操作,那么他们区别、优缺点应用场景都有哪些呢?我们通过源码和数据结构来说明一下 ArrayList和...
  • LinkedList源码解析(基于JDK1.8)

    千次阅读 多人点赞 2018-05-27 18:41:48
    LinkedList将做为双链表来实现,它本身实现了List接口和Deque接口,并且实现了所有可选的列表操作,并且允许包含所有元素(包括null)。 下图是LinkedList的UML图: 从图中我们可以看出: 继承了...
  • java集合框架05——ArrayList和LinkedList的区别

    万次阅读 多人点赞 2016-04-13 20:39:09
    前面已经学习完了List部分的源码,主要是ArrayList和LinkedList两部分内容,这一节主要总结下List部分的内容。 List概括 先来回顾一下List在Collection中的的框架图: 从图中我们可以看出: 1. List是一个接口,它...
  • Java 常见面试题之“Arraylist和Linkedlist的区别”

    万次阅读 多人点赞 2018-07-24 11:19:22
    Arraylist:底层是基于动态数组,根据下表随机访问数组元素的效率高,向数组尾部添加元素的效率高;但是,删除数组中的数据以及向数组中间添加数据效率低,因为需要移动数组。例如最坏的情况是删除第一个数组元素,...
  • 当我们在聊LinkedList

    2018-05-23 18:00:25
    一丶概述上篇说到ArrayList及源码,这篇说说LinkedList及源码二丶正文1.目录图2.ArrayList与LinkedList区别(1)数据结构ArrayList,List()接口,列表,想象结构如下图:底层为数组,单向。LikedList实现List()...
  • linkedList

    2018-02-13 23:23:37
    深入解析hashMap底层原理,非常深入的讲解了HashMap和相关的数据的等信息

空空如也

1 2 3 4 5 ... 20
收藏数 239,501
精华内容 95,800
关键字:

linklist