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

資訊專欄INFORMATION COLUMN

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

stackfing / 652人閱讀

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

linkedlist簡(jiǎn)單介紹（jdk1.8）

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

類定義

AbstractSequentialList是List接口的簡(jiǎn)化版，支持按次序訪問，abstractList支持隨機(jī)訪問。

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

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

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

Serializable代表可以被序列化

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

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

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

transient int size = 0;


transient Node first;


transient Node last;


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

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

public LinkedList() {}

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


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

核心方法

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


Node


鏈表中的單個(gè)結(jié)點(diǎn)，具有兩個(gè)指針域和一個(gè)數(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實(shí)現(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;
        }


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


//將頭結(jié)點(diǎn)賦值給final f，新建一個(gè)新的結(jié)點(diǎn)newNode,將newNode定義為頭節(jié)點(diǎn)。如果f=null，說(shuō)明此前是個(gè)空鏈表，所以last也定義newNode，否則將原頭節(jié)點(diǎn)f（現(xiàn)第二個(gè)節(jié)點(diǎn)）的前指針指向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é)點(diǎn)指向final l，聲明一個(gè)新的結(jié)點(diǎn)newNode（頭指針指向尾結(jié)點(diǎn)，尾指針指向null），將newNode定義    為新的尾結(jié)點(diǎn)。如果l=null，代表原鏈表沒有尾節(jié)點(diǎn)（空鏈表），則將newNode也設(shè)為頭節(jié)點(diǎn)。否則將原尾節(jié)點(diǎn)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é)點(diǎn)之前插入元素。在AC結(jié)點(diǎn)中插入b元素，將b元素生成B結(jié)點(diǎn)，將B節(jié)點(diǎn)的前指針指向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é)點(diǎn)從鏈表中分離。
    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ù)索引隨機(jī)訪問linkedlist，為get方法的真正實(shí)現(xiàn)。
//size右移1位，大致相當(dāng)于size/2.若index>size/2，則從尾結(jié)點(diǎn)向前遍歷，否則從頭結(jié)點(diǎn)向后遍歷
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é)

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

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

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

               

                      
               
              
              

                
相關(guān)文章

                
    
                             
                                                                                                    
  • 
                                                
    
                          
    我的阿里之路+Java面經(jīng)考點(diǎn)
    
                                                     
    摘要：我的是忙碌的一年，從年初備戰(zhàn)實(shí)習(xí)春招，年三十都在死磕源碼，三月份經(jīng)歷了阿里五次面試，四月順利收到實(shí)習(xí)。因?yàn)槲倚睦砗芮宄业哪繕?biāo)是阿里。所以在收到阿里之后的那晚，我重新規(guī)劃了接下來(lái)的學(xué)習(xí)計(jì)劃，將我的短期目標(biāo)更新成拿下阿里轉(zhuǎn)正。

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

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

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

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

              

              
               

                  
                  
發(fā)表評(píng)論

                   
               

              

                

                  
0條評(píng)論
   
                
 
                      

              

           
           

              
 
                

                   
              
  

                  
最新活動(dòng)
 
           
                             
              





                                
              

           

        
       
    
    
     

      
    

    
    

    
       
       

         
閱讀需要支付1元查看
  
         
     
       

      
  
    
    








        

            

              
              
            

             
        

    







<