Эффективная реализация неизменяемого (двойного) LinkedList

Question

Прочитав этот вопрос Immutable or not immutable? и прочитав ответы на мои предыдущие вопросы о неизменности, я все еще немного озадачен эффективной реализацией простого LinkedList, который является неизменным. С точки зрения массива, похоже, легко - скопируйте массив и верните новую структуру на основе этой копии.

Якобы у нас есть общий класс Node:

class Node{ 
    private Object value; 
    private Node next; 
} 

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

Мне также интересно узнать ответы в Immutable or not immutable?, в которых упоминается оптимизация cerain, ведущая к log (n) времени и пространства с помощью двоичного дерева. Кроме того, я где-то читал, что добавление элева к фронту равно 0 (1). Это меня очень сильно озадачивает, как будто мы не предоставляем копию ссылок, тогда на самом деле мы модифицируем одни и те же структуры данных в двух разных источниках, что нарушает неизменность ...

Будет ли любой из ваших ответов работать на двусвязных списках? Я с нетерпением жду любых ответов/указаний на любые другие вопросы/решения. Заранее спасибо за вашу помощь.

Answer 1

Предположительно у нас есть общий класс узлов и классов LinkedList на основе вышеизложенного, позволяющий пользователю добавлять, удалять и т. Д. Теперь, как бы мы гарантировали неизменность?

Вы гарантируете неизменность, делая каждое поле объекта readonly и гарантируя, что каждый объект, на который ссылается одно из этих полей readonly, также является неизменным объектом. Если поля все только для чтения и относятся только к другим неизменяемым данным, то, очевидно, объект будет неизменным!

Должны ли мы рекурсивно копировать все ссылки на список при вставке элемента?

Вы могли бы. Различие, которое вы получаете здесь, - это разница между неизменяемыми и постоянными. Неизменяемую структуру данных нельзя изменить. A Постоянная структура данных использует тот факт, что структура данных является неизменной для повторного использования ее частей.

Упорная неизменны связанный список особенно легко:

abstract class ImmutableList 
{ 
    public static readonly ImmutableList Empty = new EmptyList(); 
    private ImmutableList() {} 
    public abstract int Head { get; } 
    public abstract ImmutableList Tail { get; } 
    public abstract bool IsEmpty { get; } 
    public abstract ImmutableList Add(int head); 
    private sealed class EmptyList : ImmutableList 
    { 
     public override int Head { get { throw new Exception(); } } 
     public override ImmutableList Tail { get { throw new Exception(); } } 
     public override bool IsEmpty { get { return true; } } 
     public override ImmutableList Add(int head) 
     { 
      return new List(head, this); 
     } 
    } 

    private sealed class List : ImmutableList 
    { 
     private readonly int head; 
     private readonly ImmutableList tail; 
     public override int Head { get { return head; } } 
     public override ImmutableList Tail { get { return tail; } } 
     public override bool IsEmpty { get { return false; } } 
     public override ImmutableList Add(int head) 
     { 
      return new List(head, this); 
     } 
    } 
} 
... 
ImmutableList list1 = ImmutableList.Empty; 
ImmutableList list2 = list1.Add(100); 
ImmutableList list3 = list2.Add(400); 

И там вы идете. Конечно, вы хотели бы добавить лучшую обработку исключений и другие методы, например методы IEnumerable<int>. Но есть постоянный непреложный список. Каждый раз, когда вы создаете новый список, вы повторно используете содержимое существующего неизменяемого списка; list3 повторно использует содержимое списка2, что можно сделать безопасно, потому что list2 никогда не изменится.

Будет ли какой-либо из ваших ответов работать над дважды связанными списками?

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

Создание постоянных двухсвязного списка довольно сложно, но есть способы сделать это. То, что я сделаю, - это подход к проблеме с другого направления. Вместо того, чтобы говорить «могу ли я сделать упорный двусвязный список?» спросите себя: «Каковы свойства двойного списка, который я считаю привлекательным?» Перечислите эти свойства, а затем посмотрите, можете ли вы создать постоянную структуру данных, обладающую этими свойствами.

Например, если вам понравилось, что двусвязные списки могут быть дешево расширены с любого конца, дешево разбиты пополам на два списка, а два списка могут быть объединены вместе, а оставшаяся структура - неизменный catenable deque, а не двусвязный список. Даю пример неизменного, не catenable здесь: дека

http://blogs.msdn.com/b/ericlippert/archive/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue.aspx

Продление его быть catenable Deque оставляется в качестве упражнения; бумага, на которую я ссылаюсь на пальцевые деревья, является хорошей для чтения.

UPDATE:

в соответствии с вышеизложенным нам нужно скопировать префикс до точки вставки. По логике непреложности, если w удаляет что-либо из префикса, мы получаем новый список, а также в суффиксе ... Почему копировать только префикс, а не суффикс?

Хорошо рассмотрим пример. Что делать, если у нас есть список (10, 20, 30, 40), и мы хотим вставить 25 в позицию 2? Поэтому мы хотим (10, 20, 25, 30, 40).

Какие части можно использовать повторно? У хвостов у нас есть (20, 30, 40), (30, 40) и (40). Ясно, что мы можем повторно использовать (30, 40).

Рисунок может помочь. Мы имеем:

10 ----> 20 ----> 30 -----> 40 -----> Empty 

и мы хотим

10 ----> 20 ----> 25 -----> 30 -----> 40 -----> Empty 

так давайте

| 10 ----> 20 --------------> 30 -----> 40 -----> Empty 
|      /
| 10 ----> 20 ----> 25 -/ 

Мы можем повторно использовать (30, 40), потому что часть общего для обоих списков.

UPDATE:

Можно ли предоставить код для случайного вставки и удаления, а?

Вот рекурсивный решение:

ImmutableList InsertAt(int value, int position) 
{ 
    if (position < 0) 
     throw new Exception(); 
    else if (position == 0) 
     return this.Add(value); 
    else 
     return tail.InsertAt(value, position - 1).Add(head); 
} 

Вы видите, почему это работает?

Теперь, как упражнение, напишите рекурсивный DeleteAt.

Теперь, как упражнение, введите нерекурсивный InsertAt и DeleteAt. Помните, у вас есть неизменный связанный список в вашем распоряжении, поэтому вы можете использовать его в своем итеративном решении!

Answer 2

Должны ли мы рекурсивно копировать все ссылки на список при вставке элемента?

Вы должны рекурсивно скопировать префикс списка до точки вставки, да.

Это означает, что вставка в неизменный связанный список - O (n). (As вставляет (не переписывает) элемент в массиве).

По этой причине вставка обычно неодобрительно (наряду с добавлением и конкатенацией).

Обычная операция по неизменяемым связанным спискам - «минус», то есть добавление элемента в начале, который является O (1).

Вы можете ясно видеть сложность, например. реализация Haskell. Учитывая, связанный список, определенный в качестве рекурсивного типа:

data List a = Empty | Node a (List a) 

мы можем определить «против» (вставка элемента на фронте) непосредственно как:

cons a xs = Node a xs 

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

Важно помнить о связанных списках:

• линейный доступ

Для неизменяемых списков это означает:

• копирование префикса списка обмена
• хвост.

Если вы часто вставляете новые элементы, предпочтительна структура на основе журнала, такая как дерево.

Answer 3

Существует способ подражать «мутации»: использование неизменных карт.

Для связного списка строк (в Scala стиле псевдокод):

case class ListItem(s:String, id:UUID, nextID: UUID)

то ListItems можно хранить в карте, где ключ UUID: type MyList = Map[UUID, ListItem]

Если я хочу для вставки нового ListItem в val list : MyList:

def insertAfter(l:MyList, e:ListItem)={ 
    val beforeE=l.getElementBefore(e) 
    val afterE=l.getElementAfter(e) 
    val eToInsert=e.copy(nextID=afterE.nextID) 
    val beforeE_new=beforeE.copy(nextID=e.nextID) 
    val l_tmp=l.update(beforeE.id,beforeE_new) 
    return l_tmp.add(eToInsert) 
} 

Где add, update, get занимает постоянное время, используя Map: http://docs.scala-lang.org/overviews/collections/performance-characteristics

Реализация двойной связанный список идет аналогично.