Node (computer science)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often hierarchical, data structures such as linked lists, trees, and graphs. Large and complex data structures can be formed from groups of interlinked nodes. Nodes are conceptually similar to vertices, which are elements of a graph. Software is said to have a node graph architecture when its organization consists of interlinked nodes.

Pseudocode implementation examples[edit]

A node containing a single node reference field.

 record SinglyLinkedNode {
    next, // A reference to the next node
    data // Data or reference to data
 }

Here, three such nodes form a singly linked list of length 3: Node chain.svg

A node containing two node reference fields.

 record DoublyLinkedNode {
    previous, // A reference to the previous node
    next, // A reference to the next node
    data // Data or reference to data
 }

Here three such nodes form a doubly linked list of length 3: Doubly-linked-list.svg

Also common is a binary tree node containing references to left and right child nodes, and a reference to a parent node.

 record BinaryNode {
    parent, // A reference to the parent node                                
    left_child, // A reference to the left child node
    right_child, // A reference to the right child node
    data // Data or reference to data
 }

See also[edit]