patternModerate
Does every data type just boil down to nodes with pointers?
Viewed 0 times
nodesjustwitheverytypedownpointersdoesboildata
Problem
An array or vector is just a sequence of values. They can surely be implemented with a linked list. This is just a bunch of nodes with pointers to the next node.
Stacks and queues are two abstract data types commonly taught in Intro CS courses. Somewhere in the class, students often have to implement stacks and queues using a linked list as the underlying data structure, which means we are back to the same "collection of nodes" idea.
Priority queues can be created using a Heap. A heap can be thought of as a tree with the min value at the root. Trees of all sorts, including BSTs, AVL, heaps can be thought of as a collection of nodes connected by edges. These nodes are linked together where one node points to another.
It seems like every data concept can always boil down to just nodes with pointers to some other appropriate node. Is that right? If it's this simple, why do textbooks not explain that data is just a bunch of nodes with pointers? How do we go from nodes to binary code?
Stacks and queues are two abstract data types commonly taught in Intro CS courses. Somewhere in the class, students often have to implement stacks and queues using a linked list as the underlying data structure, which means we are back to the same "collection of nodes" idea.
Priority queues can be created using a Heap. A heap can be thought of as a tree with the min value at the root. Trees of all sorts, including BSTs, AVL, heaps can be thought of as a collection of nodes connected by edges. These nodes are linked together where one node points to another.
It seems like every data concept can always boil down to just nodes with pointers to some other appropriate node. Is that right? If it's this simple, why do textbooks not explain that data is just a bunch of nodes with pointers? How do we go from nodes to binary code?
Solution
Well, that is basically what all data structures boil down to. Data with connections. The nodes are all artificial - they don't actually exist physically. This is where the binary part comes in. You should create a few data structures in C++ and check out where your objects land in memory. It can be very interesting to learn about how the data is laid out in memory.
The main reason for so many different structures is that they all specialize in one thing or another. For example, it is typically faster to iterate through a vector instead of a linked list, due to how pages are pulled from memory. A linked list is better to store larger sized types because vectors must allocate extra space for unused slots (this is required in the design of a vector).
As a side note, an interesting data structure you may want to look at is a Hash Table. It does not quite follow the Nodes and Pointers system you are describing.
TL;DR: Containers basically all Nodes and Pointers but have very specific uses and are better for something and worse for others.
The main reason for so many different structures is that they all specialize in one thing or another. For example, it is typically faster to iterate through a vector instead of a linked list, due to how pages are pulled from memory. A linked list is better to store larger sized types because vectors must allocate extra space for unused slots (this is required in the design of a vector).
As a side note, an interesting data structure you may want to look at is a Hash Table. It does not quite follow the Nodes and Pointers system you are describing.
TL;DR: Containers basically all Nodes and Pointers but have very specific uses and are better for something and worse for others.
Context
StackExchange Computer Science Q#68346, answer score: 16
Revisions (0)
No revisions yet.