Двусвязный список: круговая структура - PullRequest
Новая
       36

Двусвязный список: круговая структура

0 голосов
/ 13 декабря 2018

Я реализую двусвязный список в Javascript: 

    const LinkedList = function() {
        this.head = null;
        this.tail = null;
    };
    
    const Node = function(value, next, prev) {
        this.value = value;
        this.next = next;
        this.prev = prev;
    };
    
    LinkedList.prototype.addToHead = function(value) {
        const newNode = new Node(value, this.head, null);
        if (this.head) {
            this.head.prev = newNode;
        } else {
            this.tail = newNode;
        }
        this.head = newNode;
    };
    
    const list = new LinkedList();
    list.addToHead(100);
    list.addToHead(200);
    list.addToHead(300);
    console.log(list);

Каждый узел имеет значения next и prev, содержащие предыдущий и следующий объекты.Поскольку объекты копируются по ссылке в Javascript, мы не копируем весь объект, а указываем на него.

Но когда я создаю экземпляр LinkedList и записываю его в журнал, я получаю круговую структуру, где каждый узел показывает свойnext узел внутри node.next;этот node.next будет иметь значение prev, показывая первый узел.И это круговая структура ... Например, если вы попытаетесь структурировать этот список, вы получите TypeError: Converting circular structure to JSON: 

const LinkedList = function() {
            this.head = null;
            this.tail = null;
        };
        
        const Node = function(value, next, prev) {
            this.value = value;
            this.next = next;
            this.prev = prev;
        };
        
        LinkedList.prototype.addToHead = function(value) {
            const newNode = new Node(value, this.head, null);
            if (this.head) {
                this.head.prev = newNode;
            } else {
                this.tail = newNode;
            }
            this.head = newNode;
        };
        
        const list = new LinkedList();
        list.addToHead(100);
        list.addToHead(200);
        list.addToHead(300);
        console.log(JSON.stringify(list));

Является ли это ожидаемым поведением двусвязного списка?Есть ли проблемы с памятью?

...