т. (383) 381-86-26

Блог о создании вебсайтов

 

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

 

На днях для небольшого функционала на клиентской стороне потребовалось запоминать порядок шествия элементов и производить с ними разные манипуляции. Для этой цели сгодился двунаправленный список. Несмотря на большое количество реализаций этой структуры данных, очень не хотелось использовать какую-либо большую библиотеку, так как функционал этого не оправдывал. Поэтому я накидал самостоятельный набросок двунаправленного связного списка на javascript.

Как ты наверняка знаешь, базовая идея этой структуры данных заключается в том, что каждый элемент списка знает не только кто идёт после него, но и кто был до него: Благодаря этому мы можем двигаться по списку в любом направлении, и нам легче производить модифицирование списка и поиск нужных элементов (ну, да тебе это наверняка известно, это же первый курс любого профильного вуза ^__~)

Код ниже — небольшой набросок базовой структуры двусвязного списка. Работает. Наверняка не оптимален и требует полировки. Но работает =)

function DoubleLinkedList() {
    this.length = 0;
    this.head = null;
}
 
DoubleLinkedList.prototype = {
    add: function(value) {
        var node = {
            value: value,
            next: null,
            prev: null,
        }
         
        if (this.length == 0) {
            this.head = node;
        }
        else {
            this.head.next = node;
            node.prev = this.head;
            this.head = node;
        }
        this.length++;
    },
     
    getByValue: function(value) {
        var node = this.head;
        var i = 0;

        while (i++ < this.length) {
            if (node.value === value){
                return node;
            }
            node = node.prev;
        }
         
        return null;
    },
     
    displayNode: function(node) {
        if (node != null) {
            console.log('value = ' + node.value);
            console.log('prev = ' + (node.prev != null ? node.prev.value : 'null'));
            console.log('next = ' + (node.next != null ? node.next.value : 'null'));
            console.log('--------------');
            return;
        }
    },
     
    removeByValue: function(value) {
         
        var node = this.getByValue(value);
        var i = 0;

        if (node.value === value){
            if (node.prev !== null && node.next !== null){
                node.next.prev = node.prev;
                node.prev.next = node.next;
                delete node;
            }
            else if (node.prev === null && node.next !== null) 
            {
                node.next.prev = null;
                delete node;
            }
            else if (node.next === null && node.prev !== null) { 
                node.prev.next = null;
                this.head = node.prev;
                node.prev = null;
                delete node;
            }
            else{
                this.head = null;
            }
        }
        this.length--;
        return;
    },



};

Подпишитесь на рассылку, будет интересно!