Programming basics using React source code as an example

Data structures

Linked List

Widely used in the codebase, especially for managing units of work, updates, and effects. For example, data structure Fiber itself forms a tree structure through properties child, sibling And return. Update queues for class and function components are also implemented as linked lists, allowing updates to be handled efficiently.

Why React Uses Linked Lists

(1) Efficient updating and reconciliation

The dynamic nature of user interfaces. UI updates in React often involve adding, removing, and reordering elements. Linked lists are well suited for such dynamic operations because they allow nodes to be inserted and removed efficiently without having to move elements around as in an array. This is critical to React's negotiation algorithm, which minimizes DOM manipulation for optimal performance.
Constant time insertion and deletion. Linked lists provide constant time complexity (O(1)) for insertions and deletions at the beginning or end of the list. This efficiency is useful when managing update queues and effect lists, where new updates or effects are typically added or removed from the front or tail.

(2) Memory efficiency

Reduced memory allocation. Linked lists dynamically allocate memory as needed, adding new nodes only when needed. This contrasts with arrays, which often require a fixed amount of memory to be allocated upfront, even if not all slots are in use. For large and dynamic user interfaces, linked lists can be more memory efficient.
Flexible memory usage. In React's virtual DOM, each fiber node (unit of work) is represented by a linked list structure. This flexibility allows the library to allocate and free memory for individual fiber nodes as they enter and exit the negotiation process, optimizing memory usage.

(3) Functional programming paradigm

Immutability. React supports immutability, in which data structures are not directly modified but are replaced by new versions. Linked lists are a natural fit for this paradigm because updating a list involves creating a new list with the desired changes, leaving the original list untouched.
Recursion. Linked lists are well suited for recursive algorithms, which are common in functional programming. React's consensus algorithm and several other internal processes use recursion to efficiently traverse and manipulate the tree of fiber nodes.

Stack

Used to manage context, suspend handlers, and other contextual information during the rendering and commit stages. Module ReactFiberStack.js provides features such as push, pop And createCursor for working with stacks.

Map

Used to manage various mappings, such as a record map in ReactCacheOld.jswhich links resources to corresponding records, and a map _chunks V ReactFlightClient.js to store response fragments.

Set

Used to store unique values, such as a set _updatedFibers V ReactFiberTracingMarkerComponent.jswhich tracks the units of work updated during the transition.

Heap (Min Heap)

scheduler packageused by React for task management, uses a minimal heap data structure to prioritize tasks based on their expiration time.

Trees

The virtual DOM itself is a tree structure represented by “Fiber” nodes. Besides, ReactFiberTreeContext.js manages a separate tree structure to generate unique IDs during hydration.

Algorithms

Reconciliation Algorithm

The core React algorithm responsible for efficiently updating the user interface by comparing the current and next virtual DOM trees and making minimal changes to the real DOM. This involves traversing trees, comparing nodes, and computing minimal comparison operations. Implemented in various files such as ReactChildFiber.js And ReactFiberBeginWork.js.

LRU Cache

Module LRU.js implements an LRU (Long Unused) cache to store and manage cached data. This algorithm helps optimize performance by reusing previously calculated values.

Scheduler Algorithm

The scheduler package uses a min-heap-based priority queue to schedule and prioritize tasks based on their expiration times and priority levels.

String Encoding/Decoding

Used in ReactFlightClient.js and others. modules for efficient data transfer between server and client.

Context Propagation

Algorithms for efficiently propagating context changes through a component tree, especially with the introduction of lazy context propagation.

Hydration Algorithm

Used to effectively “attach” handlers to existing HTML markup during initial rendering instead of creating the DOM from scratch.

Error Handling

Error handling and fallback algorithms Suspense, traversing the unit of work tree to find the nearest suitable error boundary.

Design Patterns

Module Pattern

The code is organized into modules, each with its own responsibilities and API. This promotes code reuse, maintainability, and separation of concerns. For example, ReactChildren.js provides functions for working with child elements, and ReactContext.js deals with creating and managing context.

Factory Pattern

createElement And cloneElement functions act as factories for creating and cloning React elements. This provides a central point for creating elements and ensures consistency in their structure.

Observer Pattern

Hook useSyncExternalStore implements an observer pattern where components subscribe to external storage and re-render it when the storage is updated. This enables efficient state management and synchronization with external data sources.

Provider Pattern

Context API implemented in ReactContext.js , uses the provider template. The context provider makes the value available to its child components, allowing data to be passed down the component tree without explicitly passing props through each level.

Decorator Pattern

Higher order components (HOC) and some hooks represent this pattern. HOC: forwardRef, memo. Hooks: useMemo, useCallback. HOCs and hooks enrich components and functions with additional behavior without changing their underlying implementation. This promotes flexibility and code reuse.

SOLID principles

Single Responsibility Principle (SRP)

Each module and function has clearly defined responsibilities. For example, ReactFiberBeginWork.js focuses on the initial phase of the approval process, and ReactFiberCompleteWork.js processes the full phase.

Open/Closed Principle (OCP)

The library is open for expansion, but closed for modification. This is evident in the use of hooks, which allow you to add new functionality without changing core React components.

Liskov Substitution Principle (LSP)

Component subtypes (for example, PureComponent And memo components) can be used wherever expected Componentensuring consistent behavior.

Interface Separation Principle (ISP)

The library provides several smaller, focused interfaces (for example, Dispatcher) and not large monolithic ones. This reduces coupling and makes it easier to use certain parts of the library without depending on unnecessary functionality.

Dependency Inversion Principle (DIP)

The library relies on abstractions (for example, ReactFiberReconciler uses HostConfig interface) instead of specific implementations, allowing different renderers to use the same basic logic.