Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

One, foreword

Today we continue to learn source code together, before we learned the ArrayList implementation, so today we will illustrate the LinkedList implementation principle.

Note: This article is based on JDK1.8

Two, preparation before class

When it comes to LinkedList, I believe all of you can say a lot of words, such as bidirectional LinkedList, ordered set, add and delete fast query slow, etc. After all, this is also a frequent interview question, back n times, then the next question is, what is a bidirectional LinkedList? Why add and delete fast query slow? How does the addition and deletion work? What is the iterative approach? . .

In the face of this series of problems, today spend elder brother to take small partners to go, read affirmation learned.

  • What is a linked list?

That’s our first question today. To understand what a linked list is, let’s start with a simple one-way linked list. Let’s look at this nice illustration.

As can be seen from the figure, each linked list is composed of nodes, which we call Node. The Node structure of one-way linked list uses data which stores its own content and next, which represents the position of the next Node (reference).

  • What is a bidirectional list

The structure of each Node is composed of prev, data and next. Compared with the one-way list, there is one more preV used to point to the last Node in the bidirectional list. Firstly, the functions of each attribute in the following figure are briefly described:

  • Prev: Stores a reference to the previous node.
  • Data: stores the details of the current node.
  • Next: Stores a reference to the next node;
  • First: the head of a bidirectional list whose last node is null;
  • Last: the end of a bidirectional list whose next node is null;

Note that if the list stores no data, it has the same First and Last, and null prev and next.

Let’s look at the implementation of Node in the LinkedList code:

private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; }}Copy the code

Three, LinkedList source analysis

With all that in mind, we will formally analyze the source code of LinkedList, mainly to discuss the implementation principle of the new delete query of LinkedList.

  • End add node (linkLast)

There are two ways to add a LinkedList: header add and tail add.

Void linkLast(E E) {// Void linkLast(E E) {final Node<E> l = last; Final Node<E> newNode = newNode <>(l, E, null); // update the newNode to the tail node last = newNode; If (l == null) // If (l == null) // First = newNode; Else_next = newNode; else_next = newNode; // update list size and version size++; modCount++; }Copy the code

The above code can be illustrated as follows:

  • First, create a node, Node4, and update the current node to a tail node

  • If the list is not null, the next reference in Node3, the end node of the current list, points to the current node

  • If the linked list is empty, the current node is set as the head node. The structure of the linked list is shown below

  • Header add node (linkFirst)

The method of adding headers is basically the same as above, except that a new node is appended to the head of the list.

// private void linkFirst(E E) {// Private void linkFirst(E E) {// Final void linkFirst(E E); // Create a newNode, next points to the head Node final Node<E> newNode = newNode <>(null, E, f); // set the newNode to the head node first = newNode; If (f == null) // If (f == null) last = newNode; Else // the list is not empty. The prev of the original head node points to the newNode. // update list size and version size++; modCount++; }Copy the code

  • Header delete node (unlinkFirst)

There are also two ways to delete a node. First, let’s talk about tail deletion. The commonly used remove method is to delete the head.

Private E unlinkFirst(Node<E> f) {final E element = f.tem; private E unlinkFirst(Node<E> f) {final E element = f.tem; final Node<E> next = f.next; // Set the head node to null to help GC recover F.tem = null; f.next = null; // Set the next node as the head node first = next; If (next == null) last = null; if (next == null) last = null; else next.prev = null; size--; modCount++; // Return element; }Copy the code

Continuing with the old, graphical approach, let’s look at the implementation:

  • Set data and next of the head node to null to facilitate GC to reclaim resources

  • If there is more than one element in the current list, the node pointed to by Next in the original head node (Node1) is set as the head node (Node2), and the prev in Node2 is empty, thus completing the deletion process

  • If the list contains only the current node, the end node is set directly to NULL

  • Tail delete node (unlinkLast)

Tail deletion is almost the same as the above method, a brief introduction to the code.

Private E unlinkLast(Node<E> l) {final E element = l.tem; private E unlinkLast(Node<E> l) {final E element = l.tem; Final Node<E> prev = l.prev; final Node<E> prev = l.prev; l.item = null; l.prev = null; // Set last = prev; If (prev == null) first = null; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; }Copy the code

  • Find the specified node

LinkedList uses dichotomy to find data. It first judges the position of the target node, whether it is the first half or the last half, and then finds the target node through traversing, thus improving the query efficiency.

Node<E> Node (int index) {//size >> 1: If (index < (size >> 1)) {Node<E> x = first; if (index < (size >> 1)) {Node<E> x = first; For (int I = 0; for (int I = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; For (int I = sie-1; i > index; i--) x = x.prev; return x; }}Copy the code

Four,

LinkedList is a two-way LinkedList structure at the bottom, which can be used as a stack or queue to operate. It is suitable for fast insertion and deletion. At the same time, it is also a high-frequency interview question.