In the previous article, we analyzed the underlying implementation of ArrayList and knew that the underlying implementation of ArrayList is based on arrays, so it has the characteristics of fast search and modification while slow insertion and deletion. The LinkedList introduced in this article is another implementation of the List interface. Its underlying layer is based on a bidirectional linked list. Therefore, it has the characteristics of fast insertion and deletion while slow search and modification. In addition, the functions of queues and stacks can be realized through the operation of the bidirectional linked list. The underlying structure of LinkedList is shown in the figure below.
F represents the head node reference, L represents the tail node reference, and each node in the linked list has three elements, namely the forward node reference (P), the node element value (E), and the subsequent node reference (N). The node is represented by the inner class Node, let's look at its internal structure.
//Node internal class private static class Node<E> { E item; //Element Node<E> next; //Next node Node<E> prev; //Previous node Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; }}The internal class Node is actually very simple, with only three member variables and a constructor. The item represents the value of the node, next is the reference to the next node, and prev is the reference to the previous node. These three values are passed through the constructor. Next, let’s take a look at the member variables and constructors of LinkedList.
//The number of set elements is translated int size = 0;//The header node references transient Node<E> first;//The tail node references transient Node<E> last;//The parameterless constructor public LinkedList() {}//The constructor passed into the external collection public LinkedList(Collection<? extends E> c) { this(); addAll(c);}LinkedList holds a reference to the header node and a reference to the tail node. It has two constructors, one is a parameterless constructor, and the other is a constructor passed to the external collection. Unlike ArrayList, LinkedList does not specify the initial size constructor. Check out its methods of adding, deleting, modifying and searching.
//Add (add) public boolean add(E e) { //Add linkLast(e); return true;}//Add (insert) public void add(int index, E element) { checkPositionIndex(index); if (index == size) { //Add linkLast(element); } else { //Insert linkBefore(element, node(index)); }}//Delete (Give index) public E remove(int index) { //Check whether the subscript is legal checkElementIndex(index); return unlink(node(index));}//Delete (given element) 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 { //Tranquility link list for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { //Delete unlink(x); return true; } } } return false;}//Change public E set(int index, E element) { //Check whether the subscript is legal checkElementIndex(index); //Get the node reference of the specified subscript Node<E> x = node(index); //Get the value of the specified subscript node E oldVal = x.item; //Set the node element to the new value x.item = element; //Return the previous value return oldVal;}//Check public E get(int index) { //Check whether the subscript is legal checkElementIndex(index); //Return the value of the node of the specified subscript return node(index).item;}The method of adding elements in LinkedList is mainly to call the two methods linkLast and linkBefore. The linkLast method is to link an element behind the linked list, and the linkBefore method is to insert an element in the middle of the linked list. The delete method of LinkedList removes an element from the linked list by calling the unlink method. Let’s take a look at the core code of the insertion and deletion operations of the linked list.
//Before linking to the specified node void linkBefore(E e, Node<E> succ) { //Get the previous node reference of the given node final Node<E> pred = succ.prev; //Create a new node, the previous node reference of the new node points to the previous node of the given node//The reference of the next node of the new node points to the given node final Node<E> newNode = new Node<>(pred, e, succ); //Point the previous node reference of the given node to the new node succ.prev = newNode; //If the previous node of the given node is empty, it means that the given node is the header node if (pred == null) { //Point the header node reference to the new node first = newNode; } else { //Otherwise, point the next node reference to the new node pred.next = newNode; } //Add the number of set elements one size++; //Add the number of modifications one modCount++; } //Unload the specified node E unlink(Node<E> x) { //Get the element of the given node final E element = x.item; //Get the reference to the next node of the given node final Node<E> next = x.next; //Get the reference to the previous node of the given node final Node<E> prev = x.prev; //If the previous node of the given node is empty, Explanation: The given node is a header node if (prev == null) { //Point the header node reference to the next node of the given node first = next; } else { //Reference the successor node of the previous node pointing to the subsequent node of the given node prev.next = next; //Reference the previous node of the given node x.prev = null; } //If the next node of the given node is empty, it means that the given node is a tail node if (next == null) { //Point the tail node reference to the previous node of the given node last = prev; } else { //Reference the forward node of the next node pointing to the previous node of the given node next.prev = prev; x.next = null; } //Empty the element of the given node x.item = null; //Subtract the number of set elements by size--; //Add modCount++; return element;} linkBefore and unlink are representative operations of linking nodes and uninstalling nodes. Other methods of linking and uninstalling nodes at both ends are similar, so we focus on linkBefore and unlink methods.
Process diagram of linkBefore method:
Process diagram of unlink method:
Through the above illustration, the time complexity of the insertion and deletion operations of the linked list is O(1), and the search and modification operations of the linked list require traversing the linked list to locate elements. Both operations are called node(int index) method to locate elements to see how it locates elements through subscripts.
//Get node Node<E> node(int index) { //If the index is in the first half of the linked list, check from the beginning if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { //If the index is in the second half of the linked list, check from the end Node<E> x = last; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; }} When positioning the subscript, first determine whether it is in the upper half or the lower half of the linked list. If it is in the upper half, start from the beginning, and if it is the lower half, start from the end. Therefore, the time complexity of the operation of searching and modifying the subscript is O(n/2). Through the operation of the bidirectional linked list, the functions of single-item queues, two-way queues and stacks can also be realized.
One-way queue operation:
//Get the header node public E peek() { final Node<E> f = first; return (f == null) ? null : f.item;}//Get the header node public E element() { return getFirst();}//Pop up the header node public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f);}//Remove the header node public E remove() { return removeFirst();}//Add node at the end of the queue public boolean offer(E e) { return add(e);}Two-way queue operation:
//Add public boolean offerFirst(E e) { addFirst(e); return true;}//Add public boolean offerLast(E e) { addLast(e); return true;}//Get the header node public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; }//Get the tail node public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item;}Stack operation:
//Putting the stack public void push(E e) { addFirst(e);}//Putting the stack public E pop() { return removeFirst();} Whether it is a one-way queue, a two-way queue or a stack, they actually operate on the head and tail nodes of the linked list. Their implementations are based on the four methods: addFirst(), addLast(), removeFirst(), and removeLast(). Their operations are similar to linkBefore() and unlink(), except that one is to operate on both ends of the linked list, and the other is to operate on the middle of the linked list. It can be said that these four methods are special cases of linkBefore() and unlink() methods, so it is not difficult to understand their internal implementations, so I will not introduce them here. At this point, our analysis of LinkedList is about to end, and we will summarize the key points in the whole text:
1. LinkedList is implemented based on a two-way linked list. Whether it is the addition, deletion, modification and search method or the implementation of queues and stacks, it can be implemented through operation nodes.
2. LinkedList does not need to specify capacity in advance, because based on linked list operations, the capacity of the collection will automatically increase with the addition of elements.
3. The memory occupied by the collection after LinkedList is deleted is automatically reduced, and there is no need to call the trimToSize() method like ArrayList
4. All methods of LinkedList are not synchronized, so it is not thread-safe, and should be avoided in multi-threaded environments.
5. The above analysis is based on JDK1.7, and other versions will have some differences, so it cannot be generalized.
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.