Структура данных односвязного списка

О серии #data-structures

Серия #data-structures — это коллекция постов о перереализованных структурах данных в JavaScript.

Если вы не знакомы со структурами данных, краткое введение и полный список перереализованных структур данных можно найти в вступительной статье серии о структурах данных в JavaScript.

Если вы чувствуете себя комфортно с концепцией каждой структуры данных и хотите увидеть только код, взгляните на итоговый пост серии. Он убирает все пояснения и содержит только JavaScript-код для всех структур данных, обсуждаемый в серии.

Получить код на Github

Разумеется, весь код также можно найти на Github в репозитории data-structures-in-javascript.

Определение

Односвязный список — это линейный набор элементов данных, называемых узлами, указывающими на следующий узел с помощью указателя. Это структура данных, состоящая из группы узлов, которые вместе представляют собой последовательность. В простейшей форме каждый узел состоит из данных и ссылки (другими словами, ссылки) на следующий узел в последовательности. Из Википедии

Связанные списки являются одними из самых простых и наиболее распространенных структур данных, поскольку они позволяют эффективно вставлять или удалять элементы из любой позиции в последовательности.

Сложность

Средний:

Доступ => O (n), Поиск => O (n), Вставка => O (1), Удаление => O (1)

Чтобы получить полное представление о временной и пространственной сложности структуры данных односвязного списка, взгляните на эту прекрасную большую шпаргалку.

Код

function Node(data) {
  this.data = data;
  this.next = null;
}
function SinglyLinkedList() {
  this.head = null;
  this.tail = null;
  this.numberOfValues = 0;
}
SinglyLinkedList.prototype.add = function(data) {
  var node = new Node(data);
  if(!this.head) {
    this.head = node;
    this.tail = node;
  } else {
    this.tail.next = node;
    this.tail = node;
  }
  this.numberOfValues++;
};
SinglyLinkedList.prototype.remove = function(data) {
  var previous = this.head;
  var current = this.head;
  while(current) {
    if(current.data === data) {
      if(current === this.head) {
        this.head = this.head.next;
      }
      if(current === this.tail) {
        this.tail = previous;
      }
      previous.next = current.next;
      this.numberOfValues — ;
    } else {
      previous = current;
    }
    current = current.next;
  }
};
SinglyLinkedList.prototype.insertAfter = function(data, toNodeData) {
  var current = this.head;
  while(current) {
    if(current.data === toNodeData) {
      var node = new Node(data);
        if(current === this.tail) {
          this.tail.next = node;
          this.tail = node;
        } else {
          node.next = current.next;
          current.next = node;
        }
      this.numberOfValues++;
    }
    current = current.next;
  }
};
SinglyLinkedList.prototype.traverse = function(fn) {
  var current = this.head;
  while(current) {
    if(fn) {
      fn(current);
    }
    current = current.next;
  }
};
SinglyLinkedList.prototype.length = function() {
  return this.numberOfValues;
};
SinglyLinkedList.prototype.print = function() {
  var string = ‘’;
  var current = this.head;
  while(current) {
    string += current.data + ‘ ‘;
    current = current.next;
  }
  console.log(string.trim());
};
var singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.print(); // => ‘’
singlyLinkedList.add(1);
singlyLinkedList.add(2);
singlyLinkedList.add(3);
singlyLinkedList.add(4);
singlyLinkedList.print(); // => 1 2 3 4
console.log(‘length is 4:’, singlyLinkedList.length()); // => 4
singlyLinkedList.remove(3); // remove value
singlyLinkedList.print(); // => 1 2 4
singlyLinkedList.remove(9); // remove non existing value
singlyLinkedList.print(); // => 1 2 4
singlyLinkedList.remove(1); // remove head
singlyLinkedList.print(); // => 2 4
singlyLinkedList.remove(4); // remove tail
singlyLinkedList.print(); // => 2
console.log(‘length is 1:’, singlyLinkedList.length()); // => 1
singlyLinkedList.add(6);
singlyLinkedList.print(); // => 2 6
singlyLinkedList.insertAfter(3, 2);
singlyLinkedList.print(); // => 2 3 6
singlyLinkedList.insertAfter(4, 3);
singlyLinkedList.print(); // => 2 3 4 6
singlyLinkedList.insertAfter(5, 9); // insertAfter a non existing node
singlyLinkedList.print(); // => 2 3 4 6
singlyLinkedList.insertAfter(5, 4);
singlyLinkedList.insertAfter(7, 6); // insertAfter the tail
singlyLinkedList.print(); // => 2 3 4 5 6 7
singlyLinkedList.add(8); // add node with normal method
singlyLinkedList.print(); // => 2 3 4 5 6 7 8
console.log(‘length is 7:’, singlyLinkedList.length()); // => 7
singlyLinkedList.traverse(function(node) { node.data = node.data + 10; });
singlyLinkedList.print(); // => 12 13 14 15 16 17 18
singlyLinkedList.traverse(function(node) { console.log(node.data); }); // => 12 13 14 15 16 17 18
console.log(‘length is 7:’, singlyLinkedList.length()); // => 7

Первоначально опубликовано на blog.benoitvallon.com.