LinkedList源碼分析

geekidentity 發布于2019-08-16 15:21 / 540人閱讀

一、屬性及獲取屬性：

1、size

transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node last;

獲取

public int size() {
    return size;
}

二、構造函數

//Constructs an empty list
public LinkedList() {
}

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

三、類

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;
    }
}

四、方法

1、Node

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;
    }
}

*、linkFirst

/**
 * Links e as first element.
 */
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++;
}

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++;
}

*、add、addFirst

public void addFirst(E e) {
    linkFirst(e);
}
public boolean add(E e) {
    linkLast(e);
    return true;
}

linkLast

2、set

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

3、get

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

*、clear

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node x = first; x != null; ) {
        Node next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

*、Push Pop

public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

*、node(int index)

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;
    }
}

GPU云服務器云服務器 LinkedList 源碼分析 nginx源碼分析 webrtc源碼分析

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73424.html

LinkedList源碼分析：JDK源碼分析系列

摘要：介紹是線程不安全的，允許元素為的雙向鏈表。構造方法共有兩個構造方法，一個是創建一個空的構造函數，一個是將已有的添加到中。是將元素插入到的頭部。下一篇文章繼續分析上次分析了的結構和添加方法這次開始分析下面的。注意源碼版本為直接進入正題。如果本文中有不正確的地方請指出由于沒有留言可以在公眾號添加我的好友共同討論。 1.介紹 LinkedList 是線程不安全的，允許元素為null的雙向鏈...

blair 2019-08-16 18:33 評論0 收藏0
LinkedList源碼和并發問題分析

摘要：在次操作中其實即尾節點是共享資源，當多個線程同時執行此方法的時候，其實會出現線程安全問題。同樣會出現并發安全問題，下面對此問題進行分析。 1.LinkedList源碼分析 LinkedList的是基于鏈表實現的java集合類，通過index插入到指定位置的時候使用LinkedList效率要比ArrayList高，以下源碼分析是基于JDK1.8. 1.1 類的繼承結構 LinkedLis...

xietao3 2019-08-15 11:58 評論0 收藏0
集合框架源碼學習之LinkedList

摘要：它們會在鏈表為空時，拋出獲取尾節點數據方法兩者區別方法在鏈表為空時，會拋出，而則不會，只是會返回。目錄： 0-1. 簡介 0-2. 內部結構分析 0-3. LinkedList源碼分析　　0-3-1. 構造方法　　0-3-2. 添加add方法　　　　0-3-3. 根據位置取數據的方法　　0-3-4. 根據對象得到索引的方法　　0-3-5. 檢查鏈表是否包含某對象的方法　...

kumfo 2019-08-15 15:15 評論0 收藏0
LinkedList源碼分析

摘要：表明該類是可以序列化的。與對比并沒有實現，而實現表明其支持快速通常是固定時間隨機訪問。此接口的主要目的是允許一般的算法更改其行為，從而在將其應用到隨機或連續訪問列表時能提供良好的性能。這是隨機訪問效率低的原因之一。指定節點不能為。總覽 showImg(https://segmentfault.com/img/bVbsIzr?w=1007&h=600); 定義 public class...

tommego 2019-08-19 11:42 評論0 收藏0
LinkedList中查詢(contains)和刪除(remove)源碼分析

摘要：一源碼分析本文分析雙向鏈表的查詢操作源碼實現。中源程序中，的查詢操作，通過函數實現。源程序中使用循環進行遍歷。表示鏈表元素索引，初值為。針對空元素的情況，用循環遍歷，查找元素為的節點，并返回索引。一、contains源碼分析本文分析雙向鏈表LinkedList的查詢操作源碼實現。jdk中源程序中，LinkedList的查詢操作，通過contains(Object o)函數實現。具體...

timger 2019-08-16 15:15 評論0 收藏0
LinkedList源碼分析

摘要：源碼分析是一個雙向鏈表的數據結構實現。對于支持隨機訪問數據的比如數組，應該優先使用。一個有序的集合支持在頭和尾進行插入和刪除元素。的大多實現元素數量是沒有大小限制的。構造方法第一個是一個空的構造器，第二個構造器調用了方法。 LinkedList源碼分析 LinkedList是一個雙向鏈表的數據結構實現。類的實現接口及繼承父類 public class LinkedList exten...

andycall 2019-08-19 11:03 評論0 收藏0