Одиночный список удалить

Question

Я занимался реализацией одиночного связывания, и я помню, как Линус Торвальдс говорил об этом here.

В отдельном списке для удаления узла мы должны иметь доступ к предыдущему узлу и затем изменять узел, на который он указывает.

Как это

Так каким-либо образом, мы должны иметь доступ к предыдущему узлу.

Но Линус Торвальдс удалил специальный случай, используя идею адреса в C. Так что голова также имеет «предыдущую вещь», которая является адресом головы, указывающим на голову. Поэтому он использовал функцию C указателя и адреса, чтобы удалить специальный случай.

нормальный код с специальным случаем

код с специальным случаем становится нормальным случаем

Я думаю, что этот вид специального удаления случае в односвязном списке не может быть сделан в Python, потому что мы не имеют понятия указателей (и, следовательно, я не смогу сделать один шаг перед головой)? Я прав ?

Answer 1

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

Теперь Python не является C, поэтому реализация будет отличаться, но принцип применяется. Сам список не является тем же объектом, что и его первый элемент, а элементы списка не должны иметь те же методы, что и список в целом, поэтому имеет смысл использовать для них отдельные типы объектов.

Оба они могут, однако, использовать атрибут с тем же именем (например, next), чтобы указать на следующий элемент. Поэтому, когда вы перебираете список, и вы находитесь в первом элементе, «предыдущий» элемент является самим списком, и вы управляете его атрибутом next, если вам нужно удалить первый элемент.

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

Answer 2

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

Answer 3

Моя первая мысль после прочтения вашего вопроса была: зачем вы хотите создать отдельный список в python? Python предлагает множество типов коллекций, и вы можете использовать их без необходимости беспокоиться о том, реализованы ли они как отдельные ссылки, как двойной связанный список или как некоторая нерекурсивная структура данных (которые обычно проще обрабатывать).

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

class Node: 
    def __init__(self, x, next): 
     self.x = x 
     self.next = next 

    def __str__(self): 
     return "<{}, {!s}>".format(self.x, self.next) 

n = Node(1, None) 
n = Node(2, n) 
n = Node(3, n) 
print(n) # output: <3, <2, <1, None>>> 

n.next.next = n.next.next.next 
print(n) # output: <3, <2, None>> 

Разница в C: мы не должны malloc() или работать с указателями, потому что Питон управляет памятью для нас. У Python есть ссылки вместо указателей, они похожи, но намного безопаснее и проще в использовании.

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

Answer 4

Вам нужно два уровня косвенности, чтобы сделать это так, как предлагает Линус, но вы можете сделать это на Python, возможно, имея ссылку на объект, который хранит ссылку на объект или что-то в этом роде (индекс индекс?). Тем не менее, я не думаю, что он так элегантно или эффективно отображает Python, и, вероятно, было бы довольно расточительно использовать объект, чтобы представлять только одну ссылку в связанной структуре.

В случае с Python я просто делал дополнительное ветвление, чтобы проверить случаи, когда вы удаляетесь из головы, если нет какой-то трюки, которой я не хватает.

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

... где сетка может иметь 10000 клеток. Большинство связанных списков, предоставляемых стандартными библиотеками, не оптимизированы для хранения 10 000 + связанных списков в размере 32-разрядного индекса для каждого списка, поскольку они пытаются предоставить интерфейсы, которые позволяют связанный список использоваться изолированно (не используя отдельная структура данных резервного копирования для хранения, такая как массив). Обычно наиболее эффективное использование связанного списка - это тот, который не владеет памятью или не управляет никакими ресурсами. Это просто связывание данных вспомогательным образом, уже выделенным и управляемым в другой структуре данных, как это для 128-битного (16-байтового) узла дерева в n-арном дереве, где элементы могут быть сохранены на любом уровне иерархии:

struct TreeNode 
{ 
    int32 parent;  // parent index or -1 for no parent 
    int32 first_child; // first child of this node or -1 
    int32 next_sibling; // next child for the parent node or -1 
    int32 element;  // element data stored in this node or -1 
         // if no data is associated 
}; 

Таким образом, есть много случаев использования для реализации собственных связанных списков и других связанных структур, которые значительно более эффективны для более узко применимого случая использования (структур данных сетки, octrees четырехъядерных деревьев, графиков и т.д.), но опять же, я не думаю, что вы можете использовать этот трюк на языках, которые не позволяют вам использовать два или более уровней указателя. Python по своей сути имеет только один объект для объектов - тот же, что и для Java и C#. Вам понадобится что-то вроде ссылки «ссылка на объект» или индекс «индекс к объекту» или «индекс ссылки объекта на объект».

Также связанные списки не так полезны на языках, которые не позволяют вам управлять тем, где все хранится в памяти, так как вы можете получить кеш-пропуски в изоляторах через связанные списки, иначе если каждый узел списка фрагментирован в как часто бывает после цикла GC, например Для того, чтобы связанные списки были действительно эффективными, как в случае с ядром Linux, вы должны иметь возможность реально контролировать то, где каждый узел находится в памяти, так что обход списка фактически в основном, если не полностью, просто повторяется через непрерывные фрагменты Память. В противном случае вы обычно лучше используете небольшие массивы, даже если это подразумевает удаление и вставки линейного времени в/из середины.