Списки

Списки как массивы

JavaScript
Массивы
Списки являются ключевой структурой организации данных в задачах искусственного интеллекта. В принципе, массивы JavaScript предоставляют все необходимые функции по работе со списками. Пустой список объявляется так: var lst = [];. Затем элемент it можно добавить в конец: lst.push(it) или начало: lst.unshift(it) списка. Функцией it=lst.pop() элемент выталкивается из конца списка, а it=lst.shift() - из начала. Слова shift и unshift как раз связаны с терминологией обыденных очередей. Когда кто-то залазит в очередь спереди, она вынуждена сдвинуться назад (unshift). При выходе первого человека из очереди - она естественным образом сдвигается вперёд (shift).

Удалить count элементов, начиная с i-того можно вызовом lst.splice(i, count). Эта же функция при вызове lst.splice(i, 0, it) вставляет элемент it на место индекса i (после lst[i-1]). Функция lst.reverse() обращает последовательность элементов списка. Ниже, справа от кода скрипта приведен результат вызова document.write(res); и тег <br> в html означает переход к следующей строке:

var lst = [],  n,   res = 'length = '+lst.length+"<br>";
lst.push(0);        res +=  lst + '<br>';
lst.push(1);        res +=  lst + '<br>';
lst.push(2);        res +=  lst + '<br>';
lst.unshift(-1);    res +=  lst + '<br>';
lst.unshift(-2);    res +=  lst + '<br><br>';
 
n = lst.pop();      res +=  lst + '  n='+n+'<br>';
n = lst.shift();    res +=  lst + '  n='+n+'<br>';
lst.splice(1,1);    res +=  lst + '<br>';
lst.splice(1,0,2);  res +=  lst + '<br>';
lst.reverse();      res +=  lst ;
length = 0
0
0,1
0,1,2
-1,0,1,2
-2,-1,0,1,2

-2,-1,0,1  n=2
-1,0,1  n=-2
-1,1
-1,2,1
1,2,-1
Однако, в ряде случаев, массив - не лучший выбор. В частности, при поиске в ширину необходимо часто добавлять элементы в начало списка. Эта операция для массива очень медленная, т.к. ему необходимо не только выделять дополнительную память, но и сдвигать все элементы массива вправо. Для таких случаев стоит использовать традиционные списки связанных между собой узлов ( = элементов) списка.

Класс List

Перейдём теперь к созданию класса List, который будет оперировать со списками. Зададим список при помощи набора структур вида { nm, prv, nxt }, где nm - имя узла (может хранить любые данные), prv - указатель на предыдущий и nxt - на следующий узел. Если узлы не имеют указателя prv - то это односторонний (правосторонний) список List, иначе список двухсторонний и он реализован классом List2. Односторонний список чуть быстрее двухстороннего, однако, он заметно медленнее при удалении из конца (pop). Если используется эта функция, необходим List2.

Класс списка так же хранит указатели на первый - beg и последний - end его узел. Существует несколько способов интерпретации этих указателей. Мы подробнее рассмотрим более быстрый вариант, когда beg и end - это фиктивные узлы, а реальные находятся между ними.

Определим функцию, которая будет конструктором класса List:

function List(nm)
{
   this.end = { nm:null, nxt:null };              // фиктивный последний элемент списка
   this.beg = { nm:null, nxt:this.end };          // фиктивный первый элементы списка
 
   this.length =  0;                              // число узлов в списке (пустой)
 
   if(nm !== undefined)                           // если есть аргумент nm
      this.push(nm);                              // сразу вставляем первый элемент
}
Функция List будет вызвана при объявлении объекта (экземпляра класса List) при помощи оператора new когда мы напишем: var lst = new List(); Теперь объект lst будет хранить данные списка, доступ к которым производится через точку: (lst.length и т.д.). Такие данные будет помнить каждый экземпляр класса (и у каждого они будут иметь свои значения). Выше подобным образом объявлены 3 переменные-свойства класса (end, beg и length).

В конструкторе класса List введен фиктивный указатель end, следующий за последним элементом списка. Фиктивный указатель beg через свойство beg.nxt ссылается на первый элемент списка. Так как список пока пустой, beg.nxt ссылается на end. Функцию (метод класса) push мы определим ниже.

Отметим, что поля nm и nxt инициализированы нулевым указателем null (напомним, что между undefined и null существует заметная разница). Фиктивный указатель end, при вставке в конец списка, будет превращаться в реальный последний узел. Поэтому, таким объявлением, мы предлагаем движку JavaScript сразу выделить память под объект с соответствующими полями, чтобы не пересоздавать его потом (при вставке). Это ускоряет работу с объектами (иногда в разы).

Методы класса

Кроме хранения данных, список должен выполнять определённые действия (иметь методы). Напишем, например, функцию, которая выводит список как строку в круглых скобках:

List.prototype.toString = function ()
{
   var n = this.beg.nxt;                          // сразу за beg стоит первый узел
   var st = "(";
   while(n !== this.end){                         // пока нет  фиктивного последнего
      st += n.nm + (n.nxt!== this.end ? "," : "");// выводим через запятую имена узлов
      n = n.nxt;                                  // переходим к следующему узлу
   }
   return st+")";
}
Конструкция (условие? значение_если_истина : значение_если_ложь), являющаяся компактной записью условного оператора if, служит для "ликвидации" запятой после последнего узла в списке.

Функция с именем toString может быть в любом классе. Если она определена, то экземпляр класса, когда этого требует соответствующий контекст, преобразуется в строку. Например, следующий скрипт:

var lst = new List();
document.write(lst);
так как список пока пустой, выведет строку: . Функция toString есть и у массивов, поэтому их элементы можно выводить аналогичным образом.

Вставка элементов

Напишем теперь функцию, вставляющую элемент с именем nm в начало списка:

List.prototype.unshift = function (nm)
{
   this.length++;                                 // увеличиваем число узлов
 
   this.beg.nxt = {nm: nm, nxt:this.beg.nxt};     // вставляемый элемент следует за beg
}
Так как мы хотим, чтобы список был похож на массив, при добавлении увеличивается переменная length (число элементов в списке). Затем (читая справа-налево) создаётся новый элемент-узел, который по указателю nxt ссылается на прежний первый элемент списка beg.nxt, а фиктивный узел beg по beg.nxt начинает ссылается на вновь добавленный узел. Аналогично выглядит функция, вставляющая элемент в конец списка:
List.prototype.push = function (nm)
{
   this.length++;                                 // увеличиваем число узлов
 
   this.end.nm = nm;                              // фиктивный end становится реальным
   this.end = this.end.nxt = { nm:null, nxt:null};// и затем снова фиктивным
}
Последнюю строку также необходимо читать справа-налево: сначала создаётся новый фиктивный последний узел, на который по указателю end.nxt ссылается реальный последний узел (которым становится "старый" фиктивный). Затем указатель на новый фиктивный сохраняется в this.end.

Графически, последовательная вставка 0, 1, 2 в начало и конец списка выглядит следующим образом: (первые картинки в каждой строке изображают пустые списки):


Удаление элементов

Обсудим алгоритмы удаления элементов из списка. Удаление в правосторонних списках (есть только ссылки nxt) из начала не представляет труда:

List.prototype.shift = function ()
{
   if(this.length===0)
      return;                                     // список пуст - вернём undefined
 
   this.length--;                                 // уменьшаем число узлов
 
   this.beg  = this.beg.nxt;                      // фиктивный beg ссылается на второй элемент
   return this.beg.nm;
}
Отметим одну тонкость. Возвращаемый функцией указатель на имя первого узла nm остаётся в фиктивном узле nm, даже, если вызывающей функцию shift программе он уже не нужен. При необходимости (если данные, хранимые в списке занимают много памяти) его можно освободить, написав lst.beg.nm=null.

Удаление из конца одностороннего списка, существенно более затратная операция, так как необходимо получить последний элемент (реальный) о котором указатель end ничего не знает:

List.prototype.pop = function ()
{
   if(this.length === 0)
      return;                                     // список пуст - вернём undefined
 
   this.length--;                                 // уменьшаем число узлов
 
   var n = this.beg.nxt;                          // начиная с первого реального узла,
   while(n.nxt !== this.end)                      // ищем реальный последний узел
      n = n.nxt;                                  // переходя каждый раз к следующему
 
   this.end = n;                                  // фиктивный сдвигаем влево на один
   return n.nm;
}
При частом выполнении этой операции, лучше использовать класс двунаправленного списка List2, в котором фиктивный финальный узел end (как и остальные узлы) хранит указатель на предыдущий элемент end.prv.

Ещё немного функций

Приведём несколько функций класса List, эффективность которых не столь высока, по сравнению с вставкой в начало или конец списка. Так, получение узла под номером pos (начиная с нуля) выглядит следующим образом:

List.prototype.node = function (pos)
{
   var n = this.beg.nxt;                         // бежим от начала
   while(n !== this.end && pos-- > 0)
      n = n.nxt;                                 // переходим к следующему узлу
   return n;
}
JavaScript
i-- vs. --i
Декриментирование справа (уменьшение значения на единицу): pos--, тоже, что pos = pos - 1. Однако, оно производится после участия переменной в выражении. Поэтому в цикле while сначала проводится сравнение (pos > 0), а только после этого уменьшается значение pos. Иначе ситуация обстоит с декриментированием слева: --pos < 0. В этом случае, сначала бы произошло уменьшение переменной, а лишь затем её сравнение с нулём.

Ещё одна функция добавляет узел с именем nm на место pos в списке (начиная с нуля), сдвигая всё вправо:

List.prototype.insert = function (pos, nm)
{
   if(pos <= 0)                                   // добавляем в начало
      return this.unshift(nm);
   if(pos >= this.length)                         // добавляем в конец
      return this.push(nm);
 
   this.length++;                                 // увеличиваем число узлов
   var n = this.node(pos-1);                      // перед вставляемым узлом
   n.nxt = { nm:nm, nxt:n.nxt};
}

Аналогична функция удаления узла на месте pos в списке (начиная с нуля) и возвращения его поля nm:

List.prototype.remove = function (pos)
{
   if(pos <= 0)                                   // удаляем из начала
      return this.shift();
   if(pos+1 >= this.length)                       // удаляем из конца
      return this.pop();
 
   this.length--;                                 // уменьшаем число узлов
   var n = this.node(pos-1);                      // перед удаляемым узлом
   var nm = n.nxt.nm;
   n.nxt = n.nxt.nxt;
   return nm;
}

Упорядоченная вставка

Добавим ещё функцию, которая вставляет элемент в начало списка, но при этом следит за упорядоченностью элементов:

List.prototype.add = function (nm)
{
   var n = this.beg;                             // бежим от начала
   while(n !== this.end && n.nxt.nm !==null && this.lt(n.nxt.nm,  nm) )
      n = n.nxt;
 
   this.length++;                                 // увеличиваем число узлов
   n.nxt = {nm: nm, nxt:n.nxt};                   // вставляемый элемент следует за n
}
Предполагается, что в общем случае имя узла nm не является числом или строкой, поэтому в цикле используется функция сравнения lt(a, b), которая должна возвращать true, если a < b, иначе (больше или равны) - false. Она задаётся извне (хотя по умолчанию она определена так, как в закомментированной строке):
lst = new List();
var arr = [1, 0, 5, 3, 0, 5, 8, 2];
 
//lst.lt = function(a, b){ return a < b; }
 
for(var i=0; i < arr.length; i++ ){
   lst.add(arr[i]);
   document.write(arr[i],' → ' ,lst, '<br>');
}
В дальнейшем мы рассмотрим более эффективные способы хранения упорядоченных данных.

Нефиктивные указатели

Рассмотрим кратко ещё один способ работы со списком, когда указатели beg и end реально ссылаются на первый и последний элементы списка (напрямую, а не через поле nxt). Оформим его в виде класса List1

function List1(nm)
{
   this.beg = null;             // указатель на первый    элемент списка (пока в никуда)
   this.end = null;             // указатель на последний элемент списка (пока в никуда)
 
   this.length =  0;            // число узлов в списке
 
   if(nm !== undefined)         // если есть аргумент nm
      this.push(nm);            // сразу вставляем первый элемент с именем nm фу-ей push
 }
Для удобства рядом с функциями-методами этого класса повторим аналогичные функции класса List. Добавление в начало списка имеет вид:
List1.prototype.unshift = function (nm)
{
   if(this.length===0){
      this.beg = this.end = { nm: nm };
      this.length= 1;
      return;
   }
   this.length++;
   this.beg = {nm: nm, nxt:this.beg};
}
List.prototype.unshift = function (nm)
{
   this.length++;
   this.beg.nxt = {nm: nm, nxt:this.beg.nxt};
}
Добавление в конец очереди:
List1.prototype.push = function (nm)
{
   if(this.length===0){
      this.beg = this.end = { nm: nm };
      this.length= 1;
      return;
   }
   this.length++;
   this.end = this.end.nxt = {nm: nm};
}
List.prototype.push = function (nm)
{
   this.length++;
   this.end.nm = nm;
   this.end = this.end.nxt = {  };
}
Как мы увидим ниже, списки List1 по быстродействию заметно седленнее списков из класса List. К тому-же, функции вставки в классе List не требуют проверки того, что список пуст, поэтому выглядят более изящными.

Двухсторонние списки

Элементы (узлы) двухcторонних списков хранят в себе указатели, как на следующий элемент (nxt), так и на предыдущий (prv):

Они реализованы классом List2, конструктор которого выглядит так:
function List2(nm)
{
   this.end = {  };             // указатель на фиктивный последний элемент списка
   this.beg = { nxt:this.end }; // указатель на фиктивный первый элементы списка
   this.end.prv = this.beg;
 
   this.length = 0;             // число узлов в списке
 
   if(nm !== undefined)
      this.push(nm);
}
Функции добавления в начало и конец реализованы следующим образом:
List2.prototype.unshift = function (nm)
{
   this.length++;
   this.beg.nxt = {nm: nm, prv:this.beg,
                           nxt:this.beg.nxt};
}
List2.prototype.push = function (nm)
{
   this.length++;
   this.end.nm = nm;
   this.end = this.end.nxt = { prv:this.end };
}
Приведём также функции удаления из конца и начала:
List2.prototype.pop = function ()
{
   if(this.length===0)
      return;
   this.length--;
 
   this.end = this.end.prv;
   return this.end.nm;
}
List2.prototype.shift = function ()
{
   if(this.length===0)
      return;
   this.length--;
 
   this.beg = this.beg.nxt;
   return this.beg.nm;
}

Тестирование быстродействия

Ниже тестируется вставка в начало и конец списка, реализованного массивом (медленный unshift) и правосторонними (List, List1) и двухсторонним списком (List2). Как организовать процесс тестирования описано в документе Speed.

добавлений раз: (ms) ( цикл: )
push unshift
Array 13 9088   Обычный массив JavaScript
List 25 15   Односторонний список List
List2 30 25   Двухсторонний список List2
List0 47 34   Односторонний список List без инициализаций null
List1 49 33   Односторонний список List с "нефиктивными" beg и end

Ещё один тест связан с последовательной вставкой всех элементов в конец, а затем их удалением из конца и начала списка:

добавлений раз: (ms) ( цикл: )
push,pop push,shift
Array 19 147   Обычный массив JavaScript
List 10693 13   Односторонний список List
List2 22 30   Двухсторонний список List2

Общий вывод такой: для операций push, unshift и shift, которые активно используются в алгоритмах поиска в ширину или глубину, стоит использовать класс List. Однако, если необходимо часто удалять элементы из конца списка pop, то List лучше не использовать.

Работа со списками

Подытожим. Методы работы со списками полностью аналогичны методам работы с массивами:

var res = "";
var lst = new List2();
for(var i=0; i < 7; i++)
   lst.push(i);
res += 'число узлов:'+ lst.length+ '<br>' + lst+'<br>';
lst.reverse();
res +=  lst+'<br>';
res += lst.pop()+ ': ' + lst+'<br>';
res += lst.node(2).nm + '<br>';
lst.put(2,"a");      res += lst+'<br>';
res += lst.get(0)+'<br>';
lst.insert(0,"b");   res += lst+'<br>';
res += lst.remove(0) + ": " + lst+'<br>';
res += lst.remove(2) + ": " + lst+'<br>';
lst.reverse();
res += lst+'<br><br>'
res += ListShow(lst);
return res;

Чтобы классы List (односторонний список) и List2 (двухсторонний список) стали доступными, необходимо подключить модуль list.js. Приведём в справочных целях все методы этих классов:

Метод грубой силы <
> Бинарные деревья