Does every data type just boil down to nodes with pointers?

Question

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?

Answer 1

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.

Answer 2

It seems like every data concept can always boil down to just nodes with pointers to some other appropriate node.

Oh, dear no. You are hurting me.

Like I tried to explain elsewhere ("What's the difference between a binary search tree and a binary heap?") even for a fixed data structure there are several levels to understand it.

Like the priority queue you mention, if you only want to use it, it is an abstract data type. You use it knowing what kind of objects it stores, and what questions you can ask it to do. That's more data structures as a bag of items. On the next level its famous implementation, the binary heap, can be understood as a binary tree, but the last level is for efficiency reasons implemented as an array. No nodes and pointers there.

And also for graphs for instance, which certainly look like nodes and pointers(edges), you have two basic representations, adjacency array and adjacency lists. Not all pointers I imagine.

When really trying to understand data structures you have to study their good points and teire weaknesses. Sometimes a representation uses an array for efficiency (either space or time) sometimes there are pointers (for flexibility). This holds even when you have good "canned" implementations like the C++ STL, because also there you can choose sometimes the underlying representations. There is always a trade-off there.

Answer 3

Let's make an analogy with mathematics. Consider the following sentence: "$f:\mathbb{R} \rightarrow \mathbb{R}$ is a continuous function". Functions are really defined in terms of relations, which are defined in terms of sets. The set of real numbers is the unique complete totally ordered field: all of these concepts have definitions in simpler terms. In order to talk about continuity you need the concept of neighborhood, which is defined in relation to a topology... and so on all the way down to the axioms of ZFC.

Nobody expects you to say all of that just to define a continuous function, otherwise nobody would be able to get any work done at all. We just "trust" that someone made the boring work for us.

Every data structure you can possibly think of boils down to the basic objects that your underlying computational model deals with, integers in some register if you use a random-access machine, or symbols on some tape if you use a Turing machine.

We use abstractions because they free our mind from trivial matters, allowing us to talk about more complex problems. It is perfectly reasonable to just "trust" that those structures work: spiraling down into every single detail is - unless you have a specific reason to do so - a futile exercise that doesn't add anything to your argument.

Answer 4

Here's a counter-example: in λ-calculus, every data type boils down to functions. λ-calculus doesn't have nodes or pointers, the only thing it has are functions, therefore everything must be implemented using functions.

This is an example of encoding booleans as functions, written in ECMAScript:

const T   = (thn, _  ) => thn,
      F   = (_  , els) => els,
      or  = (a  , b  ) => a(a, b),
      and = (a  , b  ) => a(b, a),
      not = a          => a(F, T),
      xor = (a  , b  ) => a(not(b), b),
      iff = (cnd, thn, els) => cnd(thn, els)();

And this is a cons list:

const cons = (hd, tl) => which => which(hd, tl),
      first  = list => list(T),
      rest   = list => list(F);

Natural numbers can be implemented as iterator functions.

A set is the same thing as its characteristic function (i.e. the contains method).

Note that the above Church Encoding of Booleans is actually how conditionals are implemented in OO languages like Smalltalk, which don't have booleans, conditionals, or loops as language constructs and implement them purely as a library feature. An example in Scala:

sealed abstract trait Boolean {
  def apply[T, U <: T, V <: T](thn: => U)(els: => V): T
  def ∧(other: => Boolean): Boolean
  def ∨(other: => Boolean): Boolean
  val ¬ : Boolean

  final val unary_! = ¬
  final def &(other: => Boolean) = ∧(other)
  final def |(other: => Boolean) = ∨(other)
}

case object True extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): U = thn
  override def ∧(other: => Boolean) = other
  override def ∨(other: => Boolean): this.type = this
  override final val ¬ = False
}

case object False extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): V = els
  override def ∧(other: => Boolean): this.type = this
  override def ∨(other: => Boolean) = other
  override final val ¬ = True
}

object BooleanExtension {
  import scala.language.implicitConversions
  implicit def boolean2Boolean(b: => scala.Boolean) = if (b) True else False
}

import BooleanExtension._

(2 < 3) { println("2 is less than 3") } { println("2 is greater than 3") }
// 2 is less than 3

Answer 5

Many (most?) data structures are built of nodes and pointers. Arrays are another critical element of some data structures.

Ultimately, every data structure is just a bunch of words in memory, or just a bunch of bits. It's how they are structured and how we interpret and use them that matters.

Answer 6

Implementation of data structures always boils down to nodes and pointers, yes.

But why stop there? Implementation of nodes and pointers boils down to bits.

Implementation of bits boils down to electrical signals, magnetic storage, perhaps fiberoptic cables, etc. (In a word, physics.)

This is the reductio ad absurdum of the statement, "All data structures boil down to nodes and pointers." It's true—but it only relates to implementation.

---

Chris Date very able differentiates between implementation and model, though his essay is aimed at databases in particular.

We can go a little bit further if we realize that there is not a single dividing line between model and implementation. This is similar (if not identical) to the concept of "layers of abstraction."

At a given layer of abstraction, the layers "below" you (the layers on which you are building) are mere "implementation details" for the abstraction or model which you are addressing.

However, the lower layers of abstraction themselves have implementation details.

If you read a manual for a piece of software, you are learning about the abstraction layer "presented" by that piece of software, on which you can build your own abstractions (or just perform actions such as sending messages).

If you learn the implementation details of the piece of software, you will learn how the creators underpinned the abstractions which they built. The "implementation details" may include data structures and algorithms, among other things.

However, you would not consider voltage measurement to be part of the "implementation details" for any particular piece of software, even though this underlies how "bits" and "bytes" and "storage" actually work on the physical computer.

In summary, data structures are an abstraction layer for reasoning about and implementing algorithms and software. The fact that this abstraction layer is built on lower-level implementation details such as nodes and pointers is true but irrelevant within the abstraction layer.

---

A big part of really understanding a system is grasping how the abstraction layers fit together. So it's important to understand how data structures are implemented. But the fact that they are implemented, doesn't mean that the abstraction of data structures doesn't exist.

Answer 7

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.

An array or a vector can be implemented with a linked list, but almost never should be.

That's because accessing the $n$-th element in a linked list requires traversing a chain of $n$ pointers, and thus requires $\Theta(n)$ time. A tree-based implementation (still made out of just nodes and pointers) is a bit more efficient, requiring just $\Theta(\log n)$ time to access an arbitrary leaf, but that's still far short of the $\Theta(1)$ access time provided by using an actual array (i.e. a sequential block of random access memory). Also, on the CPU, accessing the actual array is far simpler to implement and faster to execute, and storing it takes less memory due to not having to waste any space on pointers between separate nodes.

Of course, actual physical arrays have their down sides, too: notably, they need $\Theta(n)$ time to insert a new element, something that a linked list can do in $\Theta(1)$ time if you already have a pointer to a neighboring element. Insertions at the end of the physical array can be amortized down to $\Theta(1)$ on average, at the cost of at most a constant factor of extra memory, just by rounding the actual allocated size of the array up to e.g. the closest power of 2. But if you need to do a lot of insertions and/or removals of elements in the middle of your list, a physical array may not be the best implementation for your data structure. Pretty often, though, you can replace insertions and removals with swaps, which are cheap.

If you broaden your scope a little, to include physical contiguous arrays in your toolbox, almost all practical data structures can indeed be implemented with those together with nodes and pointers.

In fact, off the top of my head, I can't think of any common data structure that would need anything else, although in some cases a bit of space or time efficiency can be squeezed out by stepping outside that paradigm. As an illustrative example of such a case, consider the XOR linked list, which allows a two-way traversable linked list to be implemented using (asymptotically) no more space than a one-way linked list, by replacing the individual next and previous node pointers by their bitwise XOR, and has a few other convenient features too (such as a $\Theta(1)$ reversal operation). In practice, though, those features are rarely useful enough to overcome its drawbacks, which include extra implementation complexity and incompatibility with standard garbage collection schemes.

Answer 8

If it's this simple, why do textbooks not explain that data is just a bunch of nodes with pointers?

Because that's not what "data" means. You are conflating abstract ideas with implementations. "Data" is a highly abstract idea: It's just another name for "information." A bunch of linked nodes with pointers (a.k.a., a "linked data structure") is a much more concrete idea: It's a specific way of representing and organizing information.

Some data abstractions lend themselves very well to "linked" implementations. There are not many good ways to implement the branching nature of a fully general tree without using explicit nodes and pointers (or, some isomorphism of nodes and pointers.) But then, there are other abstractions that you would never implement using nodes and pointers. Floating point numbers come to mind.

Stacks and queues fall somewhere in between. There are times when it makes a lot of sense to do a linked implementation of a stack. There are other times when it makes much more sense to use an array and a single "stack pointer".