Статьи

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

Февраль 12, 2019
Конечный продукт
Что вы будете создавать

Двумя наиболее часто изучаемыми структурами данных в информатике являются односвязный список и двусвязный список.

Когда меня учили этим структурам данных, я попросил своих коллег по аналогиям для их концептуализации. Я услышал несколько примеров, например, список продуктов и поезд. Эти аналогии, как я в конце концов узнал, были неточными. Список покупок был больше похож на очередь; поезд был больше похож на массив.

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

Односвязный список

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

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

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

Операции односвязного списка

Поскольку односвязный список содержит узлы, которые могут быть отдельным конструктором от односвязного списка, мы обрисовываем в общих чертах операции обоих конструкторов: Node и SinglyList .

Узел

  • data хранят значение.
  • next указывает на следующий узел в списке.

SinglyList

  • _length возвращает количество узлов в списке.
  • head назначает узел в качестве заголовка списка.
  • add(value) добавляет узел в список.
  • searchNodeAt(position) ищет узел в n-позиции в нашем списке.
  • remove(position) удаляет узел из списка.

Реализация односвязного списка

Для нашей реализации мы сначала определим конструктор с именем Node а затем конструктор с именем SinglyList .

Каждому экземпляру Node требуется возможность хранить данные и указывать на другой узел. Чтобы добавить эту функциональность, мы создадим два свойства: data и next , соответственно.

1
2
3
4
function Node(data) {
    this.data = data;
    this.next = null;
}

Далее нам нужно определить SinglyList :

1
2
3
4
function SinglyList() {
    this._length = 0;
    this.head = null;
}

Каждый экземпляр SinglyList будет иметь два свойства: _length и head . Первому присваивается количество узлов в списке; последний указывает на заголовок списка — узел в начале списка. Поскольку каждый новый экземпляр SinglyList не содержит узла, значение SinglyList по умолчанию равно null а значение _length по умолчанию равно 0 .

Методы односвязного списка

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

1 из 3: add(value)

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
SinglyList.prototype.add = function(value) {
    var node = new Node(value),
        currentNode = this.head;
 
    // 1st use-case: an empty list
    if (!currentNode) {
        this.head = node;
        this._length++;
         
        return node;
    }
 
    // 2nd use-case: a non-empty list
    while (currentNode.next) {
        currentNode = currentNode.next;
    }
 
    currentNode.next = node;
 
    this._length++;
     
    return node;
};

Добавление узла в наш список включает в себя много шагов. Давайте начнем с начала нашего метода. Мы используем аргумент add(value) для создания нового экземпляра Node , который назначается переменной с именем node . Мы также объявляем переменную с именем currentNode и инициализируем ее в _head нашего списка. Если в списке нет узлов, тогда значение head равно null .

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

Первый вариант использования предполагает добавление узла в пустой список. Если заголовок не указывает на узел, тогда назначьте node в качестве заголовка нашего списка, увеличьте длину нашего списка на единицу и верните node .

Второй вариант использования предполагает добавление узла в непустой список. Мы входим в цикл while и во время каждой итерации оцениваем, указывает ли currentNode.next на другой узел. (Во время первой итерации currentNode всегда указывает на начало списка.)

Если ответ отрицательный, мы присваиваем node currentNode.next и возвращаем node .

Если ответ «да», мы вводим тело цикла while. Внутри тела мы переназначаем currentNode на currentNode.next . Этот процесс повторяется до currentNode.next пор, пока currentNode.next больше не будет currentNode.next на другой узел. Другими словами, currentNode указывает на последний узел нашего списка.

while цикл прерывается. Наконец, мы присваиваем node currentNode.next , увеличиваем _length на единицу, а затем возвращаем node .

2 из 3: searchNodeAt(position)

Теперь мы можем добавить узлы в наш список, но мы не можем искать узлы в определенных позициях в нашем списке. Давайте добавим эту функциональность и создадим метод с именем searchNodeAt(position) , который принимает аргумент с именем position . Предполагается, что аргумент будет целым числом, указывающим узел в n-позиции в нашем списке.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
SinglyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: ‘Failure: non-existent node in this list.’};
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: a valid position
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
 
    return currentNode;
};

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

Если индекс, переданный searchNodeAt(position) , действителен, мы достигаем второго searchNodeAt(position) использования — цикла while. Во время каждой итерации цикла while currentNode который первым указывает на currentNode , переназначается следующему узлу в списке. Эта итерация продолжается до тех пор, пока count не станет равным позиции.

Когда цикл окончательно разрывается, возвращается currentNode .

3 из 3: remove(position)

Последний метод, который мы создадим, называется remove(position) .

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
SinglyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 0,
        message = {failure: ‘Failure: non-existent node in this list.’},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
 
    // 1st use-case: an invalid position
    if (position < 0 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
        deletedNode = currentNode;
        currentNode = null;
        this._length—;
         
        return deletedNode;
    }
 
    // 3rd use-case: any other node is removed
    while (count < position) {
        beforeNodeToDelete = currentNode;
        nodeToDelete = currentNode.next;
        count++;
    }
 
    beforeNodeToDelete.next = nodeToDelete.next;
    deletedNode = nodeToDelete;
    nodeToDelete = null;
    this._length—;
 
    return deletedNode;
};

Наша реализация remove(position) включает три варианта использования:

  1. Недопустимая позиция передается в качестве аргумента.
  2. Позиция единицы ( head списка) передается в качестве аргумента.
  3. Существующая позиция (не первая позиция) передается в качестве аргумента.

Первый и второй варианты использования просты в обращении. Что касается первого сценария, если список пуст или пропущена несуществующая позиция, выдается ошибка.

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

  1. head переназначается на currentNode.next .
  2. deletedNode указывает на currentNode .
  3. currentNode переназначается на null .
  4. Уменьшение _length нашего списка на единицу.
  5. deletedNode возвращается.

Третий сценарий сложнее всего понять. Сложность связана с необходимостью отслеживания двух узлов во время каждой итерации цикла while. Во время каждой итерации нашего цикла мы отслеживаем как узел перед удаляемым узлом, так и удаляемый узел. Когда наш цикл в конечном итоге достигает узла в позиции, которую мы хотим удалить, цикл завершается.

На данный момент мы beforeNodeToDelete ссылки на три узла: beforeNodeToDelete , nodeToDelete и deletedNode . Перед удалением nodeToDelete мы должны присвоить его значение next со следующим значением beforeNodeToDelete . Если цель этого шага кажется неясной, напомните себе, что у нас есть список связанных узлов; простое удаление узла разрывает связь между первым узлом списка и последним узлом списка.

Далее мы назначаем deletedNode для nodeToDelete . Затем мы устанавливаем значение nodeToDelete на nodeToDelete , уменьшаем длину списка на единицу и возвращаем deletedNode .

Завершение реализации односвязного списка

Полная реализация нашего списка здесь:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
function Node(data) {
    this.data = data;
    this.next = null;
}
 
function SinglyList() {
    this._length = 0;
    this.head = null;
}
 
SinglyList.prototype.add = function(value) {
    var node = new Node(value),
        currentNode = this.head;
 
    // 1st use-case: an empty list
    if (!currentNode) {
        this.head = node;
        this._length++;
 
        return node;
    }
 
    // 2nd use-case: a non-empty list
    while (currentNode.next) {
        currentNode = currentNode.next;
    }
 
    currentNode.next = node;
 
    this._length++;
     
    return node;
};
 
SinglyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: ‘Failure: non-existent node in this list.’};
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: a valid position
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
 
    return currentNode;
};
 
SinglyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 0,
        message = {failure: ‘Failure: non-existent node in this list.’},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
 
    // 1st use-case: an invalid position
    if (position < 0 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
        deletedNode = currentNode;
        currentNode = null;
        this._length—;
         
        return deletedNode;
    }
 
    // 3rd use-case: any other node is removed
    while (count < position) {
        beforeNodeToDelete = currentNode;
        nodeToDelete = currentNode.next;
        count++;
    }
 
    beforeNodeToDelete.next = nodeToDelete.next;
    deletedNode = nodeToDelete;
    nodeToDelete = null;
    this._length—;
 
    return deletedNode;
};

От одного до двух

Удивительно, наша реализация односвязного списка завершена. Теперь мы можем использовать структуру данных, которая добавляет, удаляет и ищет узлы в списке, которые занимают несмежное пространство в памяти.

Однако в этот момент все наши операции начинаются с начала списка и продолжаются до конца списка. Другими словами, они однонаправлены.

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

Двусвязный список

Список с двойной связью берет на себя всю функциональность списка с односвязной связью и расширяет его для двунаправленного перемещения в списке. Другими словами, мы можем пройти по связанному списку от первого узла в списке до последнего узла в списке; и мы можем перейти от последнего узла в списке к первому узлу в списке.

В этом разделе мы сосредоточимся в первую очередь на различиях между двусвязным списком и односвязным списком.

Операции двусвязного списка

Наш список будет включать два конструктора: Node и DoublyList . Давайте наметим их операции.

Узел

  • data хранят значение.
  • next указывает на следующий узел в списке.
  • previous указывает на предыдущий узел в списке.

DoublyList

  • _length возвращает количество узлов в списке.
  • head назначает узел в качестве заголовка списка.
  • tail назначает узел как хвост списка.
  • add(value) добавляет узел в список.
  • searchNodeAt(position) ищет узел в n-позиции в нашем списке.
  • remove(position) удаляет узел из списка.

Реализация двусвязного списка

Давайте напишем код!

Для нашей реализации мы создадим конструктор с именем Node :

1
2
3
4
5
function Node(value) {
    this.data = value;
    this.previous = null;
    this.next = null;
}

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

Далее нам нужно реализовать DoublyList и добавить три свойства: _length , head и tail . В отличие от односвязного списка, двусвязный список имеет ссылку как на начало списка, так и на конец списка. Поскольку каждый экземпляр DoublyList без узлов, значения по умолчанию head и tail устанавливаются в null .

1
2
3
4
5
function DoublyList() {
    this._length = 0;
    this.head = null;
    this.tail = null;
}

Методы двусвязного списка

Теперь мы рассмотрим следующие методы: add(value) , remove(position) и searchNodeAt(position) . Все эти методы были использованы для односвязного списка; однако, они должны быть переписаны для двунаправленного движения.

1 из 3: add(value)

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
DoublyList.prototype.add = function(value) {
    var node = new Node(value);
 
    if (this._length) {
        this.tail.next = node;
        node.previous = this.tail;
        this.tail = node;
    } else {
        this.head = node;
        this.tail = node;
    }
 
    this._length++;
     
    return node;
};

В этом методе у нас есть два сценария. Сначала, если список пуст, тогда назначьте его head и tail добавляемый узел. Во-вторых, если список содержит узлы, найдите хвост списка и назначьте tail.next узел; аналогично, нам нужно настроить новый хвост для двунаправленного движения. Другими словами, нам нужно установить tail.previous to the tail.

2 из 3: searchNodeAt(position)

Реализация searchNodeAt(position) идентична односвязному списку. Если вы забыли, как реализовать это, я включил его ниже:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
DoublyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: ‘Failure: non-existent node in this list.’};
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: a valid position
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
 
    return currentNode;
};

3 из 3: remove(position)

Этот метод будет самым сложным для понимания. Я покажу код, а затем объясню.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
DoublyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: ‘Failure: non-existent node in this list.’},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
 
        // 2nd use-case: there is a second node
        if (!this.head) {
            this.head.previous = null;
        // 2nd use-case: there is no second node
        } else {
            this.tail = null;
        }
 
    // 3rd use-case: the last node is removed
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    // 4th use-case: a middle node is removed
    } else {
        while (count < position) {
            currentNode = currentNode.next;
            count++;
        }
 
        beforeNodeToDelete = currentNode.previous;
        nodeToDelete = currentNode;
        afterNodeToDelete = currentNode.next;
 
        beforeNodeToDelete.next = afterNodeToDelete;
        afterNodeToDelete.previous = beforeNodeToDelete;
        deletedNode = nodeToDelete;
        nodeToDelete = null;
    }
 
    this._length—;
 
    return message.success;
};

remove(position) обрабатывает четыре варианта использования:

  1. Позиция, передаваемая в качестве аргумента remove(position) , не существует. В этом случае мы выдаем ошибку.
  2. Позиция, передаваемая в качестве аргумента remove(position) является первым узлом ( head ) списка. В этом случае мы назначим deletedNode а затем переназначим deletedNode следующему узлу в списке. В этот момент мы должны рассмотреть, есть ли в нашем списке более одного узла. Если ответ «нет», head будет присвоено значение null и мы введем часть if-else нашего оператора if-else . В теле if мы также должны установить tail в null — другими словами, мы возвращаемся в исходное состояние пустого двусвязного списка. Если мы удаляем первый узел в списке и в нашем списке более одного узла, мы вводим раздел else нашего оператора if-else . В этом случае мы должны правильно установить previous свойство head в null — нет никаких узлов перед заголовком списка.
  3. Позиция, передаваемая в качестве аргумента remove(position) является хвостом списка. Сначала deletedNode назначается tail . Во-вторых, tail переназначается узлу, предшествующему хвосту. В-третьих, у нового хвоста нет узла после него, и его значение next должно быть равно null .
  4. Здесь многое происходит, поэтому я сосредоточусь на логике больше, чем на каждой строке кода. Мы разрываем наш цикл while, когда currentNode указывает на узел в позиции, передаваемой в качестве аргумента для remove(position) . В этот момент мы переназначаем значение beforeNodeToDelete.next узлу после nodeToDelete и, наоборот, переназначаем значение afterNodeToDelete.previous узлу перед nodeToDelete . Другими словами, мы удаляем указатели на удаленный узел и переназначаем их на правильные узлы. Далее мы назначаем deletedNode для nodeToDelete . Наконец, мы присваиваем nodeToDelete значение null .

Наконец, мы уменьшаем длину нашего списка и возвращаем deletedNode .

Завершить реализацию двусвязного списка

Вот полная реализация:

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
function Node(value) {
    this.data = value;
    this.previous = null;
    this.next = null;
}
 
function DoublyList() {
    this._length = 0;
    this.head = null;
    this.tail = null;
}
 
DoublyList.prototype.add = function(value) {
    var node = new Node(value);
 
    if (this._length) {
        this.tail.next = node;
        node.previous = this.tail;
        this.tail = node;
    } else {
        this.head = node;
        this.tail = node;
    }
 
    this._length++;
 
    return node;
};
 
DoublyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: ‘Failure: non-existent node in this list.’};
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: a valid position
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
 
    return currentNode;
};
 
DoublyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: ‘Failure: non-existent node in this list.’},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
 
        // 2nd use-case: there is a second node
        if (!this.head) {
            this.head.previous = null;
        // 2nd use-case: there is no second node
        } else {
            this.tail = null;
        }
 
    // 3rd use-case: the last node is removed
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    // 4th use-case: a middle node is removed
    } else {
        while (count < position) {
            currentNode = currentNode.next;
            count++;
        }
 
        beforeNodeToDelete = currentNode.previous;
        nodeToDelete = currentNode;
        afterNodeToDelete = currentNode.next;
 
        beforeNodeToDelete.next = afterNodeToDelete;
        afterNodeToDelete.previous = beforeNodeToDelete;
        deletedNode = nodeToDelete;
        nodeToDelete = null;
    }
 
    this._length—;
 
    return message.success;
};

Вывод

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

73
Share: