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, the开发者_如何学JAVAy 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?

---

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!

---

Linked List is an ADT.

When you talk about data structures, you have basically - Stacks, Queues and Lists(Don't call this linked list), Trees, etc.

When you are questioning about Linked List, it is an ADT. An Abstract Data Type. So independently it has no value. But when you want a List or a Stack or a Queue implemented, you need to use a Linked List or Array.

It's abstract because it has multiple operations that can be associated with it as and when needed and depending on the type of implementation.

List in Standard Template Library of C and C++ implement Doubly Linked List. Linked List has been always used in implementation of Lists and that's why it has become so synonymous with the List data structures.

---

A linked list itself is not abstract, it's concrete. It's considered a data structure. Time complexity of accessing data in a linked list will depend on which element your accessing and how many elements are in the list, as you have to iterate through them to get to your desired element.

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