What is LinkedList under the hood?
Good afternoon, habitrachiteli!
How ArrayList works is completely understandable. There are many articles on this subject, some of them are illustrated with wonderful pictures, so that even to beginners it becomes clear at once. The best articles on this topic are “Data structures in pictures. ArrayList , written by tarzan82 .
The same author describes the principles of LinkedList , however, some of the data is outdated even with the release of Java 7, so trying to understand in detail what is happening inside this collection is already difficult by the drawings tarzan82 . Yes, and in other sources I did not meet clear pictures, and therefore the idea arose to write this article.
So, LinkedList is 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. The actually linked list consists of a sequence of nodes, each of which is intended to store an object of a type defined during creation.
Let us see what happens when we write 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 intended for storing integers ( Integer ). While this object is empty.
The LinkedList class contains three fields:
This code adds the number 8 to the end of the previously created list. Under the “hood”, this method calls a number of other methods to create an object of type Integer , create a new node, set an object of class Integer in the item field of this node, add a node to the end of the list, and set references to neighboring nodes.
LinkedList uses objects of its nested Node class to set up links to the previous and next elements:
Each time an object is added to the list, one new node is created, and the values ​​of the linked list fields ( size , first , last ) also change.
In the case of adding the first element, a node is created whose previous and next elements are missing, i.e. are null , the size of the collection is incremented by 1, and the created node is set as the first and last element of the collection.
Add one more item to our collection:
First, a node is created for the new element (number 5) and a reference is made to the existing element (node ​​with number 8) of the collection as the previous one, and the next element of the created node is null . This new node is also saved to the variable of the linked list last :
As can be seen in fig. 4, the first element of the collection (under the index 0) so far refers to null as the next element. Now this link is replaced and the first element starts to refer to the second element of the collection (under the index 1), and the size of the collection also increases:
LinkedList allows you to add an item to the middle of the list. The add (index, element) method is used for this, 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 index value is checked, which must be a positive number that is less than or equal to the size of the list. If index does not satisfy these conditions, then an IndexOutOfBoundsException exception will be thrown .
Then, if index is equal to the collection size, then the actions described in section 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 it is inserted before the element, which has the specified index before this insertion, i.e. in this case, in front of the node with a value of 5.
First, using the node (index) method, we determine the node currently under the index under which we need to insert a new node. This node is searched using a simple for loop over 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 the new element (number 13), the link to the previous element is set to the node in which the element is number 8, and the link to the next element is set to the node in which the element is number 5. References of previously existing nodes have not yet changed:
Now the links are successively replaced: for the element following the new element, the reference to the previous element is replaced (now it points to the node with value 13), the link to the next element is replaced for the one that precedes the new element (now it points to the node with value 5). And last of all, the size of the list increases:
To remove a single item from the list, the LinkedList class offers us as many as 10 methods, which differ in the type of return value, the presence or absence of thrown exceptions, and the method of specifying which element should be deleted:
Consider removing an item from a linked list by its value. Remove the element with a value of 5 from the list below:
Please note that the accepted value in the remove (object) method is an object, if we try to delete an element with value 5 by the following line
then we get an IndexOutOfBoundsException , since The compiler will take the number 5 as an index and call the remove (index) method.
So, what happens when you call the remove (object) method? First, the desired object is compared in order with all the elements stored in the list nodes, starting with the zero node. When a node is found whose element is equal to the desired object, the first thing the element is stored in a separate variable. Then the references of neighboring nodes are redefined so that they point to each other:
Then the value of the node that contains the object to be deleted is reset, and the size of the collection is also reduced:
Now back to the moment that the element from the node to be deleted was stored in memory. Why did we do this, you ask, if we have not used this data anywhere else? The fact is that the method we are considering does not return the deleted item as a result of its work, so the data returned by the unlink (node) method called by the remove (object) method was simply not needed. But when we use the remove (index) method, which also calls the unlink (node) method, the value of this element is successively 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 are called inside, which detach the link: in the poll () , pollFirst () , remove () and removeFirst () methods this is the unlinkFirst (node) method, and in the pollLast methods () and removeLast () - unlinkLast (node) method.
So, what should be remembered about LinkedList , deciding whether to use this collection:
LinkedList Source Code (JDK 8)
LinkedList Documentation
How ArrayList works is completely understandable. There are many articles on this subject, some of them are illustrated with wonderful pictures, so that even to beginners it becomes clear at once. The best articles on this topic are “Data structures in pictures. ArrayList , written by tarzan82 .
The same author describes the principles of LinkedList , however, some of the data is outdated even with the release of Java 7, so trying to understand in detail what is happening inside this collection is already difficult by the drawings tarzan82 . Yes, and in other sources I did not meet clear pictures, and therefore the idea arose to write this article.
So, LinkedList is 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. The actually linked list consists of a sequence of nodes, each of which is intended to store an object of a type defined during creation.
Let us see what happens when we write simple and familiar lines of code.
')
1. Creating a linked list
LinkedList<Integer> numbers = new LinkedList<>(); This code creates an object of the LinkedList class and stores it in the numbers link. The created object is intended for storing integers ( Integer ). While this object is empty.
The LinkedList class contains three fields:
// transient , // transient int size = 0; transient Node<E> first; transient Node<E> 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 the previously created list. Under the “hood”, this method calls a number of other methods to create an object of type Integer , create a new node, set an object of class Integer in the item field of this node, add a node to the end of the list, and set references to neighboring nodes.
LinkedList uses objects of its nested Node class to set up links to the previous and next elements:
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; } } Each time an object is added to the list, one new node is created, and the values ​​of the linked list fields ( size , first , last ) also change.
In the case of adding the first element, a node is created whose previous and next elements are missing, i.e. are null , the size of the collection is incremented by 1, and the created node is set as the first and last element of the collection.
Add one more item to our collection:
numbers.add(5); First, a node is created for the new element (number 5) and a reference is made to the existing element (node ​​with number 8) of the collection as the previous one, and the next element of the created node is null . This new node is also saved to the variable of the linked list last :
As can be seen in fig. 4, the first element of the collection (under the index 0) so far refers to null as the next element. Now this link is replaced and the first element starts to refer to the second element of the collection (under the 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. The add (index, element) method is used for this, 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 index value is checked, which must be a positive number that is less than or equal to the size of the list. If index does not satisfy these conditions, then an IndexOutOfBoundsException exception will be thrown .
Then, if index is equal to the collection size, then the actions described in section 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 it is inserted before the element, which has the specified index before this insertion, i.e. in this case, in front of the node with a value of 5.
First, using the node (index) method, we determine the node currently under the index under which we need to insert a new node. This node is searched using a simple for loop over 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 the new element (number 13), the link to the previous element is set to the node in which the element is number 8, and the link to the next element is set to the node in which the element is number 5. References of previously existing nodes have not yet changed:
Now the links are successively replaced: for the element following the new element, the reference to the previous element is replaced (now it points to the node with value 13), the link to the next element is replaced for the one that precedes the new element (now it points to the node with value 5). And last of all, the size of the list increases:
4. Removing an object from the list
To remove a single item from the list, the LinkedList class offers us as many as 10 methods, which differ in the type of return value, the presence or absence of thrown exceptions, and the method of specifying which element should be deleted:
Consider removing an item from a linked list by its value. Remove the element with a value of 5 from the list below:
numbers.remove(Integer.valueOf(5)); Please note that the accepted value in the remove (object) method is an object, if we try to delete an element with value 5 by the following line
numbers.remove(5); then we get an IndexOutOfBoundsException , since The compiler will take the number 5 as an index and call the remove (index) method.
So, what happens when you call the remove (object) method? First, the desired object is compared in order with all the elements stored in the list nodes, starting with the zero node. When a node is found whose element is equal to the desired object, the first thing the element is stored in a separate variable. Then the references of neighboring nodes are redefined so that they point to each other:
Then the value of the node that contains the object to be deleted is reset, and the size of the collection is also reduced:
Now back to the moment that the element from the node to be deleted was stored in memory. Why did we do this, you ask, if we have not used this data anywhere else? The fact is that the method we are considering does not return the deleted item as a result of its work, so the data returned by the unlink (node) method called by the remove (object) method was simply not needed. But when we use the remove (index) method, which also calls the unlink (node) method, the value of this element is successively 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 are called inside, which detach the link: in the poll () , pollFirst () , remove () and removeFirst () methods this is the unlinkFirst (node) method, and in the pollLast methods () and removeLast () - unlinkLast (node) method.
So, what should be remembered about LinkedList , deciding whether to use this collection:
- not synchronized;
- allows you to store any objects, including null and duplicate;
- for the constant time O (1) , the operations of inserting and deleting the first and last elements are performed, the operation of inserting and deleting an element from the middle of the list (not taking into account the time of searching for the position of an element that is carried out in linear time);
- in the linear time O (n) , the operations of searching for an element by index and by value are performed.
Links
LinkedList Source Code (JDK 8)
LinkedList Documentation
Source: https://habr.com/ru/post/337558/
All Articles