This is the sixth day of my participation in Gwen Challenge

An overview of the

LinkedList, whose underlying implementation is based on bidirectional LinkedList, has discontinuous storage in memory and is highly efficient in adding and deleting data elements

This is fundamentally different from ArrayList, and for a specific efficiency difference, you can run the following code to test how much time it takes to add data

ArrayList<Integer> ArrayList = new ArrayList<>();
long startTime1 = System.currentTimeMillis();
for (int i = 0; i < 100 * 100 * 100; i++) {
	ArrayList.add(i);
}
long endTime1 = System.currentTimeMillis();
System.out.println("ArrayList time:" + (endTime1 - startTime1) + "Ms");
LinkedList<Integer> LinkedList = new LinkedList<>();
long startTime2 = System.currentTimeMillis();
for (int i = 0; i < 100 * 100 * 100; i++) {
	LinkedList.add(i);
}
long endTime2 = System.currentTimeMillis();
System.out.println("LinkedList time:" + (endTime2 - startTime2) + "Ms");
Copy the code

That’s the beauty of data structures. Of course, it would be nice to know the details of memory storage in the operating system. In short, the operating system for continuous and discontinuous data processing problems, just look at the data structure, or there will be some confusion

The basic use

The differences in the underlying implementation also lead to significant differences in the methods defined in LinkedList and ArrayList

For LinkedList, it extends the following approach

• void addFirst(E e): inserts the specified element at the beginning
• void addLast(E e): inserts the specified element at the end
• getFirst(): Returns the first element of the list
• getLast(): Returns the last element of the list
• removeFirst(): Removes the first element of the list and returns it
• removeLast(): Removes the last element in the list and returns it
• E pop(): Pops the first element of the list
• void push(E e): Adds the element to the beginning of the list
• boolean isEmpty(): Checks whether the list is empty

LinkedList<String> LinkedList = new LinkedList<>();

// Add elements to the beginning and end of the list
LinkedList.addFirst("A");
LinkedList.addFirst("B");
LinkedList.addFirst("C");
LinkedList.addLast("D");

// Get the first and last element of the list
System.out.println(LinkedList.getFirst());
System.out.println(LinkedList.getLast());

// Remove the first and last element of the list, and return
System.out.println(LinkedList.removeFirst());
System.out.println(LinkedList.removeLast());
for (String s : LinkedList) {
	System.out.println(s);
}

// The first element of the list is removeFirst()
System.out.println(LinkedList.pop());

// Add the element to the beginning of the list.
LinkedList.push("E");

// Check whether the list is empty
System.out.println(LinkedList.isEmpty());
Copy the code

Initialize the

public LinkedList(a) {}Copy the code

This is the empty expansion of LinkedList, amazing. This is just a plain no-argument constructor; there is no other operation. That is, there is no initial capacity for the LinkedList

The underlying implementation is based on linked lists, and data elements are not added like an ArrayList. The addition of an element to the LinkedList only involves the change of at most two elements, the precursor and successor elements of the added element

The above image shows how LinkedList looks as it adds elements. As you can see, there is no need to move the entire element back, just to change the pointer. Next, the discussion of node classes can also deepen understanding

capacity

This section focuses on adding elements to LinkedList. How do Pointers change

A few concepts need to be understood first, with respect to leading and trailing Pointers and node classes

• Node first: the first Node in a bidirectional list
• Node last: tail Node, the last Node in a bidirectional list

Consider the Node class again, which is important

private static class Node<E> {
    // Current element
    E item;
    // The element next to the current node
    Node<E> next;
    // The previous node of the current element
    Node<E> prev;

    // Create a node class with a data element in the middle and its successors and predecessors (elements)
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev; }}Copy the code

Simply put, the addition of a data element can be encapsulated as a node class. At the same time, it specifies the previous and next data elements, in the form of node classes

It is worth mentioning that the first element only has subsequent nodes; Tail elements only have precursor nodes

Understanding these, the next is to introduce the use of node class in detail, understand the necessity of node class design

The first node

public void addFirst(E e) {
    linkFirst(e);
}
Copy the code

private void linkFirst(E e) {
    // Create a new node class f to receive the current first node
    final Node<E> f = first;
    // Create a new node class. By default, the first node is set to the successor node, and the location of the original first node is set to null, that is, there is no first node
    final Node<E> newNode = new Node<>(null, e, f);
    // assign the newNode class newNode to the global first node
    first = newNode;
    // If there is no first node
    if (f == null)
        // the newNode class newNode is used as both the first and last node
        last = newNode;
    else
        // Otherwise, set the original first node and its precursor node to the newly created node newNode
        f.prev = newNode;
    // Record the number of nodes in the container
    size++;
    // Record the number of modification operations
    modCount++;
}
Copy the code

Look! How exquisite!

If there is no data element in the container, the first node class is added as the precursor and successor node at the same time. If there are already data elements (greater than 0) in the container, that is, there are first node and last node, then the node class added will be taken as the first node, and the precursor of the original first node will be set to the node class currently added

End node

The concept of a tail node, similar to adding a first node, is briefly introduced here

public void addLast(E e) {
    linkLast(e);
}
Copy the code

void linkLast(E e) {
    // Create a new node class l to receive the current tail node
    final Node<E> l = last;
    // create a newNode class newNode and set the previous tail node to the front node and the subsequent node to null
    final Node<E> newNode = new Node<>(l, e, null);
    // Add the current node as the tail node
    last = newNode;
    // If the last node is null, the current element is the first element in the container
    if (l == null)
        // The newly created node class newNode also exists as the first node
        first = newNode;
    else
        // Otherwise, set the successor of the previous tail node to the newly created node class newNode
        l.next = newNode;
    // Add 1 to node class
    size++;
    // Modify the operand increment by 1
    modCount++;
}
Copy the code

Similar to the insertion logic of the first node, there is no difference in the addition of tail elements. Of course, there is one point to mention

public boolean add(E e) {
    linkLast(e);
    return true;
}
Copy the code

The above code is the normal element addition method for LinkedList, where it is actually called tail element addition

Intermediate nodes

Intermediate nodes are similar to the first and last nodes, as shown in the following code analysis. Strictly speaking, intermediate nodes are inserted according to the position of the index, and can also be inserted at the head or tail

public void add(int index, E element) {
    // Determine whether the index is out of bounds at the specified insert location
    checkPositionIndex(index);

    // If the specified position is equal to the actual number of nodes, add from the tail
    if (index == size)
        // Add the element to the end
        linkLast(element);
    else
        // Add the element to any position (not the tail) and extract the element node of the current index (nulled)
        // Node (index) gets the node class by index (critical)
        linkBefore(element, node(index));
}
Copy the code

Node<E> node(int index) {
    // Check the index is in the top half of the list, the bottom half of the list, through the bit operation
    if (index < (size >> 1)) {
        // Create a new node class x and default the first node because the first node's precursor is null
        Node<E> x = first;
        // Start traversing the index to verify the node class represented by the current index
        for (int i = 0; i < index; i++)
            // Note that the next successor is itself a node class, and there is a corresponding next
            // Continuously traverses the index to obtain the node object at the specified index
            x = x.next;
        // Returns the newly created node
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        returnx; }}Copy the code

void linkBefore(E e, Node<E> succ) {
    // Create a new node class pred to receive the precursor nodes of suCC
    final Node<E> pred = succ.prev;
    // create a newNode class newNode
    final Node<E> newNode = new Node<>(pred, e, succ);
    // The precursor node of succ is set to newNode
    succ.prev = newNode;
    // PreD receives the precursor node of suCC, only the first node has no precursor node
    if (pred == null)
        // Insert the index at position 0, set newNode as the first node
        first = newNode;
    else
        // Insert the index not 0 and tail, but middle. Set newNode as the successor of pred
        pred.next = newNode;
    size++;
    modCount++;
}
Copy the code

The addition of the middle node is indeed some detour, relative to the previous first and last node addition. Here’s a quick summary

1. Determines whether the current index is out of bounds
2. Determine if the current index is a tail index and add it as a tail node
3. Gets the original node of the index position and determines whether the current index is the leading node
4. If it is not a front node, the data element is inserted in the middle, with the original node moved one bit back

Very good, very good design! For example, binary lookup is used when a node class is obtained by index. And, in the second half, if the index position is the next-to-last, no traversal is required. Upper part from front to back; Lower half from back to front

At this point, the addition of nodes to the LinkedList is over, a small gain

summary

In LinkedList, the most important concept is the node class. The rest methods will not be introduced for the moment, and can be filled up in spare time