Advanced Structs Concepts

Recursive structs

A struct type can be defined in terms of itself. This is particularly useful when the struct variable is an element of a linked list or a binary tree, commonly called a node. In that case, the node contains links (the addresses) to the neighboring nodes.

In the following examples, next for a list and left and right for a tree are pointers to another Node-variable.

Linked List

The data field contains useful information (for example a float64), and next points to the successor node; in Go-code:

type Node struct {
    data float64
    next *Node
}

The first element of the list is called the head, and it points to the 2^nd element. The last element is called the tail; it doesn’t point to any successor, so its next field has value nil. Of course, in a real list, we would have many data-nodes. The list can grow or shrink dynamically. In the same way, you could define a doubly-linked list with a predecessor node field pr and a successor field su.

type Node struct {
    pr *Node
    data float64
    su *Node
}

Binary Tree

Here, each node has at ...