Я пытаюсь написать отдельный список, связанный с блокировкой. Конечная согласованность не является проблемой (кто-то просматривает список, который может содержать неправильные элементы).
Я думаю, что я получил элемент add right (looping и Interlocked.CompareExchange
).
Но я не могу понять, как удалить узлы (в любом месте списка), так как я должен получить предыдущий элемент, и они устанавливают его поле Next
в текущее поле Next
.
class Node
{
Node Next;
object Value;
}
class SinglyLinkedList
{
Root _root;
public void Add(object value)
{}
public void Remove(object value)
{}
}
то есть.
a → b → c
to
a → c
Псевдокод:
Node prev;
Node node = _root;
while (node.Value != nodeValue)
{
prev = node;
node = node.Next;
}
prev.Next = node.Next;
как я могу сделать это атомарной операцией (т.е. убедиться, что prev.Next = node.Next
вызывается без последующего или предварительного удаления между другим потоком)?
Вместо этого я мог бы использовать ReaderWriterLockSlim
, но я нашел эту проблему интересной, поскольку я знаю, что существуют блокированные ссылки, не содержащие блокировки.
Мои проблемы:
При текущем потоке между циклом и присваиванием может произойти следующее:
- Сам
-
prev
мог быть удален другим потоком. -
node
может быть удален другим потоком. -
Node.Next
может быть удален