The question of abstractness is closely related to the language it is implemented in.

In Java, C# and the like, an abstract data structure is truly an abstract one. You can’t instantiate it directly. This may be because it is an interface or an abstract class. It is a concept with some underlying things to it. LinkedList isn’t abstract – it is a concrete implementation of a List (that’s an abstract data structure in Java), which itself is a Collection (for more abstract set of operations on it).

In C, however, you don’t have the generics. Unless you are doing everything with void* types in a given data structure, it doesn’t really exist in the abstract. And so concepts such as hash tables (a concrete type in Java) and linked lists remain in the abstract realm until you make a “here is a struct with this data structure that allows you to implement a linked list”.

So, is it abstract or not? In some languages it is, in others it isn’t.

Lets confuse things a bit.

A linked list is a Pattern – it is a tool you use or implement when a particular problem calls for it. Some have argued that design patterns are missing language features. That it is abstract in one language and concrete in another is because it is a “missing” language feature in C and not in Java (but there its part of the class library rather than being a fundamental part of the language like in Lisp).

At the end of the day, don’t worry about if it is abstract or not. It is something. And you implement or use it somehow. When a C programmer and a Java programmer talk about a Linked List, they are talking about the same thing (just the C programmer did more work). That’s all that matters. Its a common way of talking about a common thing, and that’s what Patterns are about.

It just depends on how you interpret “abstract”. The excerpt you quote defines “abstract” as capable of holding different kinds of data.

Don’t confuse this sense of “abstract” with the JAVA/OOP sense of abstract. In Java, for example, the LinkedList class is not abstract — it can be instantiated.

The answer is open to interpretation.

To me a basic or concrete data structure simply manipulates memory. Linked lists and arrays fit the bill. Abstract data structures impose regulations or semantics above a basic data structure. Queues, stacks, heaps, and so on.