React source code is used in a lot of algorithm tricks, mainly including bit operations, depth first traversal, linked list operations, stack operations, heap sort, etc. This article based on [email protected], comb out React source code in the use of linked list operation skills.

concept

A Linked List is a linear list that stores data not in a linear order, but in Pointers from each node to the next. Because they do not have to be stored sequentially, linked lists can be O(1) complex when inserted, but it takes O(n) time to find a node or access a specific number of nodes.

  1. Unidirectional linked list: Each node contains two fields, an information field and a pointer field. This pointer points to the next node in the list, and the last node points to a null value.
  2. Bidirectional linked list: Each node has two connections, one to the previous node (the first node points to a null value) and the other to the next node (the last node points to a null value).
  3. Circular list: Based on a unidirectional list, the first and last nodes are joined together.

The basic use

  1. Node insertion, time complexityO(1)
  2. Node lookup, time complexityO(n)
  3. Node deletion, time complexityO(1)
  4. Reverse the list, time complexityO(n)
// Define the Node type
function Node(name) {
  this.name = name;
  this.next = null;
}

/ / list
function LinkedList() {
  this.head = new Node('head');

  // Find the node before the node
  this.findPrevious = function(node) {
    let currentNode = this.head;
    while(currentNode && currentNode.next ! == node) { currentNode = currentNode.next; }return currentNode;
  };

  // Insert a new node newElement after node
  this.insert = function(name, node) {
    const newNode = new Node(name);
    newNode.next = node.next;
    node.next = newNode;
  };

  // Delete the node
  this.remove = function(node) {
    const previousNode = this.findPrevious();
    if(previousNode) { previousNode.next = node.next; }};// Reverse the list
  this.reverse = function() {
    let prev = null;
    let current = this.head;
    while (current) {
      const tempNode = current.next;
      // Resets the next pointer to point to the previous node
      current.next = prev;
      // Move the cursor back
      prev = current;
      current = tempNode;
    }
    // Reset the head node
    this.head = current;
  };
}
Copy the code

Use scenarios in React

In React, linked lists are used very frequently, mainly in the properties of the fiber and hook objects.

Fiber object

The properties of the Fiber object are described in the React high-frequency object, which lists four linked properties.

  1. Effect list (chained queue): Stores child nodes with side effects. The element of this queue is the Fiber object

    • fiber.nextEffect: One-way linked list pointing to the next fiber node with side effects
    • fiber.firstEffect: points to the first fiber node in the side effect list.
    • fiber.lastEffect: points to the last fiber node in the side effect list.

    Note: Only the structure of the list is shown here, the structure above will be explained in detail in the Section on Fiber Tree Construction.

  2. UpdateQueue linked list (chained queue): Stores the status to be updated. The elements in this queue are update objects

    • fiber.updateQueue.pending: storagestateThe updated queue (chained queue),classType nodestateAfter you change it, you create oneupdateObject to the queue. Since this queue is a circular queue, in order to facilitate the addition of new elements and quickly get the first element of the queue, sopendingThe pointer points to the last element in the queue.

    Note: Only the structure diagram of the list is shown here. The structure of the figure above will be explained in detail in the section of state Components (Class and Function).

Hook object

The properties of the Hook object are described in the React high frequency object. The Hook object has the. Next property, so the Hook object itself is a node in the list.

In addition, hook.queue.pending also forms a linked list, and hook linked list and hook.queue.pending linked list are simultaneously represented in the figure, and the structure obtained is as follows:

Note: Only the structure diagram of the linked list is shown here, and the above structure will be explained in detail in the hook Principle section.

List to merge

In the react after the update, will list combined ways to wait for updated (pending status) queue (updateQueue) incorporated into the base queue (class components: fiber. UpdateQueue. FirstBaseUpdate; Function component: hook. BaseQueue), select update objects with sufficient priority by traversing baseQueue, and combine them into the final component state. This process takes place in the Reconciler phase and involves the class and Function components, respectively.

Specific scenarios:

  1. The class in the component

    • In class component calls setState, will create the update object and add to fiber. The updateQueue. Shared. Pending chain queue (source address).

      export function enqueueUpdate<State> (fiber: Fiber, update: Update<State>) {
  const updateQueue = fiber.updateQueue;
  // ...
  const sharedQueue: SharedQueue<State> = (updateQueue: any).shared;
  / / add new update object to the fiber. The updateQueue. Shared. The pending list
  const pending = sharedQueue.pending;
  if (pending === null) {
    update.next = update;
  } else {
    update.next = pending.next;
    pending.next = update;
  }
  sharedQueue.pending = update;
}
Copy the code

      Because of the fiber. UpdateQueue. Shared. Pending is a circular linked list, so fiber. The updateQueue. Shared. Pending forever pointing at the end of the element (guarantee quick add new elements)

    • In the fiber tree construction phase (or the reconciler stage), the fiber. The updateQueue. Shared. Pending merger to fiber. The updateQueue. FirstBaseUpdate queue (source address).

      export function processUpdateQueue<State> (workInProgress: Fiber, props: any, instance: any, renderLanes: Lanes,) :void {
  // This is always non-null on a ClassComponent or HostRoot
  const queue: UpdateQueue<State> = (workInProgress.updateQueue: any);
  let firstBaseUpdate = queue.firstBaseUpdate;
  let lastBaseUpdate = queue.lastBaseUpdate;
  // Check if there are pending updates. If so, transfer them to the base queue.
  let pendingQueue = queue.shared.pending;
  if(pendingQueue ! = =null) {
    queue.shared.pending = null;
    // The pending queue is circular. Disconnect the pointer between first
    // and last so that it's non-circular.
    const lastPendingUpdate = pendingQueue;
    const firstPendingUpdate = lastPendingUpdate.next;
    lastPendingUpdate.next = null;
    // Append pending updates to base queue
    if (lastBaseUpdate === null) {
      firstBaseUpdate = firstPendingUpdate;
    } else{ lastBaseUpdate.next = firstPendingUpdate; } lastBaseUpdate = lastPendingUpdate; }}Copy the code

  2. The function component

    • When you use the Hook object (useState) in the function component and change the value of the Hook object (internal dispatchAction), you also create an update(Hook) object and add it to the chained queue (source address) of hook.queue.pending.

    • Hook. Queue. Pending is a circular linked list (with fiber. UpdateQueue. Shared. Are similar in the structure of the pending)

      function dispatchAction<S.A> (fiber: Fiber, queue: UpdateQueue
           
            , action: A,
           ,>) {
  / /... Omit part of the code
  const pending = queue.pending;
  if (pending === null) {
    // This is the first update. Create a circular list.
    update.next = update;
  } else {
    update.next = pending.next;
    pending.next = update;
  }
  queue.pending = update;
}
Copy the code

    • During the Fiber tree construction phase (or reconciler phase), hook.queue.pending is merged into the hook.basequeue queue (source address).

        function updateReducer<S.I.A> (reducer: (S, A) => S, initialArg: I, init? : I => S,) :S.Dispatch<A>] {
    / /... Omit part of the code
    if(pendingQueue ! = =null) {
      if(baseQueue ! = =null) {
        // Merge the queues here
        const baseFirst = baseQueue.next;
        const pendingFirst = pendingQueue.next;
        baseQueue.next = pendingFirst;
        pendingQueue.next = baseFirst;
      }
      current.baseQueue = baseQueue = pendingQueue;
      queue.pending = null; }}Copy the code

conclusion

This section mainly introduces the concept of a linked list and its use in react source code. React main data structures are related to the linked list, the use of very high frequency. Source list merge, circular list disassembly, list traversal code length is a lot, so in-depth understanding of the use of the list, to understand react principle is very beneficial.

The resources

  • The list

Write in the last

This article belongs to the diagram react principle series algorithm plate, this series of nearly 20 articles, not for the interview, really is to understand the React source code, and then improve the architecture and coding ability. You are welcome to learn React source code.