September 9, 2017 at 20:33What's under the hood of LinkedList?
Good afternoon, habrachitateli!
How ArrayList works is understandable. There are many articles on this subject, some of them are illustrated with wonderful pictures, so that even for beginners it becomes immediately clear. To the best articles on this subject, I include “Data Structures in Pictures. ArrayList " written by tarzan82 .
The same author describes how LinkedList works , however, some of the data is outdated with the release of Java 7, so trying to figure out what is happening inside this collection in detail using tarzan82 figures is already difficult. Yes, and in other sources I did not meet clear pictures, and therefore the idea arose to write this article.
So, LinkedList- a class that implements two interfaces - List and Deque . This provides the ability to create a bidirectional queue from any (including null ) elements. Each object placed in a linked list is a node (node). Each node contains an element, a link to the previous and next node. In fact, a linked list consists of a sequence of nodes, each of which is designed to store an object of a type defined when creating it.
Let’s figure out what happens when we write already simple and familiar lines of code.
This code creates an object of the LinkedList class and stores it in the numbers link . The created object is designed to store integers ( Integer ). While this object is empty.
The LinkedList class contains three fields:
This code adds the number 8 to the end of a previously created list. Under the “hood”, this method calls a number of other methods that provide creating an object of type Integer , creating a new node, setting an object of class Integer in the item field of this node, adding a node to the end of the list, and setting links to neighboring nodes.
To link to the previous and next elements, LinkedList uses the objects of its nested Node class :
Each time an object is added to the list, one new node is created, and the values of the fields in the linked list ( size , first , last ) are also changed .
In the case of adding the first element, a node is created in which the previous and next elements are absent, i.e. are null , the size of the collection is increased by 1, and the created node is set as the first and last element of the collection.
Add another item to our collection:
First, a node is created for the new element (number 5) and a link is established to the existing element (node with the number 8) of the collection as the previous one, and the next element in the created node remains null . Also, this new node is saved in the variable of the last linked list :
As can be seen in Fig. 4, the first element of the collection (under index 0) so far refers to null as the next element. Now this link is replaced and the first element begins to refer to the second element of the collection (under index 1), and the size of the collection also increases:
LinkedList allows you to add an item to the middle of the list. To do this, use the add (index, element) method, where index is the place in the list where the element element will be inserted.
Like the add (element) method, this method calls several other methods. First, the value of index is checked, which must be a positive number less than or equal to the size of the list. If index does not satisfy these conditions, an IndexOutOfBoundsException will be thrown .
Then if indexequal to the size of the collection, then the actions described in paragraph 2 are carried out, since in fact it is necessary to insert an element at the end of the existing list.
If index is not equal to the size of the list, then an insert is performed before the element that prior to this insert has a given index, i.e. in this case, before the node with a value of 5.
First, use the node (index) methodthe node that is currently under the index is determined, under which we need to insert a new node. The search for this node is carried out using a simple for loop in half the list (depending on the index value - either from the beginning to the element, or from the end to the element). Next, a node is created for a new element (number 13), a link to the previous element is set to a node in which the element is number 8, and a link to the next element is set to a node in which the element is number 5. Links of previously existing nodes have not yet been changed:
Now the links are successively replaced: for the element following the new element, the link to the previous element is replaced (now it points to the node with the value 13), for the one preceding the new element, the link to the next element is replaced (now it points to the node with the value 5). And last but not least, the size of the list is increased:
To remove one item from the list, the LinkedList class offers us 10 methods that differ in the type of return value, the presence or absence of thrown exceptions, and also the method of specifying which item should be removed:
Consider removing an item from the linked list by its value. Delete the item with the value 5 from the list below:
Please note that the accepted value in the remove (object) method is just the object, if we try to remove the element with value 5 on the next line
then we get IndexOutOfBoundsException , because the compiler takes number 5 as an index and calls the remove (index) method .
So what happens when you call the remove (object) method ? First, the desired object is compared in order with all elements stored in the list nodes, starting from the zero node. When a node is found whose element is equal to the desired object, the first thing the element is saved in is a separate variable. Then the links of neighboring nodes are redefined so that they point to each other:
Then the value of the node that contains the deleted object is reset to zero, and the size of the collection is also reduced:
Now back to the point that we saved the element from the deleted node in memory. Why did we do this, you ask, if we did not use this data anywhere else. The fact is that the method we are considering as a result of its work does not return the deleted element, because the data returned by the unlink (node) method called by the remove (object) method just was not needed. But when we use the remove (index) method, which also calls the unlink (node) method , then the value of this element is sequentially returned first by the unlink (node) method, and then by the remove (index) method. A similar situation is observed in the other methods that return the value of the deleted element, only other methods that disconnect the link are called inside: in the poll () , pollFirst () , remove () and removeFirst () methods, this is the unlinkFirst (node) method , and in pollLast methods () and removeLast () are the unlinkLast (node) method .
So, what you should remember about LinkedList when deciding whether to use this collection:
LinkedList Source Code (JDK 8) LinkedList
Documentation
How ArrayList works is understandable. There are many articles on this subject, some of them are illustrated with wonderful pictures, so that even for beginners it becomes immediately clear. To the best articles on this subject, I include “Data Structures in Pictures. ArrayList " written by tarzan82 .
The same author describes how LinkedList works , however, some of the data is outdated with the release of Java 7, so trying to figure out what is happening inside this collection in detail using tarzan82 figures is already difficult. Yes, and in other sources I did not meet clear pictures, and therefore the idea arose to write this article.
So, LinkedList- a class that implements two interfaces - List and Deque . This provides the ability to create a bidirectional queue from any (including null ) elements. Each object placed in a linked list is a node (node). Each node contains an element, a link to the previous and next node. In fact, a linked list consists of a sequence of nodes, each of which is designed to store an object of a type defined when creating it.
Let’s figure out what happens when we write already simple and familiar lines of code.
1. Create a linked list
LinkedList numbers = new LinkedList<>(); This code creates an object of the LinkedList class and stores it in the numbers link . The created object is designed to store integers ( Integer ). While this object is empty.
The LinkedList class contains three fields:
// модификатор transient указывает на то, что данное свойство класса нельзя
// сериализировать
transient int size = 0;
transient Node first;
transient Node last; 2. Adding an object to the end of a linked list
numbers.add(8);This code adds the number 8 to the end of a previously created list. Under the “hood”, this method calls a number of other methods that provide creating an object of type Integer , creating a new node, setting an object of class Integer in the item field of this node, adding a node to the end of the list, and setting links to neighboring nodes.
To link to the previous and next elements, LinkedList uses the objects of its nested Node class :
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;
}
} Each time an object is added to the list, one new node is created, and the values of the fields in the linked list ( size , first , last ) are also changed .
In the case of adding the first element, a node is created in which the previous and next elements are absent, i.e. are null , the size of the collection is increased by 1, and the created node is set as the first and last element of the collection.
Add another item to our collection:
numbers.add(5);First, a node is created for the new element (number 5) and a link is established to the existing element (node with the number 8) of the collection as the previous one, and the next element in the created node remains null . Also, this new node is saved in the variable of the last linked list :
As can be seen in Fig. 4, the first element of the collection (under index 0) so far refers to null as the next element. Now this link is replaced and the first element begins to refer to the second element of the collection (under index 1), and the size of the collection also increases:
3. Adding an object to the middle of a linked list
numbers.add(1, 13);LinkedList allows you to add an item to the middle of the list. To do this, use the add (index, element) method, where index is the place in the list where the element element will be inserted.
Like the add (element) method, this method calls several other methods. First, the value of index is checked, which must be a positive number less than or equal to the size of the list. If index does not satisfy these conditions, an IndexOutOfBoundsException will be thrown .
Then if indexequal to the size of the collection, then the actions described in paragraph 2 are carried out, since in fact it is necessary to insert an element at the end of the existing list.
If index is not equal to the size of the list, then an insert is performed before the element that prior to this insert has a given index, i.e. in this case, before the node with a value of 5.
First, use the node (index) methodthe node that is currently under the index is determined, under which we need to insert a new node. The search for this node is carried out using a simple for loop in half the list (depending on the index value - either from the beginning to the element, or from the end to the element). Next, a node is created for a new element (number 13), a link to the previous element is set to a node in which the element is number 8, and a link to the next element is set to a node in which the element is number 5. Links of previously existing nodes have not yet been changed:
Now the links are successively replaced: for the element following the new element, the link to the previous element is replaced (now it points to the node with the value 13), for the one preceding the new element, the link to the next element is replaced (now it points to the node with the value 5). And last but not least, the size of the list is increased:
4. Removing an object from the list
To remove one item from the list, the LinkedList class offers us 10 methods that differ in the type of return value, the presence or absence of thrown exceptions, and also the method of specifying which item should be removed:
Consider removing an item from the linked list by its value. Delete the item with the value 5 from the list below:
numbers.remove(Integer.valueOf(5));Please note that the accepted value in the remove (object) method is just the object, if we try to remove the element with value 5 on the next line
numbers.remove(5);then we get IndexOutOfBoundsException , because the compiler takes number 5 as an index and calls the remove (index) method .
So what happens when you call the remove (object) method ? First, the desired object is compared in order with all elements stored in the list nodes, starting from the zero node. When a node is found whose element is equal to the desired object, the first thing the element is saved in is a separate variable. Then the links of neighboring nodes are redefined so that they point to each other:
Then the value of the node that contains the deleted object is reset to zero, and the size of the collection is also reduced:
Now back to the point that we saved the element from the deleted node in memory. Why did we do this, you ask, if we did not use this data anywhere else. The fact is that the method we are considering as a result of its work does not return the deleted element, because the data returned by the unlink (node) method called by the remove (object) method just was not needed. But when we use the remove (index) method, which also calls the unlink (node) method , then the value of this element is sequentially returned first by the unlink (node) method, and then by the remove (index) method. A similar situation is observed in the other methods that return the value of the deleted element, only other methods that disconnect the link are called inside: in the poll () , pollFirst () , remove () and removeFirst () methods, this is the unlinkFirst (node) method , and in pollLast methods () and removeLast () are the unlinkLast (node) method .
So, what you should remember about LinkedList when deciding whether to use this collection:
- not synchronized;
- allows you to store any objects, including null and duplicates;
- for constant time O (1) , the operations of inserting and deleting the first and last element, the operations of inserting and deleting the element from the middle of the list are performed (not taking into account the time of searching for the position of the element, which is carried out in linear time);
- in linear time O (n) , operations are performed to search for an element by index and value.
References
LinkedList Source Code (JDK 8) LinkedList
Documentation