Сверните свой собственный связанный список / дерево в R?

Question

Я пытаюсь обдумать основные понятия языка программирования R и нахожу это трудным, поскольку R ориентирован на статистику, а не на программирование общего назначения. Я не могу найти ничего похожего на указатели / ссылки. Как бы вы реализовали связанный список, дерево поиска и т. Д. На языке R?

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

Редактировать: Что касается комментария Мэтта Шотвелла, смысл этого вопроса в том, что я хочу писать связанные списки и деревья аккуратно, в пределах R, а не как расширение, написанное на C или другом язык. Выполнение этого как расширение или путаница с загадочными деталями переводчика побеждает цель.

Answer 1

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

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

lst <- list() # creates an empty (length zero) list
lst[[1]] <- 1 # automagically extends the lst
lst[[2]] <- 2 # ditto

Это может быть неэффективно для длинных списков из-за способа, которым R обрабатывает память. Если возможно, создайте список заранее и назначьте их содержимое по мере их доступности.

lst <- list(1, 2, 3, 4, 5)    # a list of 5 items

lst <- vector("list", 10000)  # 10000 NULLs
lst[[1]] <- 1
lst[[10000]] <- 10000  # lst now contains 1, NULL, ..., NULL, 10000

Удаление элемента из списка может быть выполнено с отрицательными индексами.

lst <- list(1, 2, 3, 4, 5)
lst <- lst[-2]  # now contains 1, 3, 4, 5

Дерево - это просто список, содержащий другие списки.

tree <- list(list(1, 2), list(3, list(4, 5)))

# left child: list(1, 2)
tree[[1]]

# right child
tree[[2]]

# right child of right child:list(4, 5)
tree[[2]][[2]]

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