Concrete data type vs Abstract data type (data structures)
I have done some googling, and have found few examples of data structures for each data type. I just want to make sure if I am right.
Abstract Data Type (ADT): arrays, stack, heap, and queues
Concrete Data Type (CDT): linked lists, arrays, trees
Question: I understand the definition of Abstract data type (ADT), but I do not understand concrete data types (CDT). The definition of CDT I found online was unclear. Please clarify this topic.
Question: Why are arrays part of both abstract and concrete data types?
Thanks.
Abstract Data Type (ADT): arrays, stack, heap, and queues
Concrete Data Type (CDT): linked lists, arrays, trees
Question: I understand the definition of Abstract data type (ADT), but I do not understand concrete data types (CDT). The definition of CDT I found online was unclear. Please clarify this topic.
Question: Why are arrays part of both abstract and concrete data types?
Thanks.
No, you are still confused.
ADT vs CDT is one of those dichotomies that only exist at some line drawn in the sand.
An abstract data type exists in terms of how it can be used. For example, an integer. It has properties of being a counting number and various mathematical operations can be performed on it. We don't know (or care) how it is actually implemented.
Likewise, a list or array is an abstract idea. We know that it keeps an ordered collection of homogeneous items. Operations include traversing/indexing, etc.
A concrete data type is the way an ADT is actually implemented. For example, a C++ compiler treats an int as a machine 32 (or larger) word, and uses the machine capabilities to perform mathematical operations on it.
Likewise, a C++ array is laid out in consecutive positions in memory. A c++ vector is a wrapper around a C++ array, managing memory &c.
Where the distinction lies depends on where your level of abstraction is:
- If we're at the language level, then an int would be an ADT and a std::vector would be a CDT. ints are magic but std::vector has a specific implementation in order to exist.
- If we're at the level of the user (whoever is using our structures, such as someone using the Standard Library), then both int and std::vector are ADTs. They do something, via an interface, and we don't know (or care) how they are actually implemented underneath.
- If we're at the machine level, then an int is a CDT. We manipulate a specific block of memory using machine operations. The structure of that block of memory matters to us. We care if it is big-endian or little-endian, sign-magnitude or two's-complement, &c.
To recap, the difference is the "level of abstraction", which is basically the level at which things become magic. (As in, how does a std::string work? Who cares? It's magic.)
I've discovered that this distinction is lost on a lot of people, including professors, so whenever you get into a conversation with someone about this stuff, the first thing you want to do is figure out where their level of abstraction is. (Often, you might find that it is arbitrary depending on what data structure you are discussing.)
Hope this helps.
ADT vs CDT is one of those dichotomies that only exist at some line drawn in the sand.
An abstract data type exists in terms of how it can be used. For example, an integer. It has properties of being a counting number and various mathematical operations can be performed on it. We don't know (or care) how it is actually implemented.
Likewise, a list or array is an abstract idea. We know that it keeps an ordered collection of homogeneous items. Operations include traversing/indexing, etc.
A concrete data type is the way an ADT is actually implemented. For example, a C++ compiler treats an int as a machine 32 (or larger) word, and uses the machine capabilities to perform mathematical operations on it.
Likewise, a C++ array is laid out in consecutive positions in memory. A c++ vector is a wrapper around a C++ array, managing memory &c.
Where the distinction lies depends on where your level of abstraction is:
- If we're at the language level, then an int would be an ADT and a std::vector would be a CDT. ints are magic but std::vector has a specific implementation in order to exist.
- If we're at the level of the user (whoever is using our structures, such as someone using the Standard Library), then both int and std::vector are ADTs. They do something, via an interface, and we don't know (or care) how they are actually implemented underneath.
- If we're at the machine level, then an int is a CDT. We manipulate a specific block of memory using machine operations. The structure of that block of memory matters to us. We care if it is big-endian or little-endian, sign-magnitude or two's-complement, &c.
To recap, the difference is the "level of abstraction", which is basically the level at which things become magic. (As in, how does a std::string work? Who cares? It's magic.)
I've discovered that this distinction is lost on a lot of people, including professors, so whenever you get into a conversation with someone about this stuff, the first thing you want to do is figure out where their level of abstraction is. (Often, you might find that it is arbitrary depending on what data structure you are discussing.)
Hope this helps.
Topic archived. No new replies allowed.