notes : Blogger java Collection framework source code analysis series of source code based on JDK1.8.0 edition .

In the actual project LinkedList It's also a very frequently used collection , This blog will lead you to learn about LinkedList Knowledge .

One LinkedList The definition of a class :

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

As you can see from the above code :LinkedList Inherited from AbstractSequentialList At the same time List,Deque,Cloneable And Serializable Interface , therefore LinkedList It can be used as a two terminal queue .

Two LinkedList Some important properties of class :

transient int size = 0;
transient Node<E> first;// Pointer to the first node
transient Node<E> last;// Pointer to the last node

You can see it here LinkedList All operations are based on Node data-structured , and Node yes LinkedList An inner class , It's essentially a two-way linked list , namely LinkedList The bottom layer is based on two-way linked list , therefore LinkedList It has good insertion ability , Ability to delete .Node Class is defined as follows :

 private static class Node<E> {
E item;
Node<E> next;
Node<E> prev; Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

3、 ... and LinkedList Internal implementation principles : So let's see LinkedList Constructor

 public LinkedList() {
} public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

You can see that the constructor re calls addAll(c), Let's take a look addAll Source code :

public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
} public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); Object[] a = c.toArray();// Convert a collection to an array
int numNew = a.length;
if (numNew == 0)
return false; Node<E> pred, succ;//pred Indicates the precursor node ,succ Represents the successor node
if (index == size) {// If the insertion position is at the end of the list , Then it follows null, The precursor is the tail node
succ = null;
pred = last;
} else {
succ = node(index);// call node() Function to find the subscript index The node of
pred = succ.prev;// Save the precursor of the node
} for (Object o : a) {// While traversing the array, convert the elements in the array to Node Type into place
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)// Means insert before the first element ( The index for 0 The node of )
first = newNode;
else
pred.next = newNode;
pred = newNode;
} if (succ == null) {// Means insert after the last element
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
} size += numNew;
modCount++;
return true;
}

addAll(index,c) The function of this method is that index Insert... At position Collection aggregate c All of the elements in , You can see that before the insert operation, the collection c Convert to array structure , And then convert the elements in the array to Node Node inserted , At the same time, you can see that the function has been called node function ,node The source of the function is as follows :

 /**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// Judge whether the insertion position is in the first half or the second half of the list
if (index < (size >> 1)) {// When index < size/2 when , The insertion position is in the first half
Node<E> x = first;
for (int i = 0; i < index; i++)// Forward traversal from the beginning
x = x.next;
return x;
} else {// The insertion position is in the second half
Node<E> x = last;
for (int i = size - 1; i > index; i--)// Starting from the tail node, the reverse traversal
x = x.prev;
return x;
}
}

Its function is to return a not for null According to the passed in location parameter index, You can see that the function first passes through index < (size >> 1) This statement is used to determine the query's index In the front or the back , Nodes in the first half are traversed from the beginning , In the second half, we start from the tail , In this way, only half of the nodes need to be traversed to find the node with the specified index . Improved search efficiency .

That is, when you create a LindedList When ,LindedList The inner part of is to first convert the set into an array , And then convert the elements in the array to Node Nodes are inserted to construct a collection of elements c Of LinkedList.

Four LinkedList Some important functions :

1. add function

public boolean add(E e) {
linkLast(e);
return true;
} /**
* Links e as last element.
*/
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++;
}

As you can see from the above code add Functions are actually called LinkLast(E) function , namely add Function to add an element to LinkedList Is added to linkedList At the end of .

2get function

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

You can see get Functions are actually called node function , That is to say, it returns a value that is not null According to the passed in location parameter index.

3getFirst/getLast

 public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
} public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}

because first Nodes always point to LinkedList The first node in , So go straight back first.item, Empathy last Nodes always point to LinkedList The last node in , So go straight back last.item.

4remove function

 public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

Put the element o From the collection LinkedList Delete in , Which is called unLink() function , This function is used to disconnect the specified node from the list .

5、 ... and : summary :

1LinkedList The interior of is based on the realization of two-way circular linked list , The definition of a two-way circular list is Node, It is LinkedList An inner class .

2 When using a set as a parameter to construct a LinkedList when , Inside, we first convert the set into an array , And then convert the elements in the array to Node Nodes are inserted to construct a collection of elements c Of LinkedList.

3 You can see LinkedList None of the methods in are used synchronized Keyword modification , namely LinkedList asynchronous , If you want to create a synchronous LinkedList You need to use Collections.synchronizedList Function to construct : namely List list = Collections.synchronizedList(new LinkedList(...));

3LinkedList Realized Deque, therefore LinkedList It can be used as a two terminal queue , When you need to use a queue structure , You can consider LinkedList.

4LinkedList Allow duplicate elements to exist , Because in add There is no element in the process HashMap in put The process of time-dependent replacement , It's just a simple insert operation .

【java Collection framework source code analysis series 】java Source analysis of LinkedList More articles about

  1. Java Set framework system JCF

    Java Set framework system as Java It's a very important part of , It plays a very important role in our daily development , So what is Java Set framework system ? stay Java In language ,Java The designer of the language has done a research on the commonly used data structure and algorithm ...

  2. Java Summary of collection framework usage

    Java Summary of collection framework usage Preface : This article is about Java The set framework gives a general explanation , The aim is to Java There is a general understanding of the set framework system , If you want to learn how to use specific interfaces and classes , Please see JavaAPI file . One . Overview data node ...

  3. 【java Collection framework source code analysis series 】java Source analysis of TreeSet

    This blog will lead you to learn from the perspective of source code TreeSet Relevant knowledge . One TreeSet The definition of a class : public class TreeSet<E> extends AbstractSet<E&g ...

  4. 【java Collection framework source code analysis series 】java Source analysis of HashSet

    notes : Blogger java Collection framework source code analysis series of source code based on JDK1.8.0 edition . This blog will lead you to learn about HashSet Knowledge . One HashSet The definition of : public class HashSet&l ...

  5. 【java Collection framework source code analysis series 】java Source analysis of TreeMap

    notes : Blogger java Collection framework source code analysis series of source code based on JDK1.8.0 edition . This blog will lead you to learn about TreeMap Knowledge . One TreeMap The definition of : public class TreeMap&l ...

  6. 【java Collection framework source code analysis series 】java Source analysis of ArrayList

    notes : Blogger java Collection framework source code analysis series of source code based on JDK1.8.0 edition . This blog will lead you to learn about ArrayList Knowledge . One ArrayList The definition of a class : public class Arr ...

  7. 【java Collection framework source code analysis series 】java Source analysis of HashMap

    Preface : The reason why I plan to write java Collection framework source code analysis series blog is due to my reflection on the failure of Ali push side ( I don't think so , Because writing this blog has been a week away from Alibaba ), At that time, after the interview, I felt that I answered very well , And according to the interviewer's last words ...

  8. 【java Collection framework source code analysis series 】java Source analysis of java Half insert sort algorithm in set

    notes : About sorting algorithm , The blogger wrote [ Data structure sorting algorithm series ] Eight sorting algorithms of data structure , Basically, all the sorting algorithms have been explained in detail , And the reason why alone will java The sorting algorithm in the set is explained , It's because the interviewer asked during the interview in Alibaba ...

  9. turn :【Java Collection source code analysis 】Java Collections framework

    Reprint light, indicate the source :http://blog.csdn.net/ns_code/article/details/35564663   Java The collection kit is located in Java.util It's a bag , Contains a lot of commonly used data structures , ...

Random recommendation

  1. Spring task Timing task

    <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://mave ...

  2. Java Cognitive description of interview knowledge

    Connection pool : At the same time, operate and connect to the database , Create a connection pool , Create 10000 database links in the pool . Close the link according to the operation of the system . Peak links reach maximum MAX Queuing , Implement expiration time for links in use . There are several kinds of :tomcat Request server (serve ...

  3. 【 turn 】C# Class classification ( Static class 、 Instance class 、 Nested class 、 structure 、 Simple abstract classes 、 Simple seal class )

    Static class -------------------------------------------------------------------------------- Static classes are in class Keyword before ...

  4. iOS Simply load a web page

    .h In file @property(strong ,nonitomic) UIWebView * webView; .m In file -(void)viewDidLoad { self.webview = [[ ...

  5. Python Full stack development MySQL( Two )------navicate and python operation MySQL

    One :Navicate Installation 1. What is? navicate? Navicat It's a fast . Reliable and affordable database management tool , Designed to simplify database management and reduce system management costs . It's designed to work with database administrators . Developers and SMEs ...

  6. Windows 8 application development - Application bar

    original text :Windows 8 application development - Application bar      Through the application bar (AppBar) Various application commands can be displayed to users when needed . The application bar provides various commands related to the user's current page or currently selected content . By default , The application bar is hidden ...

  7. Windows Redis Default profile ,Redis Configuration does not work solution

    Windows Redis Default profile ,Redis Configuration does not work solution , Windows Redis The solution of self booting configuration does not work ,Windows Redis Add auto start service >>>> ...

  8. New Xiaobai , Sort out the very simple and practical div+css Compatibility issues .

    Recently, I sorted out some very simple div+css The compatibility of different browsers , Share with you , It's only suitable for beginners , You are welcome to put forward your opinions . 1. The default inner and outer margins are different problem : The default inner and outer margins of each browser are different solve : * ...

  9. Android IntentService Introduction and source code analysis

    Copyright notice : This article is from Wang Lei's blog , Please indicate the source of reprint . One .IntentService Overview and use examples IntentService The internal implementation mechanism uses HandlerThread, If the HandlerThrea ...

  10. Complete the Word CodeForces - 716B

    ZS the Coder loves to read the dictionary. He thinks that a word is nice if there exists asubstring  ...