Dúvida lista encadeada usando JS/Node

paulopimenta6
(usa Debian)

Enviado em 29/07/2022 - 13:21h

Estou novamente estudando estruturas de dados e resolvi usar como base um livro de estrutura de dados usado JavaScript. O código inicial de linkedList.js está assim:

import {defaultEquals} from '../util/util.js';
import { Node } from './models/linked-list-models.js';

export default class linkedList{
//Aqui ficara o construtor...
constructor(equalsFn = defaultEquals){
    this.count = 0;
    this.head = undefined;
    this.equalsFn = equalsFn;
}

//Aqui comecam os metodos...
push(element){
    const node = new Node(element);
    let current;        

    console.log(this.head);
    if (this.head == null){                     
        this.head = node;
        
    }
    else{            
        current = this.head;
        while(current.next != null){                
            current = current.next;
        }
        current.next = node;
    }
    this.count++;              
    }    
}

let a = new linkedList();
a.push(1);
a.push(2);
a.push(3);
a.push(4); 

E o código da classe linked-list-models.js a qual é usada pelo método push está assim:

export class Node {
constructor(element){
    this.element = element;
    this.next = undefined;
    }
} 

E o código de util.js (não usando no momento) está assim:

export function defaultEquals(a, b){
    return a === b; //exporta o valor de comparacao entre dois valores em um booleano
} 

A minha dúvida é simples, pois não consigo entender como o atributo this.head é atualizado e como ele se torna uma lista encadeada, pois somente node e current/current.next são atualizados.

Agradeço a todos desde ja!

leandropscardua
(usa Ubuntu)

Enviado em 29/07/2022 - 23:20h

Quem faz o encadeamento da lista é o campo next da classe Node. Na linha
current.next = node;
Ocorre o encadeamento. this.head é um ponteiro, só grava um endereço de memória e ele vai pulando de endereço em endereço pelo atributo next. Por isso o loop while para chegar até o final da lista, pq ela pode estar em qualquer lugar na memória. Ele vai dando pulos na memória.

paulopimenta6
(usa Debian)

Enviado em 31/07/2022 - 16:28h

Obrigado pela ajuda! Ainda fiquei com uma dúvida, é simples a dúvida, mas é a seguinte: dentro do "while" current é atualizado e fora do "while" current.next recebe node e aí atualiza o this.head. por que dentro do "while" com a atualização do current o this.head também não atualiza (Só ocorre fora do while)?

leandropscardua
(usa Ubuntu)

Enviado em 01/08/2022 - 13:06h

Esta lista adiciona itens no final dela. o item head só é atribuido quando a lista está vazia. Posteriormente quando um item vai ser inserido o loop é percorrrido até encontrar o final (current.next = null). Daí um novo endereço é atribuido para current.next e este deixa ser o final da lista.