We know that C has many primitive data types. These include integers, characters, floats, doubles, arrays, etc. Primitive data types are built-in data types provided by the language. They are used to store and manipulate data in a program and are modelled that way because of the physical constraints imposed by the machine implementing them.
They are limited in that they are more concerned with the device used to run the program than the information that the programmer desires to represent in the program. Imagine if we had primitive data types like humans and pets instead of numbers and characters. Instead of a program assuming that data should be modelled in terms of numbers and characters, it would require that everything be expressed in terms of humans and pets.
Primitive data types are limited in modelling real world objects standalone but they can be composed to produce more complex data types that do effectively model these objects.
What are abstract data types?
Abstract data types are data types that allow us to separate the concern of the interface of a data type from the underlying implementation details. Some common ADTs are:
- Stacks (LIFO)
- Queues (FIFO).
- Lists
- Sets
- Maps/Dictionaries/Associative Arrays
- Strings
With ADTs we do not concern ourselves with how the data type has been implemented e.g. how the code manages memory. Rather, we simply use the functions/methods associated with the data type to interact with it.
Strings in many languages are an abstraction on top of an underlying section of memory, as opposed to being fixed length characters arrays like in C . These languages allow us to manipulate these string ADTs through various methods e.g. split, replace, concatenate, etc., without knowing what even happens with the underlying memory. Many string implementations do not even have a fixed length for the string so it can grow indefinitely, limited only by memory constraints imposed by the system.
Stacks and Queues
Stacks are LIFO (last in first out) like a stack of plates where the last plate added to the top of the stack is the first plate we must remove in order to access the other plates. The common operations are:
- Push (add a plate to the top of the stack)
- Pop (remove the plate at the top of the stack)
Queues are FIFO (first in first out) like a line at the bank. The first person in the line will be the first person allowed to enter the bank. The common operations are:
- Enqueue (add someone to the back of the line)
- Dequeue (remove the person at the front of the line)
Notice that the operations used to work with these data types do not involve any detail of the underlying memory being used to store the information for the various nodes/items (e.g. plates and persons).
We ask the code to run the operations without thinking about how the data type was implemented i.e. the code that manages the pointers and nodes in the underlying linked list. A linked list can be used to implement a stack or a queue.