preface

Collections are a common object in writing code and a great way to store data, but do you really understand the internal implementation?

Java version 1.8Copy the code

Idea View inheritance diagram: Ctrl+Alt+ U (cursor on the class to view).

The Collection interface

This interface is simply explained here in my Collection interface, and will not be explained here

LinkedList collection description

Questions: Explore the internal implementation with questions.

  • 1. What is the way LinkedList stores elements (data structure)?
  • 2. Does LinkedList have the same expansion mechanism as ArrayList?

How do I create a collection of LinkedList?

// Create a collection of LinkedList
LinkedList<Integer> list2 = new LinkedList<>();

// It is also possible to create a collection of linkedLists in polymorphic form
List<Integer> list2 = new LinkedList<>(); 

// Note that there are differences between the two objects.
Copy the code

attribute

// The number of elements in the set
transient int size = 0;
/ / head node
transient Node<E> first;
/ / end nodes
transient Node<E> last;
Copy the code

transient

This is a keyword that does not serialize tagged attributes, is used to tag attributes, and cannot tag methods and objects

The constructor

// a no-parameter construct
public LinkedList(a) {}// a constructor with no arguments puts an element from a collection into the LinkedList
public LinkedList(Collection<? extends E> c) {
    this(a); addAll(c); }Copy the code

A brief description of the collection CRUD

Coming back to the above question, what is the difference

// Create a collection of LinkedList
LinkedList<Integer> list2 = new LinkedList<>();

// It is also possible to create a collection of linkedLists in polymorphic form
List<Integer> list2 = new LinkedList<>(); 

// Note that there are differences between the two objects.
Copy the code

Just missing some of the LinkedList’s own methods

// Create instance objects mainly in the form of polymorphisms in
List<Integer> list2 = new LinkedList<>(); 
Copy the code

What polymorphism is: compile to the left, run to the right.

Let’s talk about adding, deleting, changing, and checking

The Node object

Node: Node

// This is a private static inner class of LinkedList
private static class Node<E> {
    E item; // Current element
    Node<E> next; // Next node
    Node<E> prev; // Last node
    / / structure
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev; }}Copy the code

increase

Append to the element linkLast(E E)

public boolean add(E e) {
    linkLast(e);  // The default is to add to the end of the element
    return true;
}
// The last method is called
void linkLast(E e) {
    // Get the last node of the LinkedList property
    final Node<E> l = last;  / / end nodes
    // Create a new node with one node, the current element, and the next node
    final Node<E> newNode = new Node<>(l, e, null);
    // Assign the new node to the last node to save
    last = newNode;
    if (l == null)  // If the new node is equal to null, the new node is overwritten to the head node.
        first = newNode;
    else
        l.next = newNode; // The new node is assigned to the next node in the tail node.
    size++;  // Add one to the element
    modCount++; // Add one
}
Copy the code

Append to element addFirst(E E)

private void linkFirst(E e) {
    // Get the header of the LinkedList property
    final Node<E> f = first;
    // Create a new node with one node, the current element, and the next node
    final Node<E> newNode = new Node<>(null, e, f);
    // Assign the new node to the head node to save
    first = newNode;
    if (f == null)/if the new node equalsnullLast = newNode; last = newNode;else
        f.prev = newNode; // The new node is assigned to the previous node in the head node.
    size++;  // Add one to the element
    modCount++; // Add one
}
Copy the code

Summary:

  • Either (header) or (tail) inserts, the first time you add an element, verify that the (header) or (tail) element attributes are null.
  • Question:
    • 1. What is the way LinkedList stores elements (data structure)?
      • The form of the node is stored, and simply put, it is assumed that there are three nodes, and the elements of the middle node have the data of the previous node and the next node. This data structure is calledTwo-way linked list
    • 2. Does LinkedList have the same expansion mechanism as ArrayList?

      • No, because the data stored is in memory, it can store a lot of data, the question is whether the memory can hold so much data, too much data will lead to insufficient memory

delete

RemoveLast () returns data for the last element

public E removeLast(a) {
    final Node<E> l = last;
    if (l == null) // If there is no data, an exception is thrown
        throw new NoSuchElementException();
    return unlinkLast(l);
}
// Specific operation content
private E unlinkLast(Node<E> l) { // Pass to the last element of the set (tail node)
    // assert l == last && l ! = null;
    final E element = l.item;  // Get the current element of the last node
    final Node<E> prev = l.prev; // Assign the last node of the last node to prev
    l.item = null;  // Set the current element of the last node to null
    l.prev = null; // help GC to help the garbage collection mechanism
    last = prev;  // Assign the last node of the trailing node to the trailing node of the LinkedList attribute
    if (prev == null) // Set the LinkedList attribute header to NULL if the last node of the LinkedList attribute is null
        first = null; // There is only one element in the set
    else
        prev.next = null;  // Otherwise, set the next node in the tail node to NULL
    size--; // Element minus one
    modCount++; // The number of operations is increased by one
    return element; Return the current element
}
Copy the code

RemoveFirst () returns the first element data

public E removeFirst(a) {
    final Node<E> f = first;
    if (f == null) // If there is no data, an exception is thrown
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
// Specific operation content
private E unlinkFirst(Node<E> f) { // Pass the first element of the set (the head node)
    // assert f == first && f ! = null;
    final E element = f.item; // // gets the current element of the head node
    final Node<E> next = f.next;  // Assign the next node in the head node to next
    f.item = null; // Set the current element of the head node to NULL
    f.next = null; // help GC to help the garbage collection mechanism
    first = next; // Assign the next node of the first node to the last node of the LinkedList attribute
    if (next == null) // If the next node of the head node is null, set the end node of the LinkedList attribute to NULL
        last = null; // There is only one element in the set
    else
        next.prev = null; // Otherwise, set the previous node in the head node to NULL
     size--; // Element minus one
    modCount++; // The number of operations is increased by one
    return element; Return the current element
}
Copy the code

Remove (int index), remove(Object O), remove() these methods implement principle.

change

public E set(int index, E element) { // Return the element that was changed before
    // Check data out of bounds exception, mainly by size to judge
    checkElementIndex(index);
    // Returns the current node of the specified index
    Node<E> x = node(index);
    // Save the old node to oldVal
    E oldVal = x.item;
    // When data is assigned to the current element in the current node
    x.item = element;
    return oldVal; // Return the element that was changed before
}
// Get the corresponding node by subscript
Node<E> node(int index) {
     // assert isElementIndex(index);
     // >> Is the right displacement calculation
     /* Size >> n² */
    // This is similar to binary search, called half search
    // If 8 < (15 >> 1) = 7, I'm looking for the 8th element
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next; // Get the next node of the former node
        return x;
    } else { // Find the element of the last node backwards
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev; // Get the last node of the last node
        returnx; }}Copy the code

check

Query first getFirst()

public E getFirst() { final Node<E> f = first; If (f == null) throw new NoSuchElementException(); return f.item; // Return the current element of the head node}Copy the code

Query last getLast()

public E getLast() { final Node<E> l = last; If (l == null) throw new NoSuchElementException(); return l.item; // Return the current element of the last node}Copy the code

Get (int index);

Public E get(int index) {public E get(int index) {public E get(int index) {public E get(int index) { // This method is explained above. return node(index).item; }Copy the code

The illustration

Conclusion:

  • The underlying implementation of LinkedList is a LinkedList structure, and the structure of the LinkedList is a bidirectional LinkedList structure. The general idea is that the first node will retain the position of the next node, and the next node will retain the position of the next node, and there is no previous node or the next node is null
  • LinkedList can hold null values, non-thread-safe collections, and duplicate elements
  • LinkedList is a LinkedList structure, so there is no capacity shortage, so there is no capacity expansion.

Java Collection series -ArrayList internal exploration

Throw in chicken soup


Can’t deny you later, but in my eyes you are and I said later is just a whim. Can’t deny you later, but in my eyes you are and I said later is just a whim.