国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

集合源碼學(xué)習(xí)之路---linkedlist

stackfing / 647人閱讀

摘要：類定義是接口的簡化版，支持按次序訪問，支持隨機訪問。否則將原尾節(jié)點的尾指針指向。在某結(jié)點之前插入元素。根據(jù)索引隨機訪問，為方法的真正實現(xiàn)。總結(jié)其實只要你對雙向鏈表結(jié)構(gòu)比較熟悉，那源碼讀起來就會很輕松。

linkedlist簡單介紹（jdk1.8）

linkedlist的底層結(jié)構(gòu)是線性表的雙向鏈表，每個節(jié)點包括兩個指針域（一個指向前驅(qū)結(jié)點，一個指向后繼結(jié)點）和一個數(shù)據(jù)域，因為雙指針域的獨特結(jié)構(gòu)，所以其擁有增刪快和存取慢的特點。鏈表結(jié)構(gòu)不需要預(yù)分配存儲空間，增加新的結(jié)點再去內(nèi)存中申請即可，不會造成內(nèi)存浪費和碎片化。

類定義

AbstractSequentialList是List接口的簡化版，支持按次序訪問，abstractList支持隨機訪問。

list接口許多常用的基礎(chǔ)方法,如set,get,indexof,remove等

Deque是一個雙端隊列接口，提供了類似棧、隊列,push,pop,peek的方法

Cloneable代表可以被復(fù)制

Serializable代表可以被序列化

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

和Arraylist一樣，linkedlist也是一個非線程安全的集合，只能在單線程環(huán)境下使用。若想獲得一個線程安全的linkedlist可以使用：

List list = Collections.synchronizedList(new LinkedList<>());
類屬性

transient int size = 0;


transient Node first;


transient Node last;


size:雙向鏈表中節(jié)點的個數(shù)
first:指向鏈表的首結(jié)點
last:指向鏈表的尾結(jié)點

構(gòu)造函數(shù)

public LinkedList() {}

public LinkedList(Collection c) {
        this();
        addAll(c);
    }


構(gòu)造函數(shù)只有兩個，第一個非常簡單，構(gòu)造一個空的linkedList。第二個有參構(gòu)造就是所有Collection下的子類都通過toArray變?yōu)閿?shù)組，然后通過遍歷生成節(jié)點插入雙向鏈表中。

核心方法

在閱讀核心方法之前，我們首先需要了解它的核心內(nèi)部類Node和ListItr.


Node


鏈表中的單個結(jié)點，具有兩個指針域和一個數(shù)據(jù)域，其結(jié)構(gòu)為:


private static class Node {
        E item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }


ListItr


AbstractSequentialList定義了抽象方法listIterator,linkedlist實現(xiàn)此方法，并返回迭代器ListItr;其結(jié)構(gòu)為：


private class ListItr implements ListIterator {
        private Node lastReturned;
        private Node next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }


其實迭代器的核心就是游標(biāo)，如果不清楚迭代器可以自行查詢相關(guān)原理，lastReturned是游標(biāo)前的元素，迭代器中修改數(shù)據(jù)結(jié)構(gòu)的方法操作的都是lastReturned，next就是游標(biāo)后元素，nextIndex為next的索引，expectedModCount
為父類AbstractList的modCount，因為是線程不安全的類，用來觸發(fā)fast-fail機制。用來遍歷iterator的有hasNext(),next(),hasPrevious(),previous()。通過iterator修改linkedlist的有remove(),set(),add(),操作的都是游標(biāo)前元素lastReturned，并且會根據(jù)modcount來觸發(fā)fast-fail機制的檢驗，這些方法的實現(xiàn)依賴于linkedlist的核心方法。 終于說完ListItr，強烈建議你們自己看下源碼，接下來讓我們一起看下linkedlist的實現(xiàn)：


//將頭結(jié)點賦值給final f，新建一個新的結(jié)點newNode,將newNode定義為頭節(jié)點。如果f=null，說明此前是個空鏈表，所以last也定義newNode，否則將原頭節(jié)點f（現(xiàn)第二個節(jié)點）的前指針指向newNode
private void linkFirst(E e) {
        final Node f = first;
        final Node newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
    
    //將尾結(jié)點指向final l，聲明一個新的結(jié)點newNode（頭指針指向尾結(jié)點，尾指針指向null），將newNode定義    為新的尾結(jié)點。如果l=null，代表原鏈表沒有尾節(jié)點（空鏈表），則將newNode也設(shè)為頭節(jié)點。否則將原尾節(jié)點l的尾指針指向newNode。
    void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    //在某結(jié)點之前插入元素。在AC結(jié)點中插入b元素，將b元素生成B結(jié)點，將B節(jié)點的前指針指向A，后指針指向C,將C的前指針指向B，將A的后指針指向B
    void linkBefore(E e, Node succ) {
        // assert succ != null;
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
    
    //將結(jié)點從鏈表中分離。
    E unlink(Node x) {
        // assert x != null;
        final E element = x.item;
        final Node next = x.next;
        final Node prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }


//根據(jù)索引隨機訪問linkedlist，為get方法的真正實現(xiàn)。
//size右移1位，大致相當(dāng)于size/2.若index>size/2，則從尾結(jié)點向前遍歷，否則從頭結(jié)點向后遍歷
Node node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    
    public E set(int index, E element) {
        checkElementIndex(index);
        Node x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
    
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    //查詢o最后一次出現(xiàn)的索引，將o分為兩種情況，一種為==null，另一種用equals比較，后序遍歷得索引值。
    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

總結(jié)

其實只要你對雙向鏈表結(jié)構(gòu)比較熟悉，那linkedlist源碼讀起來就會很輕松。linkedlist不需要分配存儲空間，只要有就可以分配，元素個數(shù)也不受限制，在找到指定索引的結(jié)點后，進行增刪改都是O（1）的操作，效率非常高。在遍歷linkedlist的時候，最好使用foreach或者iterator，嚴(yán)禁直接使用get（）遍歷。
           
               
                                           
                       
                 
            
                     
             
               

                   
 文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

                 
                   
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/68053.html

               

                      
               
              
              

                
相關(guān)文章

                
    
                             
                                                                                                    
  • 
                                                
    
                          
    我的阿里之路+Java面經(jīng)考點
    
                                                     
    摘要：我的是忙碌的一年，從年初備戰(zhàn)實習(xí)春招，年三十都在死磕源碼，三月份經(jīng)歷了阿里五次面試，四月順利收到實習(xí)。因為我心理很清楚，我的目標(biāo)是阿里。所以在收到阿里之后的那晚，我重新規(guī)劃了接下來的學(xué)習(xí)計劃，將我的短期目標(biāo)更新成拿下阿里轉(zhuǎn)正。

我的2017是忙碌的一年，從年初備戰(zhàn)實習(xí)春招，年三十都在死磕JDK源碼，三月份經(jīng)歷了阿里五次面試，四月順利收到實習(xí)offer。然后五月懷著忐忑的心情開始了螞蟻金...
    
                                                   
                          
    
                                
    
                                    姘擱『
                                    
                                    評論0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                                       
  • 
                                                
    
                          
    [學(xué)習(xí)筆記-Java集合-2] List -  LinkedList源碼分析
    
                                                     
    摘要：刪除元素作為雙端隊列，刪除元素也有兩種方式，一種是隊列首刪除元素，一種是隊列尾刪除元素。作為，又要支持中間刪除元素，所以刪除元素一個有三個方法，分別如下。在中間刪除元素比較低效，首先要找到刪除位置的節(jié)點，再修改前后指針，時間復(fù)雜度為。

介紹
LinkedList是一個以雙向鏈表實現(xiàn)的List，它除了作為List使用，還可以作為隊列或者棧來使用，它是怎么實現(xiàn)的呢？讓我們一起來學(xué)習(xí)吧。
繼...
    
                                                   
                          
    
                                
    
                                    novo
                                    
                                    評論0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                                       
  • 
                                                
    
                          
    Java 常用List集合使用場景分析
    
                                                     
    摘要：常用集合使用場景分析過年前的最后一篇，本章通過介紹，，，底層實現(xiàn)原理和四個集合的區(qū)別。和都是線程安全的，不同的是前者使用類，后者使用關(guān)鍵字。面試官會認(rèn)為你是一個基礎(chǔ)扎實，內(nèi)功深厚的人才到這里常用集合使用場景分析就結(jié)束了。

Java 常用List集合使用場景分析
過年前的最后一篇，本章通過介紹ArrayList，LinkedList，Vector，CopyOnWriteArrayList...
    
                                                   
                          
    
                                
    
                                    godruoyi
                                    
                                    評論0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                                       
  • 
                                                
    
                          
    Java集合干貨——LinkedList源碼分析
    
                                                     
    摘要：前言在上篇文章中我們對對了詳細的分析，今天我們來說一說。他們之間有什么區(qū)別呢最大的區(qū)別就是底層數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)不一樣，是數(shù)組實現(xiàn)的具體看上一篇文章，是鏈表實現(xiàn)的。至于其他的一些區(qū)別，可以說大部分都是由于本質(zhì)不同衍生出來的不同應(yīng)用。

前言
在上篇文章中我們對ArrayList對了詳細的分析，今天我們來說一說LinkedList。他們之間有什么區(qū)別呢？最大的區(qū)別就是底層數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)不一樣，...
    
                                                   
                          
    
                                
    
                                    jsdt
                                    
                                    評論0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                           
                

              

              
               

                  
                  
發(fā)表評論

                   
               

              

                

                  
0條評論
   
                
 
                      

              

           
           

              
 
                

                   
              
  

                  
最新活動
 
           
                             
              





                                
              

           

        
       
    
    
     

      
    

    
    

    
       
       

         
閱讀需要支付1元查看
  
         
     
       

      
  
    
    








        

            

              
              
            

             
        

    







<