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

This article focuses on "how to understand the LinkedList source code", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to understand the LinkedList source code.

The LinkedList class diagram is as follows:

The underlying LinkedList is implemented by a two-way linked list. A linked list is like a train. Each car contains a connecting point between the car and the next car. Each node of the two-way linked list has not only a pointer to the next node, but also a pointer to the previous node. There is a Node static class in the LinkedList source code. The source code is as follows:

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;}}

A Node node consists of three parts, namely

Item: data

Next: pointer to the next node

Prev: pointer to the previous node

The main variables of LinkedList are as follows:

/ / the number of elements in the collection transient int size = 0. The pointer to the header node. * Invariant: (first = = null & & last = = null) | | * (first.prev = = null & & first.item! = null) * / transient Node first;/** * pointer to the tail node. * Invariant: (first = = null & & last = = null) | | * (last.next = = null & & last.item! = null) * / transient Node last;-add an element

LinkedList supports adding elements to any node location, providing not only the add () method commonly used in collections, but also addFirst () and addLast (). The add () method calls the addLast () method by default, that is, inserting elements into the end of the list by default.

Add () method source code:

Public boolean add (E e) {linkLast (e); return true;} 1.1 tail insert element

The linkLast () source code is as follows:

Void linkLast (E e) {final Node l = last; final Node newNode = newNode (l, e, null); last = newNode; if (l = = null) first = newNode; else l.next = newNode; size++; modCount++;}

Let's draw a diagram to demonstrate how to insert elements at the end of a linked list:

If there are no elements in the linked list

Corresponding to the if statement in the source code, if there is no element, the new node is the only element in the linked list, which is both the first node and the end node. The pointer of the former element and the pointer of the latter element are both null. Note here that the head node is not the first node, the head node simply identifies the address of the linked list.

If there are elements in the linked list

Corresponding to the else statement in the source code. Treat the new element as a Last node, and then point the next of the original Last node to the new node.

Else l.next = newNode

A picture is better than a preface. If you draw a picture, you will understand everything.

1.2 header insert element

The linkFirst () source code is as follows:

Private void linkFirst (E e) {final Node f = first; final Node newNode = newNode (null, e, f); first = newNode; if (f = = null) last = newNode; else f.prev = newNode; size++; modCount++;}

Or according to the above diagram to interpret the source code, first assign the first node to the intermediate variable f, and the new node newNode to the first node. If the linked list has no elements, both the Last node and the First node are the newly inserted node newNode, otherwise, the header pointer of the original First node is pointed to the new node.

Delete elements

LinkedList provides deletion methods based on index and element, as well as methods for deleting the first element and the last element. Here we will only analyze the method of deletion based on the index.

Public E remove (int index) {checkElementIndex (index); return unlink (node (index));}

The checkElementIndex (index) method is used to determine whether the transmitted index value is legal, and if it is illegal, an array out of bounds exception is thrown. Let's focus on how the unlink (node (index)) method deletes elements.

Node (index) method source code:

The node (index) method is to get the node of the index location according to the index.

Node node (int index) {/ / assert isElementIndex (index); / / if the subscript is specified

> 1)) {Node x = first; for (int I = 0; I

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

The unlink (Node x) source code is as follows:

E unlink (Node x) {/ / assert x! = null; final E element = x.item; final Node next = x.next; final Node prev = x.item; if (prev = = null) {first = next;} else {prev.next = next; x.prev = null;} if (next = = null) {last = prev;} else {next.prev = prev X.next = null;} x.item = null; size--; modCount++; return element;}

Draw a diagram to analyze how the deletion is done:

Suppose the first element is deleted: then its prev==NULL, we need to take its latter element (second in the figure) as the first element.

Assuming that the last element is deleted, then its next==null, we need to take its previous element (second on the way) as the last element.

If it is any element in the middle, you need to point the next pointer of its previous element to its latter element, and the prev pointer of its latter element to its previous element.

At this point, I believe you have a deeper understanding of "how to understand the LinkedList source code", might as well come to the actual operation of it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.