JDK LinkedList Source Analysis

2010-12-23  来源:本站原创  分类:Java  人气:94 

Then today, another of about JDK collection classes in the LinkedList.

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

As you can see the same LinkedList and ArrayList implement the List interface. Take a look at its constructor:

public LinkedList() {
        header.next = header.previous = header;//  Initialize the first node
    }

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);//  Collection interface implementation to join the class to store all the elements  LinkedList  In
    }

In the default constructor can see a header of the private variables, see the statement:

private transient Entry<E> header = new Entry<E>(null, null, null);

Entry type header variable is, for the Entry to see the following code:

private static class Entry<E> {
        E element;
        Entry<E> next;
        Entry<E> previous;

        Entry(E element, Entry<E> next, Entry<E> previous) {
            this.element = element;
            this.next = next;
            this.previous = previous;
        }
    }

Entry is a private inner class LinkedList, external and can not access, which declared its three properties, namely the data to be displayed, a reference point to the next Entry, Entry point to the previous reference. From here you can see and realize the different ArrayList. LinkedList the bottom is the use of chain structure, each Entry represents a chain of nodes, which

Entry includes a point on the reference and the next Entry, Entry to associate with the adjacent.

Another argument for the constructor to receive a Collection interface types, it can be a list, it can be set, and then call the default constructor to initialize a

header node as a head pointer, then call the addAll method to set the parameters passed all the elements to the LinkedList. The following look at the source code addAll methods:

public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

The source code calls a addAll method:

public boolean addAll(int index, Collection<? extends E> c) {
        if (index < 0 || index > size) //  If the incoming index out of bounds  ,  An exception is thrown
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Object[] a = c.toArray();//  Incoming parameter of type Collection into an array
        int numNew = a.length;//  The length of the array
        if (numNew==0) //  Length is 0, return  false
            return false;
        modCount++;

        Entry<E> successor = (index==size ? header : entry(index));//  Back to index position of the  Entry
        Entry<E> predecessor = successor.previous;//  Be on a  Entry
        for (int i=0; i<numNew; i++) {//  Loop through the array
            Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);//  I use the index on the first element to construct a  Entry
            predecessor.next = e;//predecessor  A reference to the next  Entry
            predecessor = e;//  E at this time into the last  Entry,  I +1 as the first location of the array constructed on  Entry  The previous
        }
        successor.previous = predecessor;// After end of the cycle after the last element to the array as the previous section index Entry  Entry

        size += numNew;//  The total length of the array length units
        return true;
    }

The code has an entry (index) method is used to find the first index on the entry, JDK in the second method uses a technique, the following look at the source code of the method:

private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;
        if (index < (size >> 1)) {//  If the entire left side of the part of the list, you can just look at the left side
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {//  Otherwise, look in the right side
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;//  Back to Search  entry
    }

Can be seen through the jdk source code to find the corresponding entry in time is optimized to avoid traversing the list to find the overall improved efficiency

The following look at other ways:

public boolean add(E e) {
        addBefore(e, header);
        return true;
    }

add method calls the addBefore methods:

private Entry<E> addBefore(E e, Entry<E> entry) {
        Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);//  Changed the two references
        newEntry.previous.next = newEntry;//  Before the new element to a position where a reference to the next element of the new
        newEntry.next.previous = newEntry;//  The next new element to the last position a reference to the new element
        size++;
        modCount++;
        return newEntry;
    }

Signaled by the code, you can see the changes when added with the adjacent entry and add the entry of related references, because the bottom is a doubly linked list, said that inserting a new element will change the reference 4

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

 public E removeFirst() {
        return remove(header.next);
    }

  private E remove(Entry<E> e) {
        if (e == header)
            throw new NoSuchElementException();

        E result = e.element;
        e.previous.next = e.next;
        e.next.previous = e.previous;
        e.next = e.previous = null;
        e.element = null;
        size--;
        modCount++;
        return result;
    }

LinkedList can be seen for the deletion of an entry, after a number of calls was transferred to the core of the method remove (Entry e), in the method, by

Modify the reference to the adjacent entry, and then set their own null, so as to achieve removal, their mother, and finally reduced with the size of a unit of length, complete removal of this

On the whole, LinkedList uses a linked list of the underlying mechanism, which is the biggest difference with the ArrayList. Use the list can insert, delete operations more efficient environment for frequent, because you do not want to move as frequently as ArrayList array, but through the entry ( index) method can be seen that it is necessary to find step by step starting from scratch down the node beginning to find, a bit slow on the efficiency of

相关文章
  • JDK LinkedList Source Analysis 2010-12-23

    Then today, another of about JDK collection classes in the LinkedList. public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable As you can see the same LinkedList an

  • JDK ArrayList Source Analysis 2010-12-22

    Today looked at the source ArrayList to write about their own experiences ArrayList first integrated system, the code is as follows: public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.S

  • JDK LinkedHashMap Source Analysis 2010-12-25

    Today to analyze the source code of JDK LinkedHashMap public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> You can see, LinkedHashMap extends HashMap, and also implements the Map interface, so most of LinkedHashMap fo

  • Struts1 Source analysis - international resource file 2010-04-01

    Struts1 Source analysis - international resource file 1. URL class diagram 2. Description a) Struts resources to international, use the JDK following categories: o java.text.MessageFormat o java.util.ResourceBundle o java.util.PropertyResourceBundle

  • HashMap source analysis 2010-06-17

    HashMap source analysis public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable HashMap is inherited from AbstractMap <K,V>, then we first look at a AbstractMap <K,V> public abstract cl

  • Lucene3.0 Source Analysis (1) in the Eclipse / MyEclipse project to build Lucene3.0 2010-06-19

    Source analysis of the first step is to establish related projects in the IDE, and then go step by step learning. Lucene3.0.2 project I set up some unnecessary long way around, so feel the need to write this blog: 1. Download Source: Download Lucene3

  • Axis source analysis - the server processes the request and response (3) 2010-08-16

    Source analysis of the Axis-Web Services Deployment (II) http://dead-knight.javaeye.com/blog/732961 Has two web deployment are analyzed, involving a server AxisServlet initialization. As well as get, post a request for monitoring. Server processes th

  • TOMCAT Source Analysis (start frame) 2010-09-11

    Reprinted: http://edu.codepub.com/2010/0518/22773.php TOMCAT Source Analysis (start frame) Introduction: This is after I read some tips TOMCAT source. Mainly explain the TOMCAT system framework, and start the process. If errors and omissions, please

  • CLucene source analysis (c) cross-platform, thread-safe 2010-12-21

    Home> CLucene, program Life> CLucene source analysis (c) cross-platform, thread-safe CLucene source analysis (c) cross-platform, thread-safe May 29, 2009 Xiao Wu brother comment read comments in the multi-threaded programming, the program thread-saf

  • jQuery 1.2.6 Source Analysis (pdf) 2010-03-29

    jQuery source code analysis.

  • [Java performance analysis] Sun JDK visual performance analysis tools introduced 2010-04-29

    In addition to some basic tools, together with the Sun JDK release some visual analysis tools, including in the JDK6.0.7 version of JConsole and the introduction of the Visual VM. 1. JConsole: JConsole can be said of all the features described above

  • struts1 Source Analysis 2010-05-03

    Initialization of first struts struts core class is org.apache.struts.action.ActionServlet, this class will be used in the struts for the first time, Tomcat as a servlet initialization and into the container. Clearly, the initialization will call the

  • android player (music player) Source analysis of 1-Service, Binder, ServiceConnection 2010-07-21

    <! - [If gte mso 9]> <xml> <w:WordDocument> <w:View> Normal </ w: View> <w:Zoom> 0 </ w: Zoom> <w:PunctuationKerning/> < w: DrawingGridVerticalSpacing> 7.8 Lb </ w: DrawingGridVerticalSpacing> &l

  • SQLITE Source Analysis (3) 2010-07-22

    Disclaimer: The SQLite source code analysis series Xing (http://deepfuture.javaeye.com/) original, without author authorization, any human institution can not be reproduced / * ** The SQLITE_DEFAULT_MEMSTATUS macro must be defined as either 0 or 1. *

  • SQLITE Source Analysis (5) 2010-07-28

    Disclaimer: The SQLite source code analysis series Xing (http://deepfuture.javaeye.com/) original, without author authorization, any human institution can not be reproduced /************** Include sqlite3.h in the middle of sqliteInt.h **************

  • Dictionary - Source Analysis (idiom dictionary) 2010-08-05

    Chinese dictionary project, designed primarily to study several aspects of technology Pinyin and Chinese character index Document literacy I). Pinyin index number of idioms of magnitude in 1300, its only through the sqlite query time-consuming, there

  • android player (music player) Source analysis of 5 (Online Play function) 2010-08-12

    Based on the article page on Baidu MP3 analysis, generated the following format xml document. <?xml version="1.0" encoding="UTF-8" standalone="no" ?> - <Result> - <Catagory cID="0"> Top artists <

  • SQLITE Source Analysis (7) 2010-08-21

    Disclaimer: The SQLite source code analysis series Xing (http://deepfuture.javaeye.com/) original, without author authorization, any human institution can not be reproduced ** ^ The sqlite3_version [] string constant contains the text of [SQLITE_VERS

  • SQLITE Source Analysis (8) 2010-08-22

    Disclaimer: The SQLite source code analysis series Xing (http://deepfuture.javaeye.com/) original, without author authorization, any human institution can not be reproduced / * Thread-safe libraries ** CAPI3REF: Test To See If The Library Is Threadsa

  • SQLITE Source Analysis (9) 2010-08-24

    / * Disclaimer: The SQLite source code analysis series Xing (http://deepfuture.javaeye.com/) original, without author authorization, any human institution can not be reproduced ** CAPI3REF: 64-Bit Integer Types ** KEYWORDS: sqlite_int64 sqlite_uint64