DEV Community

Cover image for Node-based Data Structure
Nelson chege
Nelson chege

Posted on

Node-based Data Structure

while searching for solutions on Google, I came across a new term, "node-based data structure" ,
this term was new to me and I decided to dig in a little bit deeper.
These are some of the concepts that I discovered while researching node-based data structures.

Node-based data structures are data structures that organizes and stores data as interconnected nodes. Each node contains data and one or more pointers that point to other nodes.

This structure allows for efficient traversal and manipulation of the data

what is a node ?
I explain this using an analogy;
think of how the TV show The Amazing Show worked, contestants reached a given destination and got instructions on how to reach the next destination. Now replace the destination as the data in a node and the instructions as the pointer to the next node

Simply node-base data structures are a collection of linked nodes that point to each other:

the two main node-base data structures are:
Linked List: its a data structure that can have a node that has a single pointer pointing to a next node singular linked list or two pointers, one pointing the previous and one pointing to the next doubly linked list

Tree: for trees you can have a multiple pointers pointing to the next nodes. Trees don't have pointers for previous nodes, this create a parent-child relationship between the nodes

Implementation of A Tree
we can represent a math equation into a tree
Using BODMAS we can create tree for this equation

3 * (y + x) as

     *
    / \
   /   \
  3  (y + x)
Enter fullscreen mode Exit fullscreen mode

and 3 * y + X as

     +
    / \
   /   \
(3 * y)  x
Enter fullscreen mode Exit fullscreen mode

Below is the code representation of the Tree


# represent 3 * (y + x) and  3 * y + X as trees 

class exp():
    pass

class Times(exp):
    def __init__(self,l,r):
        self.r = r
        self.l = l

    def __str__(self):
        return str(self.r) +" * "+ str(self.l)

    def eval(self,env):
        return self.r.eval(env) * self.l.eval(env)

class Plus(exp):
    def __init__(self,l,r):
        self.r = r
        self.l = l

    def __str__(self,l,r):
        return str(self.r) + " + " + str(self.l) 

    def eval(self,env):
        return self.r.eval(env) + self.l.eval(env)

class Const(exp):
    def __init__(self,val):
        self.val = val

    def __str__(self):
        return str(self.val)

    def eval(self):
        return self.val

class Variable(exp):
    def __init__(self,name):
        self.name = name

    def eval(self,env):
        return env[self.name]



# 3 * (y + x)
e1 = Times(Const(3),Plus(Variable('y'),Variable('x')))

# 3 * y + x
e2 = Plus(Times(Const(3),(Variable('y'))),Variable('x'))

# to get the calculations

env = {"x":2,"y":4}

e1.eval(env)
e2.eval(env)
Enter fullscreen mode Exit fullscreen mode

Top comments (0)