Is Linked List an ADT or is it a Data Structure, or both?
If I use the standard definition of an Abstract Data Type as a black box that provides some functions to manage a collection of data, a Linked List fits that description:
A container that offers functions add(x) and get(i) (among others) that can be used to maintain a list of objects.
But when you ask the question, what is the time complexity of these operations, then you realize it depends on how this container is implemented:
If you just internally maintain a link to the head node, the above two operations will perform in O(n) time. If you additionally maintain a link to the tail node, you'll get O(1) time on both.
So my question is, for learning purposes, do you consider a Linked List an ADT or a Data Structure?
This question came about when I was trying to implement a Stack ADT from Skiena's Algorithm Design Manual, and was reading about how the performance of it's put(x) and get() methods will depend on what Data Structure is chosen to implement it. The book says in this case it doesn't matter so much if you choose an array or a linked list data structure to implement this ADT, they both offer similar performance.
But do they? Doesn't it depend on how that link list is implemented? There are many ways to implement the linked list itself, so doesn't that fact make it just another ADT itself?
Answer
From Wikipedia on ADT: In computing, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior so, linked list is an ADT, and every ADT is also a data structure, so linked list is both.
EDIT:
However, notice that singly-linked-list, and doubly-linked-list, both have the same operations and the same complexity for these operations, so they are both a linked list ADT, and we do not distinguish between them as ADT concerned. But they are different data structures!