LinkedList brief introduction
This is the back-end small class of the monastery. Each article is shared from
[background introduction] [knowledge analysis] [common problems] [solutions] [coding practice] [extended thinking] [more discussion] [References]
Eight aspects of in-depth analysis of back-end knowledge / skills. This article shares:
[brief introduction to LinkedList]
Hello, I am the 27th java student of Beijing Branch of it Academy. I am an honest, pure and kind java programmer.
Today, I'd like to share with you a brief introduction to LinkedList, a knowledge point in in-depth thinking, Java task 10 on the official website of the Academy
1. Background introduction
1. Collection interface: the collection interface is the root node of all collection classes. Collection represents a rule. All classes that implement the collection interface follow this rule
2. List interface: list is the sub interface of collection. It is an ordered, repeatable and nullable collection of elements (maintaining the element order according to the insertion order)
3. Abstractcollection class: the skeleton implementation class of the collection interface, which minimizes the workload required to implement the collection interface
4. Abstractlist class: the skeleton implementation class of the list interface, which minimizes the workload required to implement the list interface
5. Clonable interface: the class that implements the interface can call object Clone () method, legally copy the field of this class instance. If the instance does not implement the clonable interface, call obejct Clonenotsupportexception will be thrown for the clone () method. Under normal circumstances, classes that implement the clonable interface will override object with public methods clone()
6. Serializable interface: this interface is implemented, which indicates that the class can be serialized and deserialized. Specific
7. Deque interface: deque defines a linear collection that supports inserting and deleting elements at both ends. Deque is actually the abbreviation of "double ended queue". Most implementations of deque interfaces do not limit the number of elements, but this queue supports both implementations with and without capacity constraints, For example, LinkedList is an implementation with capacity constraints, and its maximum capacity is integer MAX_ VALUE
8. Abstractsequentiallist class: provides the backbone implementation of the list interface, minimizing the work required to implement this interface supported by "continuous access" data storage (such as linked list). For random access data (such as array), abstractlist should be used first rather than abstractsequentiallist class
2. Knowledge analysis
Constructor / / number of collection elements: transient int size = 0// The chain header node is transient node first// The end node of the linked list is transient node last// Do nothing public linkedlist() {} / / call public Boolean addall (collection C) to insert all elements of collection C into the linked list public LinkedList (collection C) {this(); addall (c);} The construction method does little.
Node structure: private static class node {e item; / / element value node next; / / post node prev; / / front node
Node(Node prev,E element,Node next) { this.item = element; this.next = next; this.prev = prev; } } It can be seen that this is a two-way linked list.
Add 1 addall, then add addall first
//Addall, batch add public Boolean addall (collection C) {return addall (size, c); / / insert all elements in collection C with size as the insertion subscript} / / insert all elements in collection C with index as the insertion subscript public Boolean addall (int index, collection C) {checkpositionindex (index); / / check the out of bounds [0, size] closed interval
Object[] a = c.toArray();// Get the target set array int numnew = a.length// Number of new elements if (numnew = = 0) / / if the number of new elements is 0, it does not increase and returns false return false;
Node pred,succ; // The front node of the index node, Post node if (index = = size) {/ / append data succ = null at the end of the linked list. / / the post node of the size node (end of queue) must be null PRED = last. / / the front node is the end of queue} else {succ = node (index); / / take the index node as the post node PRED = succ.prev. / / the front node is the previous node of the index node} / / the linked list increases in batch, The for loop is used to traverse the original array and insert nodes in turn. The ArrayList is compared through system Arraycopy completes the for (object o: a) {/ / traverse the nodes to be added. @ suppresswarnings ("unchecked") e e = (E) O; node newnode = new node < > (PRED, e, null); / / build a new node with the preceding node and element value E, if (PRED = = null) //If the front node is empty, it means the head node first = newnode; Else / / otherwise, ask the new node pred next = newNode; pred = newNode;// Step by step, the current node is the front node. Prepare for the next node addition}
If (succ = = null) {/ / after the loop ends, judge if the post node is null. This indicates that it is attached at the end of the queue. Last = PRED; / / set the end node} else {pred.next = succ; / / otherwise, it is a node inserted in the queue. Update the pre node. Prev = PRED; / / update the pre node of the post node}
size += numNew; // Modify quantity size modcount + +// Modify modcount return true;}// Query the node according to the index, node node (int index) {/ / assert iselementindex (index); / / when a node is obtained by subscript, (add, query), it will be halved according to whether the index is in the first half or the second half to improve the query efficiency if (index < (size > > 1)) {node x = first; for (int i = 0; I < index; I + +) x = x.next; return x;} else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } Private Boolean ispositionindex (int index) {return index > = 0 & & index < = size; / / check during insertion. The subscript can be size [0, size]} summary:
The batch increase of linked list depends on the for loop to traverse the original array and insert nodes in turn. The ArrayList is compared through system When arraycopy completes batch addition and obtains a node through subscript, (add select), it will be halved according to whether the index is in the first half or the second half to improve query efficiency. 2. Insert a single node add / / insert a node at the end: add public Boolean add (e e) {linklast (E); return true;}
//Generate a new node and insert it at the end of the linked list to update the last / first node. Void linklast (e e) {final node L = last; / / record the original tail node final node newnode = new node < > (L, null); / / take the original tail node as the front node of the new node last = newnode; / / update the tail node if (L = = null) / / if the original list is empty, you need to update the head node first = newnode; else / / otherwise, update the rear node of the original tail node to the current tail node (new node) l.next = newnode; size + +; / / modify size modcount + +; / / modify modcount} / / at the specified subscript and index, insert a node public void add (int index, e element) {checkpositionindex (index); / / check whether the subscript is out of bounds [0, size] if (index = = size) / / insert linklast (element) after the tail node; else / / insert linkbefore (element, node (index) in the middle ); } // Before the succ node, Insert a new node e void linkbefore (e e, node succ) {/ / assert succ! = null; / / save the preceding node of the post node final node PRED = succ.prev; / / build a new node with the preceding and subsequent nodes and element values E. final node newnode = new node < > (PRED, succ); / / the new node new is the preceding node succ.prev = newnode of the original node succ; if (PRED = = null) //If the previous preceding node is empty, succ is the original header node. Therefore, the new node is the current head node, first = newnode; Else / / otherwise, the post node of the pre node is new pred next = newNode; size++;// Modify quantity modcount + +// Modify modcount} summary: * adding will modify modcount
Delete remove / / delete: remove the target node public e remove (int index) {checkelementindex (index); / / check whether the subscript [0, size) return unlink (node (index)); / / delete a node from the linked list} / / delete the X node e unlink (node x) from the linked list {/ / assert X! = null; final e element = x.item; / / the element value of the current node final node next = x.next; / / the post node of the current node final node prev = x.prev; / / the front node of the current node
If (prev = = null) {/ / if the front node is empty (indicating that the current node is originally the head node), first = next; / / then the head node is equal to the back node} else {prev.next = next; x.prev = null; / / set the front node of the current node to empty}
If (next = = null) {/ / if the post node is empty (indicating that the current node was originally the tail node), last = prev; / / then the tail node is the front node} else {next.prev = prev; x.next = null; / / set the post node of the current node to empty}
x.item = null; // Set the current element value to null size --// Modify quantity modcount + +// Modify modcount return element// Return the retrieved element value} private void checkelementindex (int index) {if (! Iselementindex (index)) throw new indexoutofboundsexception (outofboundssg (index));}// Subscript [0, size) private Boolean iselementindex (int index) {return index > = 0 & & index < size;} Delete the specified node in the linked list:
//Because null elements should be considered, public Boolean remove (object o) {if (o = = null) {/ / if a null node is to be deleted (it can be seen from remove and add that null elements are allowed) / / traverse each node and compare for (node x = first; X! = null; X = x.next) {if (x.item = = null) {unlink (x); return true;}}}} else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } // Delete node x from the linked list. E unlink (node x) {/ / assert X! = null; final e element = x.item; / / continue the element value to return final node next = x.next; / / save the post node of the current node. Final node prev = x.prev; / / the front node
If (prev = = null) {/ / the front node is null, first = next; / / then the first node is next} else {/ / otherwise, update the rear node of the front node prev.next = next; x.prev = null; / / remember to set the front node of the node to be deleted to null} / / if the rear node is null, it is the tail node if (next = = null) {last = prev;} Else {/ / otherwise, update the front node of the post node. Next. Prev = prev; x.next = null. / / remember that the post node of the deleted node is null} / / set the element value of the deleted node to null so that GC x.item = null; size--;// Modify size modcount + +// Modify modcount return element// Return the deleted element value} deletion will also modify modcount. To delete by subscript, first find the node according to the index, and then unlink the node from the linked list. When deleting by element, you will first traverse the linked list to find out whether there is the node. Considering that null value is allowed, you will traverse twice, and then unlink it.
Change set public e set (int index, e element) {checkelementindex (index); / / check for out of bounds [0, size) node x = node (index); / / take out the corresponding node e oldval = x.item; / / save the old value for returning x.item = element; / / overwrite the old value with the new value return oldval; / / return the old value} change the node according to the index, and then replace the value without modifying modcount
Query get. / / query the node according to the index
Public e get (int index) {checkelementindex (index); / / judge whether it is out of bounds [0, size) return node (index). Item; / / call the node() method to get the node,} / / query the subscript according to the node object
Public int indexof (object o) {int index = 0; if (o = = null) {/ / if the target object is null / / traverse the linked list for (node x = first; X! = null; X = x.next) {if (x.item = = null) return index; index + +;}} Else {/ / / / traverse the linked list for (node x = first; X! = null; X = x.next) {if (o.equals (x.item)) return index; index + +;}} return -1; } // Traverse the linked list from tail to head to find the node with the target element value of O
public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } Do not modify modcount
Toarray(), let's also take a look at toarray() After all, this is a high-frequency API
Public object [] toarray() {/ / new a new array, then traverse the linked list, store each element in the array, and return object [] result = new object [size]; int i = 0; for (node x = first; X! = null; X = x.next) result [i + +] = x.item; return result;}
3. Frequently asked questions
To summarize LinkedList?
4. Solutions
LinkedList is a bidirectional linked list.
The batch increase of linked list depends on the for loop to traverse the original array and insert nodes in turn. The ArrayList is compared through system Arraycopy completes batch addition. Adding will certainly modify modcount. When a node is obtained by subscript, (add select), it will be halved according to whether the index is in the first half or the second half to improve the query efficiency
Deleting will also modify modcount. To delete by subscript, first find the node according to the index, and then unlink the node from the linked list. When deleting by element, you will first traverse the linked list to find out whether there is the node. If so, unlink the node from the linked list.
To change, first find the node according to the index, and then replace the value. Do not modify modcount. The query itself is to find the node according to the index. Therefore, its crud operation involves the operation of finding nodes according to index.
5. Coding practice
See video for details
6. Expand thinking
7. References
The list set is as simple as this [source code analysis]:
https://segmentfault.com/a/1190000014240704
8. More discussion
Q1: what is the deque interface and what kind of specification does it define? A1: deque indicates a two terminal queue. Double ended queues are queues that can be inserted and deleted at both ends. Deque is a more powerful interface than stack and queue. It implements the functions of stack and queue at the same time. Arraydeque and linkelist implement the deque interface
Q2: LinkedList is a two-way linked list. What is its underlying implementation and what operations are included?
A2: it can be seen in the summary section
Q3: what are the characteristics and differences between ArrayList and LinkedList?
A3：
The essence of the difference between arrays and linked lists is the difference between continuous space storage and discontinuous space storage, mainly in the following two points:
That's all for today's sharing. You are welcome to like, forward, leave messages and make bricks~
Ppt link video link