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

Связанный список — это линейная структура данных с элементами (узлами) со ссылками, указывающими на другие элементы списка.
Существует три типа связанных списков:

• Односвязный список — узлы имеют один указатель на следующий элемент в списке. Последний узел указывает на ноль.
• Двусвязные списки — каждый узел имеет два указателя, один из которых указывает на предыдущий элемент списка, а другой — на следующий элемент.
• Циклический связный список — последний узел указывает на первый элемент в списке.

В этой статье мы рассмотрим односвязный список.

Элемент в односвязном списке состоит из двух основных частей. Первая часть
содержит значение данных, а другая часть содержит ссылку на следующий элемент. Однако последнему элементу не на что указывать, поэтому его следующее значение равно null.

Зачем и когда использовать связные списки

Связные списки рекомендуется использовать, если у вас есть список объектов со ссылками на следующий элемент в списке. Их основное преимущество заключается в следующем;

• Простая вставка

Вставка элемента в массив является довольно дорогостоящей, поскольку вам придется сдвигать все остальные элементы. Аналогично, при удалении элемента в массиве останутся дыры или придется сдвигать позиции элементов после удаленного элемента.

Однако при использовании связанного списка вы можете легко просмотреть список и вставить или удалить узел в нужной позиции.

Недостатки связанных списков

1. Не поддерживается случайный доступ к элементам. Таким образом, вам придется просматривать список последовательно, начиная с первого элемента. Это может занять много времени, особенно в худшем случае.## Как создать связный список

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

 class Node {
  constructor(val, next = null) {
    this.data = val;
    this.next = next;
  }
}

Далее давайте инициализируем связанный список.
Обратите внимание, что head будет иметь нулевое значение и нулевой размер, так как мы еще не добавили ни одного элемента.

 class Node {
  constructor(val, next = null) {
    this.data = val;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  //methods
}

1. Вставка узла в первую позицию (голова)

Чтобы вставить узел в первую позицию, мы воспользуемся конструктором Node.

Мы создадим новый узел со свойством data вставляемого значения и свойством next предыдущего head.

  insertFirst(data) {
    this.head = new Node(data, this.head);
    this.size++
  }

2. Вставка узла в последнюю позицию (хвост)

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

Мы присвоим новому узлу следующее значение за последним узлом.

Не забудьте проверить, пуста ли голова. Если да, то новый узел будет головой.

  insertLast(data) {
    let node = new Node(data);
    let current;

    //if empty make the node the head
    if (!this.head) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next) { // the loop terminates when  the pointer gets to a node whose next property is null
        current = current.next;
      }
      current.next = node;
    }
    this.size++
  }

3. Вставка узла в индекс

Первое, что нужно сделать при работе с индексом, — это проверить, является ли индекс допустимым. То есть не меньше нуля и не больше размера списка.

Если индекс равен нулю, то узел становится головным.

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

Когда цикл завершится, свойство next предыдущего элемента будет указывать на добавляемый узел previous.next = node, а следующий элемент нового узла будет указывать на текущий элемент, node.next = current.

   insertatIndex(data, index) {
    if (index < 0 || index > this.size) { // Checking if the index is valid. That is, less than zero or greater than the size 

      return;
    }
    //inserting at the first position. You can reuse the insertFirst()
    if(index == 0){
      this.head = new Node(data, this.head) //making the new node the head and the next value, the previous head
        console.log( this.head)
        return;
    }
    const node = new Node(data); // creating the node using the Node class
    let current, previous; // 

    //set current to first
    current= this.head;
    let pos = 0;
    //looping through untill you get to the index 
    while(pos < index){
        previous = current;
        pos++;
        current = current.next;

    }
    node.next = current;
    previous.next = node;
    this.size++
  }

4. Получить узел по индексу

Чтобы получить элемент по определенному индексу в связанном списке, пройдитесь циклом по списку, проверяя, равна ли текущая позиция индексу.

Если значение позиции равно индексу, выведите его значение данных.

В противном случае увеличьте позицию и переместите указатель на следующий элемент.

 getAt(index){
    let current = this.head;
    let pos=0;
    while(current){ // the loop terminates if the currenmt value (this.head) is null
        if(pos == index){
            console.log(current.data)
        }
        pos++;
        current= current.next; // moving the pointer to the next value

    }
    return null;
  }

5. Удаление узла по индексу

Сначала проверьте, действителен ли индекс. То есть, он не меньше нуля или больше размера, если вы знаете размер.

Если head равен нулю, то необходимо удалить первое значение, переместив указатель head на head.next.

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

Чтобы удалить узел, свойство next у previous должно указывать на следующий элемент после удаляемого. То есть previous.next = current.next.

 removeAtIndex(index){
    if (index < 0 || index > this.size){ //checking if the index is valid
      return
    }
    let count=0;
    let previous, current;
    current = this.head;
    if (index === 0) { // Deleting from beginning 
      this.head = current.next;
    }else{
    while(count < index){
      previous = current;
      current = current.next; 
      count++     
    }
    previous.next = current.next;
    this.size--;
    return;
  }
}

6. Очистить список

Пустой связный список имеет головное значение null. Следовательно, чтобы очистить список, нужно указать головное значение на null.

 clearList(){
    this.head = null;
    this.size = 0;
  }

7. Пересечение связного списка

Мы переходим по связанному списку, используя указатель head. Помните, что указатель head ссылается на первый узел.

В цикле while мы проверим, что head не равен null. То есть, список не пуст или мы не исчерпали цикл по списку и выведем head.data (помните, что узел — это объект), а затем переместим указатель на следующее значение.

printList() {
    while (this.head) {
      console.log(this.head.data);
      this.head = this.head.next;
    }
  }

Анализ Big O

Заключение

Лучший способ понять структуры данных — это практика. После понимания основ попробуйте написать фрагменты кода или найдите задачи по leetcode и решите их.