Динамические структуры данных: различия между версиями

===Добавление в начало - AddFirst===
Пусть '''TNode<T>''' node - новый узел списка self, тогда:
var node = new TNode<'''T'''>(value, <span style="color:blue">self</span>.'''Head''', null)
if (<span style="color:blue">self</span>.'''Count''' > 0) then
<span style="color:blue">self</span>.Head.'''Previous''' = node
<span style="color:blue">self</span>.'''Head''' = node
<span style="color:blue">self</span>.'''Count''' += 1
[[File:AddFirstMethod2.jpg|frameless|400px]]
 
Пусть '''TNode<T>''' node - новый узел списка self, а '''TNode<T>''' last - последний узел списка self тогда:
var node = new TNode<'''T'''>(value)
if (<span style="color:blue">self</span>.'''Count''' == 0) then
<span style="color:blue">self</span>.'''Head''' = node
else
self.last.'''Next''' = node
node.'''Previous''' = <span style="color:blue">self</span>.'''last'''
<span style="color:blue">self</span>.'''Count''' += 1
 
===Вставка после целевого узла - InsertAfter===
Пусть '''TNode<T>''' node - новый узел списка self, а '''TNode<T>''' target - узел списка self (target.Value == targetValue), после которого будет добавлен node, тогда:
if (<span style="color:blue">self</span>.'''Count''' == 0) then
error
var node = new TNode<'''T'''>(value, target.'''Next''', target)
if (node.'''Next''' != null) then
node.Next.'''Previous''' = node
<span style="color:blue">self</span>.'''Count''' += 1
Предполагается, что target существует, иначе - ошибка.
 
===Вставка перед целевым узлом - InsertBefor===
Пусть '''TNode<T>''' node - новый узел списка self, '''TNode<T>''' target - узел списка self (target.Value == targetValue), перед которым будет добавлен node, а '''TNode<T>''' ancillary - узел списка self (ancillary.Next == target), который может ссылаться на node, тогда:
if (<span style="color:blue">self</span>.'''Count''' == 0) then
error
var node = new TNode<'''T'''>(value, <span style="color:blue">self</span>.'''Head''', null)
if (<span style="color:blue">self</span>.Head.'''Value''' == target.'''Value''') then
{
<span style="color:blue">self</span>.Head.'''Previous''' = node
<span style="color:blue">self</span>.'''Head''' = node
else
{
target.'''Previous''' = node
}
<span style="color:blue">self</span>.'''Count''' += 1
Предполагается, что target существует, иначе - ошибка.
 
 
===Удаление первого узла - RemoveFirst===
if (<span style="color:blue">self</span>.'''Count''' == 0) then
error
<span style="color:blue">self</span>.'''Head''' = <span style="color:blue">self</span>.Head.'''Next'''
if (<span style="color:blue">self</span>.'''Head''' != null) then
<span style="color:blue">self</span>.Head.'''Previous''' = null
<span style="color:blue">self</span>.'''Count''' -= 1
 
===Удаление последнего узла - RemoveLast===
Пусть '''TNode<T>''' predLast - предпоследний узел списка self, тогда:
if (<span style="color:blue">self</span>.'''Count''' == 0) then
error
if (<span style="color:blue">self</span>.'''Count''' == 1) then
<span style="color:blue">self</span>.'''Head''' = null
else
self.predLast.'''Next''' = null
<span style="color:blue">self</span>.'''Count''' -= 1
 
===Удаление после целевого узла - RemoveAfter===
Пусть '''TNode<T>''' target - узел списка self (target.Value == value), после которого будет удален node, тогда:
if (<span style="color:blue">self</span>.'''Count''' in set{0, 1}) then ''# Гарантия существования хотя бы двух узлом списка.''
error
target.'''Next''' = target.Next.'''Next'''
if (target.'''Next''' != null) then
target.Next.'''Previous''' = target
<span style="color:blue">self</span>.'''Count''' -= 1
 
===Удаление целевого узла - Remove===
Пусть '''TNode<T>''' target - узел списка self, после которого будет удален node, тогда:
if (<span style="color:blue">self</span>.'''Count''' == 0) then ''# Гарантия существования хотя бы одного узла списка.''
error
if (node.'''Value''' == <span style="color:blue">self</span>.Head.'''Value''') then
<span style="color:blue">self</span>.'''Head''' = <span style="color:blue">self</span>.Head.'''Next'''
if (<span style="color:blue">self</span>.'''Head''' != null) then
<span style="color:blue">self</span>.Head.'''Previous''' = null
else
target.'''Next''' = target.Next.'''Next'''
if (target.'''Next''' != null) then
target.Next.'''Previous''' = target
<span style="color:blue">self</span>.'''Count''' -= 1
''Пояснение: если удаляемый элемент - это голова списка, то переместить голову списка на один узел вперёд; если список еще содержит элементы, то убрать ссылку на предыдущий элемент для текущей головы списка; если удаляемый узел - не голова, то убрать связь с удаляемым элементом; если удаляемый элемент не был последним, то установить ссылку Previous на предыдущий узел предыдущего узла.''