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

This article introduces the relevant knowledge of "how to analyze LinkedList source code from the perspective of interview". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Note: the jdk versions used in this series of articles are all java8

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; / * pointer to the first 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

First, add elements

LinkedList supports adding elements at 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 insert elements at the tail

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.

II. 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

< 一半元素数量，则从首结点开始遍历 // 否则，从尾结点开始遍历 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; iMurt -) x = x.colors; return x;}}

The unlink (Nodex) 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:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

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 in the figure) 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.

This is the end of the content of "how to analyze the LinkedList source code from the perspective of the interview". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.