Node Based Data Structures

Many data structures are node based – Each node would carry some data, and be linked to other nodes. We can build a dynamic, reusable node data structure that can be used to power many different data structures.

In the below video, we explore just that, testing it out by building several data structures including a Linked List and a graph!

To review the code used in the video, please refer to the following download link: https://drive.google.com/open?id=0B2Ia5aQpQ8CnUmlmVVdqcndLRzg

This article serves as a summary of the above video, which has run a little long.

The Node Data Structure

Each node must minimally contain the following two things:

  • Data
  • One “subsequent” node to be connected to

By using Java Object Oriented Programming, we can express these things as attributes of a class.

In such cases, some getter and setter functions would be ideal:

  • getData()
  • setData()
  • getNext()
  • setNext()

Interestingly in Java, you can simply refer to a different node by containing the node object within your class.

This works because Java objects are recorded as references, allowing one object to refer to another instead of containing the second object within the first. The simplest form of our data structure looks like this:

Node
– data: int
– next: Node
+ Node(da:int, nx:Node)
+ getData(): int
+ getNext(): Node
+ setData(da:int)
+ setNext(nx:Node)

We can create a simple data structure like a linked list by simply chaining a set of nodes together, and maintaining a reference to the first (also known as the head). With creative pointer manipulations, you can read, insert to and delete from the list, allowing the node based structure to be completely transparent to the user. For more on linked lists, refer to this earlier blog post: Demystifying Linked Lists

Using generics

Right now, our nodes only hold integer data values. As such, they cannot be used if we want to record other types. Luckily, Java allows us to easily solve this problem with generics.

Generics allows a user to specify a variable data type. As such, the Node object may be adapted to record any kind of information. We use “T” to represent this unknown data type:

Node<T>
– data: T
– next: Node
+ Node(da:T, nx:Node)
+ getData(): T
+ getNext(): Node
+ setData(da:T)
+ setNext(nx:Node)

With this, we can specify the generic type when creating a node. For example, if we wished to create a node containing a String, we could specify:

Node<String> myNode = new Node<String>("Hello World!", null);

Extending Further

While nodes with one link are useful for simple data structures like the Linked List, this is usually insufficient for more complex data structures like trees or graphs. Luckily, we can easily expand upon this by adding more entries for a node to link to.

In fact, for a general purpose Node data structure, you would want to hold the neighbors in an array or list like so:

Node<T>
– data: T
– neighbors: ArrayList<Node>
+ Node(da:T)
+ getData(): T
+ setData(da:T)
+ getNeighbors(): Node[]
+ setNeighbors(nei:Node[])

Applications & Wrapup

As we have previously mentioned, nodes can be used to implement many types of data structures, from Linked Lists to graphs. In fact, these are the two data structures we tested in the video! You’ll also find code pages for these applications in the download above.

A node is a very fundamental unit of a more complex data structure, and understanding its thought process can help us get a better grasp of the computational thinking that goes into data structures and working them.

That’s all for this post! If you like my work and wish to support me, I’ll greatly appreciate a one-time or recurring donation!