[JS] - [array, Stack, queue, Link List basis] - Notes

Déclaration：Cette note est basée sur un petit livre de Nuggets,Pour en savoir plus,Avancez, s'il vous plaît.https://juejin.cn/book/6844733800300150797

1 Tableau

1.1 Création unidimensionnelle

const arr = []
const arr = new Array()

Spécifier la longueur

const arr = new Array(7)

Créer une détermination de longueur、Un tableau dans lequel la valeur de chaque élément est également déterminée

const arr = (new Array(7)).fill(1)

1.2 Traversée unidimensionnelle

1. for Cycle

// Obtenir la longueur du tableau
const len = arr.length
for(let i=0;i<len;i++) {
    
    //  Valeurs des éléments du tableau de sortie , Exporter l'index courant 
    console.log(arr[i], i)
}

2. forEach Méthodes

arr.forEach((item, index)=> {
    
    //  Valeurs des éléments du tableau de sortie , Exporter l'index courant 
    console.log(item, index)
})

3. map Méthodes

Sur une base ergodique “Retraitement”

const newArr = arr.map((item, index)=> {
    
    //  Valeurs des éléments du tableau de sortie , Exporter l'index courant 
    console.log(item, index)
    //  Ajouter à la valeur actuelle de l'élément 1
    return item+1
})

map Pour retourner un nouveau tableau , La valeur de chaque élément du tableau est basée sur sa valeur d'élément existante +1Après les résultats

1.3 Tableau bidimensionnel

Initialisation d'un tableau 2D

const len = arr.length
for(let i=0;i<len;i++) {
    
    //  Initialiser chaque emplacement de puits du tableau dans le tableau 
    arr[i] = []
}

1.4 Traversée du tableau 2D

#  Longueur du tableau externe du cache 
const outerLen = arr.length
for(let i=0;i<outerLen;i++) {
    
    #   Longueur du tableau interne du cache 
    const innerLen = arr[i].length
    for(let j=0;j<innerLen;j++) {
    
       # Valeur du tableau de sortie, Index du tableau de sortie `const arr = [1,2]
arr.push(3) // [1,2,3]`
        console.log(arr[i][j],i,j)
    }
}

2 Méthodes d'ajout et de suppression de tableaux

2.1 Ajouter un élément au tableau

1. unshift Méthodes-Ajouter un élément à l'en - tête du tableau

const arr = [1,2]
arr.unshift(0) # [0,1,2]

2. push Méthodes- Ajouter des éléments à la fin du tableau

const arr = [1,2]
arr.push(3) # [1,2,3]

3. splice Méthodes- Ajouter des éléments n'importe où dans le tableau

const arr = [1,2] 
arr.splice(1,0,3) # [1,3,2]

 Le premier paramètre entrant est la valeur de l'index de départ , Le deuxième paramètre d'entrée indique le nombre d'éléments à supprimer à partir de l'index de départ , Le troisième paramètre est la valeur entrante 

2.2 Supprimer un élément du tableau

1. shift Méthodes- Supprimer les éléments de l'en - tête du tableau

const arr = [1,2,3]
arr.shift() # [2,3]

2. pop Méthodes-Supprimer les éléments à la fin du tableau

const arr = [1,2,3]
arr.pop() # [1,2]

3. splice Méthodes- Supprimer les éléments n'importe où dans le tableau

const arr = [1,2,3]
arr.splice(1,1) # [1, 3]

3 Pile、File d'attente

L'implémentation de la pile et de la file d'attente dépend généralement du tableau
La différence entre les deux est que, Ils ont chacun une relation Ajouter / supprimer Les opérations ont des limites différentes .

3.1 Pile

Seuls les éléments de queue sont autorisés
Seuls les éléments retirés de la queue sont autorisés

// État initial,Pile vide
const stack = []  
// Processus de pile
stack.push(' Plaque nord - Est ')
stack.push('Coredo.')
stack.push('Chow Roz')
stack.push('Ice Factory')
stack.push(' Brique de lait brillant ')

// Processus de sortie de pile, Exécuter lorsque la pile n'est pas vide 
while(stack.length) {
    
    //  Accès simple à l'élément supérieur de la pile （Ne sort pas de la pile）
    const top = stack[stack.length-1]
    console.log(' Maintenant, la crème glacée est ', top)  
    // Éloignez l'élément supérieur de la pile de la pile
    stack.pop()
}

// Pile vide
stack // []

3.2File d'attente

Seulement push Et shift Ajouter ou supprimer “Tableau”

const queue = []  
queue.push(' Petite sœur aînée ')
queue.push(' Deuxième sœur aînée ')
queue.push(' Petite sœur aînée ')  
  
while(queue.length) {
    
    //  Élément d'en - tête d'équipe d'accès simple （Pas hors de l'équipe.）
    const top = queue[0]
    console.log(top,'Prenez vos repas.')
    // Éloignez le chef d'équipe de l'équipe.
    queue.shift()
}

// L'équipe est vide.
queue // []

4 Liste des liens

Dans la liste, Le nom de l'unit é de données est appelé “Noeud”, Et la distribution des noeuds , Peut être discret en mémoire .
Pour accéder à n'importe quel élément de la liste liée , Nous devons tous commencer par le noeud de départ ,Visite individuelle next, Jusqu'au noeud cible . Pour s'assurer que le noeud de départ est accessible , Parfois, on met en place un head Pointeur vers la position de départ de la liste ：

1. Créer des noeuds de liste liés,Un constructeur est nécessaire：

function ListNode(val) {
    
    this.val = val;
    this.next = null;
}

2. Créer un noeud en utilisant un constructeur

const node = new ListNode(1)  
node.next = new ListNode(2)

La valeur du champ de données est 1,next La valeur du champ de données du noeud est 2

3. Insérer un nouveau noeud entre deux noeuds

Ce que nous devons changer Noeud avantEtNoeud cibleDe next Le pointeur pointe vers

#  Si le noeud cible n'existait pas , N'oubliez pas de créer manuellement 
const node3 = new ListNode(3)     

# Prends ça.node3De next Le pointeur pointe vers node2（C'est - à - dire: node1.next）
node3.next = node1.next

# Prends ça.node1De next Le pointeur pointe vers node3
node1.next = node3

4. Suppression d'éléments de liste liés

Pour que son noeud précurseur node1 De next Le pointeur l'a sauté. 、Pointage node3 Suivi de

node1.next = node3.next 

Vous pouvez utiliser un seul pointeur , Ce pointeur est utilisé pour localiser le noeud avant du noeud cible .

// Utilisation node1 Peut être localisé à node3
const target = node1.next  
node1.next = target.next

Par rapport au tableau , La liste a un avantage évident , C'est - à - dire que ni l'ajout ni la suppression d'éléments n'ont besoin de déplacer des éléments supplémentaires

Dans la liste des liens, Dès qu'il est clair que vous voulez insérer / Emplacement cible supprimé , La complexité des opérations d'ajout et de suppression est constante ,Exprimé en O(1).

MaisListe des liensIl y a un inconvénient.： Quand on essaie de lire quelque chose （Noi- Oui.） Lorsque le noeud de la liste de liens , Vous devez parcourir toute la liste pour la trouver ,Exprimé en O(n).
Mais dansTableauMoyenne, Nous accédons directement à l'index 、 Peut faire un pas en avant , La complexité de cette opération est réduite à un niveau constant O(1)

Insertion d'une liste liée/Suppression plus efficace, Et l'efficacité d'accès est faible ; Accès plus efficace au tableau , Faible efficacité d'insertion