Nodes: The Building Block of Linked Structures, thesarfo

In Python, a list holds a sequence of elements you can walk from the first to the last:

a = [1, 2, 3, 4, 5]

At every position there’s a value, and (except at the end) a value that follows it. To model this explicitly, we use a node: a fundamental data structure holding two things — the value at the current position, and a pointer to the next value in the sequence.

class Node:
    def __init__(self, value, next):
        self.value = value
        self.next = next

    def getValue(self):
        return self.value

    def getNext(self):
        return self.next

    def setValue(self, value):
        self.value = value

    def setNext(self, next):
        self.next = next

# creating Node objects
first = Node(3, None)   # None means it points to nothing
second = Node(4, first) # this one points to first

Here’s the same idea in Java:

public class Node {
    public String data;
    public Node next;

    public Node(String data) { // set data and next in the constructor
        this.data = data;
        this.next = null;
    }

    public static void main(String[] args) {
        Node firstNode = new Node("I am a Node!");
        System.out.println(firstNode.data);
        System.out.println(firstNode.next);
    }
}

When a node is created, its next is null. To link nodes into a sequence, add a setter:

public class Node {
    public String data;
    public Node next;

    public Node(String data) {
        this.data = data;
        this.next = null;
    }

    public void setNextNode(Node node) {
        this.next = node;
    }

    public static void main(String[] args) {
        Node firstNode = new Node("I am a Node!");
        Node secondNode = new Node("I am the second Node!");

        firstNode.setNextNode(secondNode);
        System.out.println(firstNode.next.data);
    }
}

Since important state should only be reachable through methods, make next private and add a getter too:

public class Node {
    public String data;
    private Node next;

    public Node(String data) {
        this.data = data;
        this.next = null;
    }

    public void setNextNode(Node node) {
        this.next = node;
    }

    public Node getNextNode() {
        return this.next;
    }

    public static void main(String[] args) {
        Node firstNode = new Node("I am the first Node!");
        Node secondNode = new Node("I am the second Node!");
        firstNode.setNextNode(secondNode);
        System.out.println(firstNode.getNextNode().data);
    }
}

This node — a value plus a pointer to the next one — is the building block every linked list, stack, and queue in this section is built from.