日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
數(shù)據(jù)結(jié)構(gòu)之LinkedList底層實(shí)現(xiàn)和原理詳解

前言

日常開發(fā)中，集合是我們經(jīng)常用到的一種數(shù)據(jù)結(jié)構(gòu)，當(dāng)然，集合也并不是一種，也沒有所謂的最好的集合，只有最適合的;

成都創(chuàng)新互聯(lián)是一家專注網(wǎng)站建設(shè)、網(wǎng)絡(luò)營(yíng)銷策劃、微信小程序定制開發(fā)、電子商務(wù)建設(shè)、網(wǎng)絡(luò)推廣、移動(dòng)互聯(lián)開發(fā)、研究、服務(wù)為一體的技術(shù)型公司。公司成立10年以來，已經(jīng)為上1000家成都純水機(jī)各業(yè)的企業(yè)公司提供互聯(lián)網(wǎng)服務(wù)?，F(xiàn)在，服務(wù)的上1000家客戶與我們一路同行，見證我們的成長(zhǎng)；未來，我們一起分享成功的喜悅。

當(dāng)然作為高級(jí)程序員，我們不僅僅要會(huì)用，還要了解其中的原理;

今天我們就來聊聊LinkedList底層實(shí)現(xiàn)和原理

一、LinkedList介紹

 
 
 
 
      
  
  
  
  1. public class LinkedList 
    2.   
  
  
  
  2.     extends AbstractSequentialList 
    3.   
  
  
  
  3.     implements List, Deque, Cloneable, java.io.Serializable 
    4.   
  
  
  
  4. { 
    5.   
  
  
  
  5.     //長(zhǎng)度 
    6.   
  
  
  
  6.     transient int size = 0; 
    7.   
  
  
  
  7.     //指向頭結(jié)點(diǎn) 
    8.   
  
  
  
  8.     transient Node first; 
    9.   
  
  
  
  9.     //指向尾結(jié)點(diǎn) 
    10.   
  
  
  
  10.     transient Node last; 
    11.   
  
  
  
  11. } 
    12.

1、LinkedList概述

LinkedList同時(shí)實(shí)現(xiàn)了List接口和Deque對(duì)口，也就是收它既可以看作一個(gè)順序容器，又可以看作一個(gè)隊(duì)列(Queue)，同時(shí)又可以看作一個(gè)棧(stack);

這樣看來，linkedList簡(jiǎn)直就是無敵的，當(dāng)你需要使用棧或者隊(duì)列時(shí)，可以考慮用LinkedList,一方面是因?yàn)镴ava官方已經(jīng)聲明不建議使用Stack類，更遺憾的是，Java里根本沒有一個(gè)叫做Queue的類(只是一個(gè)接口的名字);

關(guān)于?；蜿?duì)列，現(xiàn)在首選是ArrayDeque，它有著比LinkedList(當(dāng)作?；蜿?duì)列使用時(shí))更好的性能;

LinkedList的實(shí)現(xiàn)方式?jīng)Q定了所有跟下表有關(guān)的操作都是線性時(shí)間，而在首段或者末尾刪除元素只需要常數(shù)時(shí)間。為追求效率LinkedList沒有實(shí)現(xiàn)同步(synchronized)，如果需要多個(gè)線程并發(fā)訪問，可以先采用Collections.synchronizedList()方法對(duì)其進(jìn)行包裝

2、數(shù)據(jù)結(jié)構(gòu)

繼承關(guān)系

 
 
 
 
      
  
  
  
  1. java.lang.Object  
    2.   
  
  
  
  2.     java.util.AbstractCollection  
    3.   
  
  
  
  3.         java.util.AbstractList  
    4.   
  
  
  
  4.             java.util.AbstractSequentialList  
    5.   
  
  
  
  5.                 java.util.LinkedList  
    6.

實(shí)現(xiàn)接口

 
 
 
 
      
  
  
  
  1. Serializable, Cloneable, Iterable, Collection, Deque, List, Queue  
    2.

基本屬性

  • transient int size = 0; //LinkedList中存放的元素個(gè)數(shù)
  • transient Node first; //頭節(jié)點(diǎn)
  • transient Node last; //尾節(jié)點(diǎn)
  • Collection 接口：Collection接口是所有集合類的根節(jié)點(diǎn)，Collection表示一種規(guī)則，所有實(shí)現(xiàn)了Collection接口的類遵循這種規(guī)則

繼承的類與實(shí)現(xiàn)的接口

  • List 接口：List是Collection的子接口，它是一個(gè)元素有序(按照插入的順序維護(hù)元素順序)、可重復(fù)、可以為null的集合
  • AbstractCollection 類：Collection接口的骨架實(shí)現(xiàn)類，最小化實(shí)現(xiàn)了Collection接口所需要實(shí)現(xiàn)的工作量
  • AbstractList 類：List接口的骨架實(shí)現(xiàn)類，最小化實(shí)現(xiàn)了List接口所需要實(shí)現(xiàn)的工作量
  • Cloneable 接口：實(shí)現(xiàn)了該接口的類可以顯示的調(diào)用Object.clone()方法，合法的對(duì)該類實(shí)例進(jìn)行字段復(fù)制，如果沒有實(shí)現(xiàn)Cloneable接口的實(shí)例上調(diào)用Obejct.clone()方法，會(huì)拋出CloneNotSupportException異常。正常情況下，實(shí)現(xiàn)了Cloneable接口的類會(huì)以公共方法重寫Object.clone()
  • Serializable 接口：實(shí)現(xiàn)了該接口標(biāo)示了類可以被序列化和反序列化，具體的 查詢序列化詳解
  • Deque 接口：Deque定義了一個(gè)線性Collection，支持在兩端插入和刪除元素，Deque實(shí)際是“double ended queue(雙端隊(duì)列)”的簡(jiǎn)稱，大多數(shù)Deque接口的實(shí)現(xiàn)都不會(huì)限制元素的數(shù)量，但是這個(gè)隊(duì)列既支持有容量限制的實(shí)現(xiàn)，也支持沒有容量限制的實(shí)現(xiàn)，比如LinkedList就是有容量限制的實(shí)現(xiàn),其最大的容量為Integer.MAX_VALUE
  • AbstractSequentialList 類：提供了List接口的骨干實(shí)現(xiàn)，最大限度地減少了實(shí)現(xiàn)受“連續(xù)訪問”數(shù)據(jù)存儲(chǔ)(如鏈表)支持的此接口所需的工作，對(duì)于隨機(jī)訪問數(shù)據(jù)(如數(shù)組)，應(yīng)該優(yōu)先使用 AbstractList，而不是使用AbstractSequentailList類

二、底層源碼分析

LinkedList是通過雙向鏈表去實(shí)現(xiàn)的，既然是鏈表實(shí)現(xiàn)那么它的隨機(jī)訪問效率比ArrayList要低，順序訪問的效率要比較的高。每個(gè)節(jié)點(diǎn)都有一個(gè)前驅(qū)(之前前面節(jié)點(diǎn)的指針)和一個(gè)后繼(指向后面節(jié)點(diǎn)的指針)

效果如下圖：

源碼標(biāo)注如下：

 
 
 
 
      
  
  
  
  1. public class LinkedListextends AbstractSequentialList 
    2.   
  
  
  
  2.     implements List, Deque, Cloneable, java.io.Serializable 
    3.   
  
  
  
  3. { 
    4.   
  
  
  
  4.     transient int size = 0;   //LinkedList中存放的元素個(gè)數(shù) 
    5.   
  
  
  
  5.     transient Node first;  //頭節(jié)點(diǎn) 
    6.   
  
  
  
  6.     transient Node last;   //尾節(jié)點(diǎn) 
    7.   
  
  
  
  7.     //構(gòu)造方法，創(chuàng)建一個(gè)空的列表 
    8.   
  
  
  
  8.     public LinkedList() { 
    9.   
  
  
  
  9.     } 
    10.   
  
  
  
  10.     //將一個(gè)指定的集合添加到LinkedList中，先完成初始化，在調(diào)用添加操作 
    11.   
  
  
  
  11.     public LinkedList(Collection c) { 
    12.   
  
  
  
  12.         this(); 
    13.   
  
  
  
  13.         addAll(c); 
    14.   
  
  
  
  14.     } 
    15.   
  
  
  
  15.     //插入頭節(jié)點(diǎn) 
    16.   
  
  
  
  16.     private void linkFirst(E e) { 
    17.   
  
  
  
  17.         final Node f = first;  //將頭節(jié)點(diǎn)賦值給f節(jié)點(diǎn) 
    18.   
  
  
  
  18.         //new 一個(gè)新的節(jié)點(diǎn)，此節(jié)點(diǎn)的data = e , pre = null , next - > f  
    19.   
  
  
  
  19.         final Node newNode = new Node<>(null, e, f); 
    20.   
  
  
  
  20.         first = newNode; //將新創(chuàng)建的節(jié)點(diǎn)地址復(fù)制給first 
    21.   
  
  
  
  21.         if (f == null)  //f == null，表示此時(shí)LinkedList為空 
    22.   
  
  
  
  22.             last = newNode;  //將新創(chuàng)建的節(jié)點(diǎn)賦值給last 
    23.   
  
  
  
  23.         else 
    24.   
  
  
  
  24.             f.prev = newNode;  //否則f.前驅(qū)指向newNode 
    25.   
  
  
  
  25.         size++; 
    26.   
  
  
  
  26.         modCount++; 
    27.   
  
  
  
  27.     } 
    28.   
  
  
  
  28.     //插入尾節(jié)點(diǎn) 
    29.   
  
  
  
  29.     void linkLast(E e) { 
    30.   
  
  
  
  30.         final Node l = last;  
    31.   
  
  
  
  31.         final Node newNode = new Node<>(l, e, null); 
    32.   
  
  
  
  32.         last = newNode; 
    33.   
  
  
  
  33.         if (l == null) 
    34.   
  
  
  
  34.             first = newNode; 
    35.   
  
  
  
  35.         else 
    36.   
  
  
  
  36.             l.next = newNode; 
    37.   
  
  
  
  37.         size++; 
    38.   
  
  
  
  38.         modCount++; 
    39.   
  
  
  
  39.     } 
    40.   
  
  
  
  40.     //在succ節(jié)點(diǎn)前插入e節(jié)點(diǎn)，并修改各個(gè)節(jié)點(diǎn)之間的前驅(qū)后繼 
    41.   
  
  
  
  41.     void linkBefore(E e, Node succ) { 
    42.   
  
  
  
  42.         // assert succ != null; 
    43.   
  
  
  
  43.         final Node pred = succ.prev; 
    44.   
  
  
  
  44.         final Node newNode = new Node<>(pred, e, succ); 
    45.   
  
  
  
  45.         succ.prev = newNode; 
    46.   
  
  
  
  46.         if (pred == null) 
    47.   
  
  
  
  47.             first = newNode; 
    48.   
  
  
  
  48.         else 
    49.   
  
  
  
  49.             pred.next = newNode; 
    50.   
  
  
  
  50.         size++; 
    51.   
  
  
  
  51.         modCount++; 
    52.   
  
  
  
  52.     } 
    53.   
  
  
  
  53.     //刪除頭節(jié)點(diǎn) 
    54.   
  
  
  
  54.     private E unlinkFirst(Node f) { 
    55.   
  
  
  
  55.         // assert f == first && f != null; 
    56.   
  
  
  
  56.         final E element = f.item; 
    57.   
  
  
  
  57.         final Node next = f.next; 
    58.   
  
  
  
  58.         f.item = null; 
    59.   
  
  
  
  59.         f.next = null; // help GC 
    60.   
  
  
  
  60.         first = next; 
    61.   
  
  
  
  61.         if (next == null) 
    62.   
  
  
  
  62.             last = null; 
    63.   
  
  
  
  63.         else 
    64.   
  
  
  
  64.             next.prev = null; 
    65.   
  
  
  
  65.         size--; 
    66.   
  
  
  
  66.         modCount++; 
    67.   
  
  
  
  67.         return element; 
    68.   
  
  
  
  68.     } 
    69.   
  
  
  
  69.     //刪除尾節(jié)點(diǎn) 
    70.   
  
  
  
  70.     private E unlinkLast(Node l) { 
    71.   
  
  
  
  71.         // assert l == last && l != null; 
    72.   
  
  
  
  72.         final E element = l.item; 
    73.   
  
  
  
  73.         final Node prev = l.prev; 
    74.   
  
  
  
  74.         l.item = null; 
    75.   
  
  
  
  75.         l.prev = null; // help GC 
    76.   
  
  
  
  76.         last = prev; 
    77.   
  
  
  
  77.         if (prev == null) 
    78.   
  
  
  
  78.             first = null; 
    79.   
  
  
  
  79.         else 
    80.   
  
  
  
  80.             prev.next = null; 
    81.   
  
  
  
  81.         size--; 
    82.   
  
  
  
  82.         modCount++; 
    83.   
  
  
  
  83.         return element; 
    84.   
  
  
  
  84.     } 
    85.   
  
  
  
  85.     //刪除指定節(jié)點(diǎn) 
    86.   
  
  
  
  86.     E unlink(Node x) { 
    87.   
  
  
  
  87.         // assert x != null; 
    88.   
  
  
  
  88.         final E element = x.item; 
    89.   
  
  
  
  89.         final Node next = x.next;  //獲取指定節(jié)點(diǎn)的前驅(qū) 
    90.   
  
  
  
  90.         final Node prev = x.prev;  //獲取指定節(jié)點(diǎn)的后繼 
    91.   
  
  
  
  91.         if (prev == null) { 
    92.   
  
  
  
  92.             first = next;   //如果前驅(qū)為null, 說明此節(jié)點(diǎn)為頭節(jié)點(diǎn) 
    93.   
  
  
  
  93.         } else { 
    94.   
  
  
  
  94.             prev.next = next;  //前驅(qū)結(jié)點(diǎn)的后繼節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn) 
    95.   
  
  
  
  95.             x.prev = null;     //當(dāng)前節(jié)點(diǎn)的前驅(qū)置空 
    96.   
  
  
  
  96.         } 
    97.   
  
  
  
  97.         if (next == null) {    //如果當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)為null ,說明此節(jié)點(diǎn)為尾節(jié)點(diǎn) 
    98.   
  
  
  
  98.             last = prev; 
    99.   
  
  
  
  99.         } else { 
    100.   
  
  
  
  100.             next.prev = prev;  //當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)的前驅(qū)指向當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn) 
    101.   
  
  
  
  101.             x.next = null;     //當(dāng)前節(jié)點(diǎn)的后繼置空 
    102.   
  
  
  
  102.         } 
    103.   
  
  
  
  103.         x.item = null;     //當(dāng)前節(jié)點(diǎn)的元素設(shè)置為null ,等待垃圾回收 
    104.   
  
  
  
  104.         size--; 
    105.   
  
  
  
  105.         modCount++; 
    106.   
  
  
  
  106.         return element; 
    107.   
  
  
  
  107.     } 
    108.   
  
  
  
  108.     //獲取LinkedList中的第一個(gè)節(jié)點(diǎn)信息 
    109.   
  
  
  
  109.     public E getFirst() { 
    110.   
  
  
  
  110.         final Node f = first; 
    111.   
  
  
  
  111.         if (f == null) 
    112.   
  
  
  
  112.             throw new NoSuchElementException(); 
    113.   
  
  
  
  113.         return f.item; 
    114.   
  
  
  
  114.     } 
    115.   
  
  
  
  115.     //獲取LinkedList中的最后一個(gè)節(jié)點(diǎn)信息 
    116.   
  
  
  
  116.     public E getLast() { 
    117.   
  
  
  
  117.         final Node l = last; 
    118.   
  
  
  
  118.         if (l == null) 
    119.   
  
  
  
  119.             throw new NoSuchElementException(); 
    120.   
  
  
  
  120.         return l.item; 
    121.   
  
  
  
  121.     } 
    122.   
  
  
  
  122.     //刪除頭節(jié)點(diǎn) 
    123.   
  
  
  
  123.     public E removeFirst() { 
    124.   
  
  
  
  124.         final Node f = first; 
    125.   
  
  
  
  125.         if (f == null) 
    126.   
  
  
  
  126.             throw new NoSuchElementException(); 
    127.   
  
  
  
  127.         return unlinkFirst(f); 
    128.   
  
  
  
  128.     } 
    129.   
  
  
  
  129.     //刪除尾節(jié)點(diǎn) 
    130.   
  
  
  
  130.     public E removeLast() { 
    131.   
  
  
  
  131.         final Node l = last; 
    132.   
  
  
  
  132.         if (l == null) 
    133.   
  
  
  
  133.             throw new NoSuchElementException(); 
    134.   
  
  
  
  134.         return unlinkLast(l); 
    135.   
  
  
  
  135.     } 
    136.   
  
  
  
  136.     //將添加的元素設(shè)置為L(zhǎng)inkedList的頭節(jié)點(diǎn) 
    137.   
  
  
  
  137.     public void addFirst(E e) { 
    138.   
  
  
  
  138.         linkFirst(e); 
    139.   
  
  
  
  139.     } 
    140.   
  
  
  
  140.     //將添加的元素設(shè)置為L(zhǎng)inkedList的尾節(jié)點(diǎn) 
    141.   
  
  
  
  141.     public void addLast(E e) { 
    142.   
  
  
  
  142.         linkLast(e); 
    143.   
  
  
  
  143.     } 
    144.   
  
  
  
  144.     //判斷LinkedList是否包含指定的元素 
    145.   
  
  
  
  145.     public boolean contains(Object o) { 
    146.   
  
  
  
  146.         return indexOf(o) != -1; 
    147.   
  
  
  
  147.     } 
    148.   
  
  
  
  148.     //返回List中元素的數(shù)量 
    149.   
  
  
  
  149.     public int size() { 
    150.   
  
  
  
  150.         return size; 
    151.   
  
  
  
  151.     } 
    152.   
  
  
  
  152.     //在LinkedList的尾部添加元素 
    153.   
  
  
  
  153.     public boolean add(E e) { 
    154.   
  
  
  
  154.         linkLast(e); 
    155.   
  
  
  
  155.         return true; 
    156.   
  
  
  
  156.     } 
    157.   
  
  
  
  157.     //刪除指定的元素 
    158.   
  
  
  
  158.     public boolean remove(Object o) { 
    159.   
  
  
  
  159.         if (o == null) { 
    160.   
  
  
  
  160.             for (Node x = first; x != null; x = x.next) { 
    161.   
  
  
  
  161.                 if (x.item == null) { 
    162.   
  
  
  
  162.                     unlink(x); 
    163.   
  
  
  
  163.                     return true; 
    164.   
  
  
  
  164.                 } 
    165.   
  
  
  
  165.             } 
    166.   
  
  
  
  166.         } else { 
    167.   
  
  
  
  167.             for (Node x = first; x != null; x = x.next) { 
    168.   
  
  
  
  168.                 if (o.equals(x.item)) { 
    169.   
  
  
  
  169.                     unlink(x); 
    170.   
  
  
  
  170.                     return true; 
    171.   
  
  
  
  171.                 } 
    172.   
  
  
  
  172.             } 
    173.   
  
  
  
  173.         } 
    174.   
  
  
  
  174.         return false; 
    175.   
  
  
  
  175.     } 
    176.   
  
  
  
  176.     //將集合中的元素添加到List中 
    177.   
  
  
  
  177.     public boolean addAll(Collection c) { 
    178.   
  
  
  
  178.         return addAll(size, c); 
    179.   
  
  
  
  179.     } 
    180.   
  
  
  
  180.     //將集合中的元素全部插入到List中，并從指定的位置開始 
    181.   
  
  
  
  181.     public boolean addAll(int index, Collection c) { 
    182.   
  
  
  
  182.         checkPositionIndex(index); 
    183.   
  
  
  
  183.         Object[] a = c.toArray();  //將集合轉(zhuǎn)化為數(shù)組 
    184.   
  
  
  
  184.         int numNew = a.length;  //獲取集合中元素的數(shù)量 
    185.   
  
  
  
  185.         if (numNew == 0)   //集合中沒有元素，返回false 
    186.   
  
  
  
  186.             return false; 
    187.   
  
  
  
  187.         Node pred, succ; 
    188.   
  
  
  
  188.         if (index == size) { 
    189.   
  
  
  
  189.             succ = null; 
    190.   
  
  
  
  190.             pred = last; 
    191.   
  
  
  
  191.         } else { 
    192.   
  
  
  
  192.             succ = node(index); //獲取位置為index的結(jié)點(diǎn)元素，并賦值給succ 
    193.   
  
  
  
  193.             pred = succ.prev; 
    194.   
  
  
  
  194.         } 
    195.   
  
  
  
  195.         for (Object o : a) {  //遍歷數(shù)組進(jìn)行插入操作。修改節(jié)點(diǎn)的前驅(qū)后繼 
    196.   
  
  
  
  196.             @SuppressWarnings("unchecked") E e = (E) o; 
    197.   
  
  
  
  197.             Node newNode = new Node<>(pred, e, null); 
    198.   
  
  
  
  198.             if (pred == null) 
    199.   
  
  
  
  199.                 first = newNode; 
    200.   
  
  
  
  200.             else 
    201.   
  
  
  
  201.                 pred.next = newNode; 
    202.   
  
  
  
  202.             pred = newNode; 
    203.   
  
  
  
  203.         } 
    204.   
  
  
  
  204.         if (succ == null) { 
    205.   
  
  
  
  205.             last = pred; 
    206.   
  
  
  
  206.         } else { 
    207.   
  
  
  
  207.             pred.next = succ; 
    208.   
  
  
  
  208.             succ.prev = pred; 
    209.   
  
  
  
  209.         } 
    210.   
  
  
  
  210.         size += numNew; 
    211.   
  
  
  
  211.         modCount++; 
    212.   
  
  
  
  212.         return true; 
    213.   
  
  
  
  213.     } 
    214.   
  
  
  
  214.     //刪除List中所有的元素 
    215.   
  
  
  
  215.     public void clear() { 
    216.   
  
  
  
  216.         // Clearing all of the links between nodes is "unnecessary", but: 
    217.   
  
  
  
  217.         // - helps a generational GC if the discarded nodes inhabit 
    218.   
  
  
  
  218.         //   more than one generation 
    219.   
  
  
  
  219.         // - is sure to free memory even if there is a reachable Iterator 
    220.   
  
  
  
  220.         for (Node x = first; x != null; ) { 
    221.   
  
  
  
  221.             Node next = x.next; 
    222.   
  
  
  
  222.             x.item = null; 
    223.   
  
  
  
  223.             x.next = null; 
    224.   
  
  
  
  224.             x.prev = null; 
    225.   
  
  
  
  225.             x = next; 
    226.   
  
  
  
  226.         } 
    227.   
  
  
  
  227.         first = last = null; 
    228.   
  
  
  
  228.         size = 0; 
    229.   
  
  
  
  229.         modCount++; 
    230.   
  
  
  
  230.     } 
    231.   
  
  
  
  231.     //獲取指定位置的元素 
    232.   
  
  
  
  232.     public E get(int index) { 
    233.   
  
  
  
  233.         checkElementIndex(index); 
    234.   
  
  
  
  234.         return node(index).item; 
    235.   
  
  
  
  235.     } 
    236.   
  
  
  
  236.     //將節(jié)點(diǎn)防止在指定的位置 
    237.   
  
  
  
  237.     public E set(int index, E element) { 
    238.   
  
  
  
  238.         checkElementIndex(index); 
    239.   
  
  
  
  239.         Node x = node(index); 
    240.   
  
  
  
  240.         E oldVal = x.item; 
    241.   
  
  
  
  241.         x.item = element; 
    242.   
  
  
  
  242.         return oldVal; 
    243.   
  
  
  
  243.     } 
    244.   
  
  
  
  244.     //將節(jié)點(diǎn)放置在指定的位置 
    245.   
  
  
  
  245.     public void add(int index, E element) { 
    246.   
  
  
  
  246.         checkPositionIndex(index); 
    247.   
  
  
  
  247.         if (index == size) 
    248.   
  
  
  
  248.             linkLast(element); 
    249.   
  
  
  
  249.         else 
    250.   
  
  
  
  250.             linkBefore(element, node(index)); 
    251.   
  
  
  
  251.     } 
    252.   
  
  
  
  252.     //刪除指定位置的元素 
    253.   
  
  
  
  253.     public E remove(int index) { 
    254.   
  
  
  
  254.         checkElementIndex(index); 
    255.   
  
  
  
  255.         return unlink(node(index)); 
    256.   
  
  
  
  256.     } 
    257.   
  
  
  
  257.     //判斷索引是否合法 
    258.   
  
  
  
  258.     private boolean isElementIndex(int index) { 
    259.   
  
  
  
  259.         return index >= 0 && index < size; 
    260.   
  
  
  
  260.     } 
    261.   
  
  
  
  261.     //判斷位置是否合法 
    262.   
  
  
  
  262.     private boolean isPositionIndex(int index) { 
    263.   
  
  
  
  263.         return index >= 0 && index <= size; 
    264.   
  
  
  
  264.     } 
    265.   
  
  
  
  265.     //索引溢出信息 
    266.   
  
  
  
  266.     private String outOfBoundsMsg(int index) { 
    267.   
  
  
  
  267.         return "Index: "+index+", Size: "+size; 
    268.   
  
  
  
  268.     } 
    269.   
  
  
  
  269.     //檢查節(jié)點(diǎn)是否合法 
    270.   
  
  
  
  270.     private void checkElementIndex(int index) { 
    271.   
  
  
  
  271.         if (!isElementIndex(index)) 
    272.   
  
  
  
  272.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 
    273.   
  
  
  
  273.     } 
    274.   
  
  
  
  274.     //檢查位置是否合法 
    275.   
  
  
  
  275.     private void checkPositionIndex(int index) { 
    276.   
  
  
  
  276.         if (!isPositionIndex(index)) 
    277.   
  
  
  
  277.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 
    278.   
  
  
  
  278.     } 
    279.   
  
  
  
  279.     //返回指定位置的節(jié)點(diǎn)信息 
    280.   
  
  
  
  280.     //LinkedList無法隨機(jī)訪問，只能通過遍歷的方式找到相應(yīng)的節(jié)點(diǎn) 
    281.   
  
  
  
  281.     //為了提高效率，當(dāng)前位置首先和元素?cái)?shù)量的中間位置開始判斷，小于中間位置， 
    282.   
  
  
  
  282.     //從頭節(jié)點(diǎn)開始遍歷，大于中間位置從尾節(jié)點(diǎn)開始遍歷 
    283.   
  
  
  
  283.     Node node(int index) { 
    284.   
  
  
  
  284.         // assert isElementIndex(index); 
    285.   
  
  
  
  285.         if (index < (size >> 1)) { 
    286.   
  
  
  
  286.             Node x = first; 
    287.   
  
  
  
  287.             for (int i = 0; i < index; i++) 
    288.   
  
  
  
  288.                 x = x.next; 
    289.   
  
  
  
  289.             return x; 
    290.   
  
  
  
  290.         } else { 
    291.   
  
  
  
  291.             Node x = last; 
    292.   
  
  
  
  292.             for (int i = size - 1; i > index; i--) 
    293.   
  
  
  
  293.                 x = x.prev; 
    294.   
  
  
  
  294.             return x; 
    295.   
  
  
  
  295.         } 
    296.   
  
  
  
  296.     } 
    297.   
  
  
  
  297.     //返回第一次出現(xiàn)指定元素的位置 
    298.   
  
  
  
  298.     public int indexOf(Object o) { 
    299.   
  
  
  
  299.         int index = 0; 
    300.   
  
  
  
  300.         if (o == null) { 
    301.   
  
  
  
  301.             for (Node x = first; x != null; x = x.next) { 
    302.   
  
  
  
  302.                 if (x.item == null) 
    303.   
  
  
  
  303.                     return index; 
    304.   
  
  
  
  304.                 index++; 
    305.   
  
  
  
  305.             } 
    306.   
  
  
  
  306.         } else { 
    307.   
  
  
  
  307.             for (Node x = first; x != null; x = x.next) { 
    308.   
  
  
  
  308.                 if (o.equals(x.item)) 
    309.   
  
  
  
  309.                     return index; 
    310.   
  
  
  
  310.                 index++; 
    311.   
  
  
  
  311.             } 
    312.   
  
  
  
  312.         } 
    313.   
  
  
  
  313.         return -1; 
    314.   
  
  
  
  314.     } 
    315.   
  
  
  
  315.     //返回最后一次出現(xiàn)元素的位置 
    316.   
  
  
  
  316.     public int lastIndexOf(Object o) { 
    317.   
  
  
  
  317.         int index = size; 
    318.   
  
  
  
  318.         if (o == null) { 
    319.   
  
  
  
  319.             for (Node x = last; x != null; x = x.prev) { 
    320.   
  
  
  
  320.                 index--; 
    321.   
  
  
  
  321.                 if (x.item == null) 
    322.   
  
  
  
  322.                     return index; 
    323.   
  
  
  
  323.             } 
    324.   
  
  
  
  324.         } else { 
    325.   
  
  
  
  325.             for (Node x = last; x != null; x = x.prev) { 
    326.   
  
  
  
  326.                 index--; 
    327.   
  
  
  
  327.                 if (o.equals(x.item)) 
    328.   
  
  
  
  328.                     return index; 
    329.   
  
  
  
  329.             } 
    330.   
  
  
  
  330.         } 
    331.   
  
  
  
  331.         return -1; 
    332.   
  
  
  
  332.     } 
    333.   
  
  
  
  333.     //彈出第一個(gè)元素的值 
    334.   
  
  
  
  334.     public E peek() { 
    335.   
  
  
  
  335.         final Node f = first; 
    336.   
  
  
  
  336.         return (f == null) ? null : f.item; 
    337.   
  
  
  
  337.     } 
    338.   
  
  
  
  338.     //獲取第一個(gè)元素 
    339.   
  
  
  
  339.     public E element() { 
    340.   
  
  
  
  340.         return getFirst(); 
    341.   
  
  
  
  341.     } 
    342.   
  
  
  
  342.     //彈出第一元素，并刪除 
    343.   
  
  
  
  343.     public E poll() { 
    344.   
  
  
  
  344.         final Node f = first; 
    345.   
  
  
  
  345.         return (f == null) ? null : unlinkFirst(f); 
    346.   
  
  
  
  346.     } 
    347.   
  
  
  
  347.     //刪除第一個(gè)元素 
    348.   
  
  
  
  348.     public E remove() { 
    349.   
  
  
  
  349.         return removeFirst(); 
    350.   
  
  
  
  350.     } 
    351.   
  
  
  
  351.     //添加到尾部 
    352.   
  
  
  
  352.     public boolean offer(E e) { 
    353.   
  
  
  
  353.         return add(e); 
    354.   
  
  
  
  354.     } 
    355.   
  
  
  
  355.     //添加到頭部 
    356.   
  
  
  
  356.     public boolean offerFirst(E e) { 
    357.   
  
  
  
  357.         addFirst(e); 
    358.   
  
  
  
  358.         return true; 
    359.   
  
  
  
  359.     } 
    360.   
  
  
  
  360.     //插入到最后一個(gè)元素 
    361.   
  
  
  
  361.     public boolean offerLast(E e) { 
    362.   
  
  
  
  362.         addLast(e); 
    363.   
  
  
  
  363.         return true; 
    364.   
  
  
  
  364.     } 
    365.   
  
  
  
  365.     //隊(duì)列操作 
    366.   
  
  
  
  366.     //嘗試彈出第一個(gè)元素，但是不刪除元素 
    367.   
  
  
  
  367.     public E peekFirst() { 
    368.   
  
  
  
  368.         final Node f = first; 
    369.   
  
  
  
  369.         return (f == null) ? null : f.item; 
    370.   
  
  
  
  370.      } 
    371.   
  
  
  
  371.     //隊(duì)列操作 
    372.   
  
  
  
  372.     //嘗試彈出最后一個(gè)元素，不刪除 
    373.   
  
  
  
  373.     public E peekLast() { 
    374.   
  
  
  
  374.         final Node l = last; 
    375.   
  
  
  
  375.         return (l == null) ? null : l.item; 
    376.   
  
  
  
  376.     } 
    377.   
  
  
  
  377.     //彈出第一個(gè)元素，并刪除 
    378.   
  
  
  
  378.     public E pollFirst() { 
    379.   
  
  
  
  379.         final Node f = first; 
    380.   
  
  
  
  380.         return (f == null) ? null : unlinkFirst(f); 
    381.   
  
  
  
  381.     } 
    382.   
  
  
  
  382.     //彈出最后一個(gè)元素，并刪除 
    383.   
  
  
  
  383.     public E pollLast() { 
    384.   
  
  
  
  384.         final Node l = last; 
    385.   
  
  
  
  385.         return (l == null) ? null : unlinkLast(l); 
    386.   
  
  
  
  386.     } 
    387.   
  
  
  
  387.     //如隊(duì)列，添加到頭部 
    388.   
  
  
  
  388.     public void push(E e) { 
    389.   
  
  
  
  389.         addFirst(e); 
    390.   
  
  
  
  390.     } 
    391.   
  
  
  
  391.     //出隊(duì)列刪除第一個(gè)節(jié)點(diǎn) 
    392.   
  
  
  
  392.     public E pop() { 
    393.   
  
  
  
  393.         return removeFirst(); 
    394.   
  
  
  
  394.     } 
    395.   
  
  
  
  395.    //刪除指定元素第一次出現(xiàn)的位置 
    396.   
  
  
  
  396.     public boolean removeFirstOccurrence(Object o) { 
    397.   
  
  
  
  397.         return remove(o); 
    398.   
  
  
  
  398.     } 
    399.   
  
  
  
  399.     //刪除指定元素最后一次出現(xiàn)的位置 
    400.   
  
  
  
  400.     public boolean removeLastOccurrence(Object o) { 
    401.   
  
  
  
  401.         if (o == null) { 
    402.   
  
  
  
  402.             for (Node x = last; x != null; x = x.prev) { 
    403.   
  
  
  
  403.                 if (x.item == null) { 
    404.   
  
  
  
  404.                     unlink(x); 
    405.   
  
  
  
  405.                     return true; 
    406.   
  
  
  
  406.                 } 
    407.   
  
  
  
  407.             } 
    408.   
  
  
  
  408.         } else { 
    409.   
  
  
  
  409.             for (Node x = last; x != null; x = x.prev) { 
    410.   
  
  
  
  410.                                                  
    
                                                文章題目：數(shù)據(jù)結(jié)構(gòu)之LinkedList底層實(shí)現(xiàn)和原理詳解                                                
    
                                                本文來源：http://m.5511xx.com/article/cdicepo.html