Czy jest połączona lista ADT, czy jest to struktura danych, czy obie te opcje?

Question

Jeśli używam standardową definicję abstrakcyjny typ danych jako czarną skrzynkę, która zapewnia pewne funkcje do zarządzania zbiór danych, połączonej listy pasuje do tego opisu:

pojemnika, który oferuje funkcje add (x) i uzyskać (i) (między innymi), które można wykorzystać do utrzymania listy obiektów.

Ale kiedy zadać sobie pytanie, co jest złożoność czas tych operacji, a potem okazuje się, że zależy to pojemnik jest realizowany:

Jeśli tylko wewnętrznie utrzymać łącze do węzła głowy, powyższe dwie operacje będą wykonywane w czasie O (n). Jeśli dodatkowo utrzymujesz łącze do węzła końcowego, uzyskasz O (1) czas na obu.

Moje pytanie brzmi, czy w celach edukacyjnych uważasz, że lista powiązana jest ADT lub struktura danych?

To pytanie pojawiło się, gdy próbowałem zaimplementować ADT stosu w Podręczniku projektowania algorytmu Skiena i czytałem o tym, jak wydajność jego metod put (x) i get() będzie zależała od tego, do której struktury danych wybrano Wdrożyć je. Książka mówi, że w tym przypadku nie ma to większego znaczenia, jeśli wybierzesz strukturę danych z listą lub połączoną listą, aby zaimplementować ten ADT, oba oferują podobną wydajność.

Ale czy? Czy to nie zależy od sposobu implementacji tej listy linków? Istnieje wiele sposobów na implementację samej połączonej listy, więc czy to nie sprawia, że ​​jest to tylko kolejny ADT?

Answer 1

Z Wikipedii na ADT: In computing, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior tak, połączonej listy jest ADT, a każdy ADT jest również struktura danych, więc lista jest powiązana zarówno.

EDIT:
jednak zauważyć, że pojedynczo-linked-list, i podwójnie związany-lista, oba mają te same operacje i taką samą złożoność tych operacji, a więc są zarówno związane lista ADT oraz nie rozróżniamy ich jako ADT. Ale są to różne struktury danych!

Answer 2

Sama lista połączona nie jest abstrakcyjna, jest konkretna. Jest to struktura danych. Złożoność czasowa dostępu do danych na połączonej liście będzie zależała od tego, który element jest twoim dostępem i ile elementów znajduje się na liście, ponieważ musisz przejść przez nie, aby uzyskać żądany element.

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

Answer 3

Lista powiązana to ADT.

Kiedy mówimy o strukturach danych, masz w zasadzie - Stosy, kolejki i listy (Nie nazywaj tego połączonej listy), drzewa itp

Podczas przesłuchania o połączonej listy, jest to ADT. Abstrakcyjny typ danych. Tak więc niezależnie nie ma żadnej wartości. Ale gdy chcesz zaimplementować listę, stos lub kolejkę, musisz użyć listy połączonej lub tablicy.

Jest abstrakcyjny, ponieważ ma wiele operacji, które można powiązać z nim w razie potrzeby i w zależności od rodzaju wdrożenia.

Lista w standardowej bibliotece Biblioteka C i C++ implementuje listę podwójnie połączoną. Lista połączona była zawsze używana w implementacji list i dlatego stała się tak synonimem struktur danych list.