Shulou(Shulou.com)06/02 Report--

In this issue, the editor will bring you about the use of LinkedList in java. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

Overall architecture

The underlying data structure is a two-way linked list, suitable for scenarios with sequential iterations.

First: header node

Last: tail nod

When the linked list is empty, last and first are all the same node, pointing to null before and after.

Because it is a two-way linked list, there is no size limit as long as the machine memory is strong enough.

Node has three attributes: prev, next, and item

Private static class Node {E item;// node value Node next; / / points to the next node Node prev; / / points to the previous node / / initialization parameter order is: the previous node, its own node value, the latter node Node (Node prev, E element, Node next) {this.item = element; this.next = next; this.prev = prev }} Source Code parsing

I. add or delete

New header: addFirst

/ / append private void linkFirst (E e) {/ / the header node to the temporary variable final Node f = first; / / the new node, the previous node points to null,e as the new node, f is the next node of the new node, and the current value is the value of the header node final Node newNode = newNode (null,e, f); / / the new node becomes the header node first = newNode / / the header node is empty, that is, the linked list is empty, and the header and tail node is a node if (f = = null) last = newNode; / / the previous node of the previous header node points to the current node else f.prev = newNode; size++; modCount++;}

New tail: add

/ / append the node void linkLast (E e) {/ / temporarily store the tail node data final Node l = last; / / create a new node, initialize the input parameter meaning: / / l is the previous node of the new node, the current value is the tail node value / / e indicates the current new node, and the last node after the current new node is null final Node newNode = newNode (l, e, null) / / append the new node to the tail last = newNode; / / if the linked list is empty (l is the tail node, the tail node is empty, the list is empty), the head and tail are the same node, and both are the new node if (l = null) first = newNodebrand! [photo description] (/ / img.mukewang.com/5d5fc69600013e4803600240.gif) / / otherwise point the next node of the front and tail node to the current tail node. Else l.next = newNode; / / size and version change size++; modCount++;}

Delete

Similar to the new, you can delete unlinkFirst in the head and unlinkLast in the tail.

/ / remove node f from scratch is the chain header node private E unlinkFirst (Node f) {/ / take out the value of the header node as the return value of the method final E element = f.item; / / take out the next node of the header node final Node next = f.next; / / help GC recycle the header node f.item = null; f.next = null / / the next node of the header node becomes the header node first = next; / / if the next is empty, it indicates that the linked list is empty if (next = = null) last = null; / / the linked list is not empty, and the previous node of the header node points to null else next.prev = null; / / modify the linked list size and version size--; modCount++; return element;}

Query

LinkedList uses dichotomy for circular query (which can be used for reference)

/ / query node Node node (int index) according to the linked list index location {/ / if index is in the first half of the queue, start from scratch. Size > > 1 means size divided by 2. If (index

< (size >

> 1)) {Node x = first; / / until the previous node of the for loop to index stops for (int I = 0; I

< index; i++) x = x.next; return x; } else {// 如果 index 处于队列的后半部分，从尾开始找 Node x = last; // 直到 for 循环到 index 的后一个 node 停止 for (int i = size - 1; i >

Index; iMurt -) x = x.colors; return x;}}

2. Iterator

ListIterator: provides forward and backward iterations

/ / two-way iterator private class ListItr implements ListIterator {Node location when private Node lastReturned;// last executed the next () or previos () method private Node next;// next node / / expectedModCount: expected version number; modCount: current latest version number private int expectedModCount = modCount;. }

From beginning to end:

/ / determine whether there is the next element public boolean hasNext () {return nextIndex

< size;// 下一个节点的索引小于链表的大小，就有}// 取下一个元素public E next() { //检查期望版本号有无发生变化 checkForComodification(); if (!hasNext())//再次检查 throw new NoSuchElementException(); // next 是当前节点，在上一次执行 next() 方法时被赋值的。 // 第一次执行时，是在初始化迭代器的时候，next 被赋值的 lastReturned = next; // next 是下一个节点了，为下次迭代做准备 next = next.next; nextIndex++; return lastReturned.item;} 从尾到头： // 如果上次节点索引位置大于 0，就还有节点可以迭代public boolean hasPrevious() { return nextIndex >

0;} / / take the previous node public E previous () {checkForComodification (); if (! hasPrevious ()) throw new NoSuchElementException (); / / next is an empty scenario: 1: it is the first iteration, take the tail node (last) 2: the tail node was deleted in the last operation / / next is not empty scenario: it means that iteration has taken place. Just take the previous node (next.prev) lastReturned = next = (next = = null)? Last: next.prev; / / Index location change nextIndex--; return lastReturned.item;}

Delete:

Public void remove () {checkForComodification (); / / lastReturned is the value to be deleted in this iteration, which can be divided into the following two cases: / / lastReturned is empty, indicating that the caller has not actively executed next () or previos (). The direct error / / lastReturned is not empty, but the value if (lastReturned = = null) throw new IllegalStateException () assigned when the last next () or previos () method is executed. Node lastNext = lastReturned.next; / / Delete the current node unlink (lastReturned) / / next = = lastReturned scenario analysis: recursive order from tail to head, first iteration, and delete the last element / / in this case, lastReturned = next = last is set in the previous () method, so next and lastReturned will be equal if (next = = lastReturned) / / then lastReturned is the tail node, lastNext is null, so next is also null, so when previous () executes If next is found to be null, the tail node will be assigned to next next = lastNext. Else nextIndex--; lastReturned = null; expectedModCount++;} above is what is the use of LinkedList in the java shared by the editor? if you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.