Связанный список - это ADT, или это структура данных, или и то, и другое?

Question

Если я использую стандартное определение Абстрактного Типа данных в качестве черного ящика, который предоставляет некоторые функции для управления сбором данных, Связанный Список соответствует этому описанию:

Контейнер, который предлагает функции add (x) и get (i) (среди прочих), которые можно использовать для ведения списка объектов.

Но когда вы задаете вопрос, какова временная сложность этих операций, вы понимаете, что это зависит от того, как реализован этот контейнер:

Если вы просто внутренне поддерживаете связь с головным узлом, две вышеуказанные операции будут выполнены за O (n) раз. Если вы дополнительно поддерживаете связь с хвостовым узлом, вы получите время O (1) для обоих.

Таким образом, мой вопрос для целей обучения: считаете ли вы связанный список ADT или структурой данных?

Этот вопрос возник, когда я пытался реализовать Stack ADT из Руководства по разработке алгоритмов Skiena и читал о том, как производительность его методов put (x) и get () будет зависеть от того, какую структуру данных выбрать для реализации. Это. В книге сказано, что в этом случае не так уж важно, выбираете ли вы массив или структуру данных связанного списка для реализации этого ADT, они оба предлагают одинаковую производительность.

Но они? Разве это не зависит от того, как реализован этот список ссылок? Существует много способов реализации самого связанного списка, поэтому разве этот факт не превращает его просто в другую ADT?

Answer 1

Из Википедии в ADT : In computing, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior таким образом, связанный список является ADT, а каждый ADT также является структурой данных, поэтому связанный список - это оба.

EDIT:
Однако обратите внимание, что односвязный список и двусвязный список имеют одинаковые операции и одинаковую сложность для этих операций, поэтому оба они являются ADT связного списка, и мы не делаемразличать их как ADTНо это разные структуры данных!

Answer 2

Связанный список является ADT.

Когда вы говорите о структурах данных, вы имеете в основном - стеки, очереди и списки (не называйте этот связанный список), деревья и т. Д.

Когда вы спрашиваете о связанном списке, это ADT. Абстрактный тип данных. Так что независимо это не имеет значения. Но если вы хотите использовать List, Stack или Queue, вам нужно использовать Linked List или Array.

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

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

Answer 3

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

http://en.wikipedia.org/wiki/Linked_list