国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

《JavaSE-第十七章》之LinkedList

2年前作者：瀟瀟雨聲遲分類：Toy博客閱讀(25)違法舉報

這篇具有很好參考價值的文章主要介紹了《JavaSE-第十七章》之LinkedList。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

前言

在你立足處深挖下去,就會有泉水涌出!別管蒙昧者們叫嚷:“下邊永遠(yuǎn)是地獄!”

博客主頁：KC老衲愛尼姑的博客主頁

博主的github，平常所寫代碼皆在于此

刷題求職神器

共勉：talk is cheap, show me the code

作者是爪哇島的新手，水平很有限，如果發(fā)現(xiàn)錯誤，一定要及時告知作者哦！感謝感謝！

LinkedList概述

LinkedList底層是基于雙鏈表實現(xiàn),內(nèi)部使用節(jié)點存儲數(shù)據(jù),相比于數(shù)組而言,LinkedList刪除和插入元素的效率遠(yuǎn)高于數(shù)組,而查找和修改的效率比數(shù)組要低。

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

《JavaSE-第十七章》之LinkedList,Java,java,數(shù)據(jù)結(jié)構(gòu),開發(fā)語言

LinkedList的繼承關(guān)系

《JavaSE-第十七章》之LinkedList,Java,java,數(shù)據(jù)結(jié)構(gòu),開發(fā)語言

說明

  1. LinkedList實現(xiàn)了List接口,說明LinkedList可以當(dāng)做一個順序存儲的容器
  2. LinkedList實現(xiàn)了Queue接口,說明LinedList可以當(dāng)做一個隊列使用
  3. LinkedList實現(xiàn)了Serializable,說明支持序列化
  4. LinkedList是實現(xiàn)了Cloneable,說明支持克隆

屬性

    //記錄鏈表長度
    transient int size = 0;

  	//頭指針
    transient Node<E> first;

	//尾指針
    transient Node<E> last;

構(gòu)造方法

無參構(gòu)造
public LinkedList() {
 }
有參構(gòu)造
   public LinkedList(Collection<? extends E> c) {
        this();
        //將集合中的元素添加到鏈表中
        addAll(c);
    }
//將指定集合中的元素添加到鏈表中
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        //檢查index是否合法
        checkPositionIndex(index);
		//將結(jié)合轉(zhuǎn)換成數(shù)組
        Object[] a = c.toArray();
        //得到數(shù)組的長度
        int numNew = a.length;
        //判讀數(shù)組長度是否為0
        if (numNew == 0)
            return false;
		//定義一個節(jié)點pred為前驅(qū),succ為后繼
        Node<E> pred, succ;
        //數(shù)組長度如果等于鏈表長度,向鏈表尾部添加元素
        if (index == size) {
            succ = null;//將后繼置空
            pred = last;//將鏈表的最后一個節(jié)點的引用賦值給pred
        } else {
            //index不等于size,則說明是插入鏈表中間位置
            succ = node(index);//index位置節(jié)點的引用
            pred = succ.prev;//index位置前一個節(jié)點的引用
        }
		//遍歷數(shù)組,每遍歷一個數(shù)組元素,就創(chuàng)建一個節(jié)點,再將它插入鏈表相應(yīng)位置
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;//強制類型轉(zhuǎn)換
            Node<E> newNode = new Node<>(pred, e, null);//構(gòu)造節(jié)點
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;//插入元素
            //更新pred為新節(jié)點的引用
            pred = newNode;
        }
		
        if (succ == null) {
            //如果是從尾部開始插入的，讓last指向最后一個插入的節(jié)點
            last = pred;
        } else {
             //如果不是從尾部插入的，則把尾部的數(shù)據(jù)和之前的節(jié)點連起來
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;//更新鏈表長度
        modCount++;
        return true;
    }

內(nèi)部類Node

    private static class Node<E> {
        E item;//鏈表中的數(shù)據(jù)域
        Node<E> next;//記錄當(dāng)前節(jié)點的后一個節(jié)點的引用
        Node<E> prev;//記錄當(dāng)前節(jié)點的前一個節(jié)點的引用

        Node(Node<E> prev, E element, Node<E> next) {//初始化節(jié)點
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

LinkedLsit特有方法

源碼如下

1.addFirst()

    public void addFirst(E e) {
        linkFirst(e);
    }
    //頭插
     private void linkFirst(E e) {
        final Node<E> f = first;//獲取到頭節(jié)點的引用
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;//更新first的指向
        if (f == null)//如果為空則說明鏈表為空
            last = newNode;//讓尾指針指向新節(jié)點
        else
            f.prev = newNode;//
        size++;//長度自增
        modCount++;
    }

代碼示例

public class Demo {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.addFirst(1);
        list.addFirst(2);
        list.addFirst(3);
        System.out.println(list);
    }
}
//運行結(jié)果
//[3, 2, 1]

圖解頭插

《JavaSE-第十七章》之LinkedList,Java,java,數(shù)據(jù)結(jié)構(gòu),開發(fā)語言

2.addLast()

源碼如下

public void addLast(E e) {
        linkLast(e);//尾插
}
 //尾插具體實現(xiàn)
  void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
}

代碼示例

public class Demo {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        System.out.println(list);
    }
}
//運行結(jié)果
//[1, 2, 3]

圖解尾插

《JavaSE-第十七章》之LinkedList,Java,java,數(shù)據(jù)結(jié)構(gòu),開發(fā)語言

3.getFirst()

源碼如下

  public E getFirst() {
        final Node<E> f = first;//得到first引用
        if (f == null)//鏈表中無節(jié)點
            throw new NoSuchElementException();//拋出異常
        return f.item;//返回頭節(jié)點的數(shù)據(jù)
    }

4.getLast()

源碼如下

public E getLast() {
        final Node<E> l = last;//得到last引用
        if (l == null)//鏈表中無節(jié)點
            throw new NoSuchElementException();//拋出異常
        return l.item;//返回頭節(jié)點的數(shù)據(jù)
    }

5.removeFirst()

源碼如下

     public E removeFirst() {
        final Node<E> f = first;//得到頭節(jié)點的引用
        if (f == null)//如果為null則沒有頭節(jié)點
            throw new NoSuchElementException();//拋出異常
        return unlinkFirst(f);//刪除操作
      }
	  //刪除鏈表第一個節(jié)點
      private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;//得到頭節(jié)點的數(shù)據(jù)
        final Node<E> next = f.next;//得到第二個節(jié)點的引用
        f.item = null;//將頭節(jié)點數(shù)據(jù)域置空
        f.next = null; //將頭節(jié)點next域置空
        first = next;//更新first指針的指向
        if (next == null)//next等于null,說明只有一個節(jié)點
            last = null;
        else
            next.prev = null;//將第二個節(jié)點的preve置空
        size--;//長度-1
        modCount++;
        return element;//返回要刪除頭節(jié)點的數(shù)據(jù)
    }

6.removeLast()

源碼如下

  public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();//拋出異常
        return unlinkLast(l);
    }
     //刪除鏈表最后個節(jié)點
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

List接口

核心方法

1.add(E e)

源碼如下

  public boolean add(E e) {
        linkLast(e);
        return true;
    }
   //尾插
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

2.add(int index, E element)

源碼如下

  public void add(int index, E element) {
        checkPositionIndex(index);//檢查index合法性

        if (index == size)//如果相等,插入到尾部
            linkLast(element);//尾插
        else//非尾部位置
            linkBefore(element, node(index));//
    }
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

	private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

   void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

   void linkBefore(E e, Node<E> succ) {
        //succ為要插入位置的節(jié)點,同時也是你要插入該位置節(jié)點的后繼
        final Node<E> pred = succ.prev;//得到插入位置的前驅(qū)
        final Node<E> newNode = new Node<>(pred, e, succ);//將元素,以及前驅(qū)和后繼傳入
        succ.prev = newNode;//更新插入位置節(jié)點的前驅(qū)為要插入節(jié)點的引用
        if (pred == null)//如果pred為空說明,要插入的節(jié)點已經(jīng)跑到頭節(jié)點之前了,需要重置頭節(jié)點
            first = newNode;
        else
            pred.next = newNode;//否則的話將pred的next域指向新節(jié)點即可
        size++;
        modCount++;
    }

    //尋找指定位置的節(jié)點
    Node<E> node(int index) {
       //如果index靠近鏈表的前部分,則從頭開始遍歷尋找要找的節(jié)點
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {//靠近后半部分,則倒著尋找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

3.remove(int index)

源碼如下

  public E remove(int index) {
        checkElementIndex(index);//檢查index合法性
        return unlink(node(index));
    }
	//刪除index位置的具體操作
   E unlink(Node<E> x) {
        
        final E element = x.item;//要刪除節(jié)點的值
        final Node<E> next = x.next;//要刪除節(jié)點的后一個節(jié)點的引用
        final Node<E> prev = x.prev;//要刪除節(jié)點的前一個節(jié)點
		//如果prev為空意味著刪除的節(jié)點是頭節(jié)點,否則就不是頭節(jié)點
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;//要刪除的節(jié)點prev域置空
        }
		//如果prev為空意味著刪除的節(jié)點是尾節(jié)點,否則就不是尾節(jié)點
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;//要刪除的節(jié)點next域置空
        }

        x.item = null;//將要刪除節(jié)點的數(shù)據(jù)域置空
        size--;//鏈表的長度減一
        modCount++;
        return element;//返回刪除節(jié)點的數(shù)據(jù)域的值
    }

4.get(int index)

源碼如下

   public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    //尋找指定位置的節(jié)點
    Node<E> node(int index) {
       //如果index靠近鏈表的前部分,則從頭開始遍歷尋找要找的節(jié)點
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {//靠近后半部分,則倒著尋找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

5.set(int index, E element)

源碼如下

    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

   Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

上述的get()和set()方法中的node()方法是以二分查找來看index位置距離size的一半位置,在決定從頭遍歷還是從尾遍歷。以o(n/2)的效率得到一個節(jié)點。

6.indexOf(Object o)

源碼如下

//從頭往尾找該元素第一次出現(xiàn)的下標(biāo)
    public int indexOf(Object o) {
        int index = 0;
        //元素為null
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            //元素不為null
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;//在鏈表中找不到
    }

7.lastIndexOf(Object o)

源碼如下

//從尾往頭找該元素第一次出現(xiàn)的下標(biāo)
    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

8.clear()

源碼如下

    //清空鏈表
    public void clear() {
		//遍歷鏈表將每個節(jié)點中next,prve,item全部置空
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;//頭尾引用都置空
        size = 0;//長度值為0
        modCount++;
    }

總結(jié)

  • LinkedList 插入，刪除都是移動指針效率很高。
  • 查找需要進(jìn)行遍歷查詢，效率較低。

ArrayList與LinkedList的區(qū)別

  1. ArrayList底層是基于數(shù)組實現(xiàn),LinkedList基于雙鏈表實現(xiàn)
  2. ArrayList在物理上是一定連續(xù)的,而LinkedList在物理上不一定連續(xù),在邏輯上連續(xù)
  3. ArrayList訪問隨機訪問元素的時間復(fù)雜度為o(1),LinkedList則為o(n)
  4. 頭插入元素時,ArrayList需要搬運元素,時間復(fù)雜度為o(1)，鏈表只需要改變頭指針的指向即可,復(fù)雜度為o(1)
  5. ArrayList適用于頻繁的訪問元素,以及高效的存儲元素上,LinkedList適應(yīng)于任意位置插入和頻繁刪除元素的場景

終

《JavaSE-第十七章》之LinkedList,Java,java,數(shù)據(jù)結(jié)構(gòu),開發(fā)語言文章來源地址http://www.zghlxwxcb.cn/news/detail-638834.html

到了這里，關(guān)于《JavaSE-第十七章》之LinkedList的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進(jìn)行投訴反饋，一經(jīng)查實，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包