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

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

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

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

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

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

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

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