Is "node" an ADT? If so, what is its interface?

Nodes are useful for implementing ADTs, but is "node" itself an ADT? How does one implement "node"? Wikipedia uses a plain old struct with no methods in its (brief) articl开发者_C百科e on nodes. I googled node to try and find an exhaustive article on them, but mostly I found articles discussing more complex data types implemented with nodes.

Just what is a node? Should a node have methods for linking to other nodes, or should that be left to whatever owns the nodes? Should a node even be its own standalone class? Or is it enough to include it as an inner struct or inner class? Are they too general to even have this discussion?

---

A node is an incredibly generic term. Essentially, a node is a vertex in a graph - or a point in a network.

In relation to data structures, a node usually means a single basic unit of data which is (usually) connected to other units, forming a larger data structure. A simple data structure which demonstrates this is a linked list. A linked list is merely a chain of nodes, where each node is linked (via a pointer) to the following node. The end node has a null pointer.

Nodes can form more complex structures, such as a graph, where any single node may be connected to any number of other nodes, or a tree where each node has two or more child nodes. Note that any data structure consisting of one or more connected nodes is a graph. (A linked list and a tree are both also graphs.)

In terms of mapping the concept of a "node" to Object Oriented concepts like classes, in C++ it is usually customary to have a Data Structure class (sometimes known as a Container), which will internally do all the work on individual nodes. For example, you might have a class called LinkedList. The LinkedList class then would have an internally defined (nested) class representing an individual Node, such as LinkedList::Node.

In some more cruder implementations you may also see a Node itself as the only way to access the data structure. You then have a set of functions which operate on nodes. However, this is more commonly seen in C programs. For example, you might have a struct LinkedListNode, which is then passed to functions like void LinkedListInsert(struct LinkedListNode* n, Object somethingToInsert);

In my opinion, the Object Oriented approach is superior, because it better hides details of implementation from the user.

---

Generally you want to leave node operations to whatever ADT owns them. For example a list should have the ability to traverse its own nodes. It doesn't need to the node to have that ability.

Think of the node as a simple bit of data that the ADT holds.

---

In the strictest terms, any assemblage of one or more primitive types into some kind of bundle, usually with member functions to operate on the data, is an Abstract Data Type.

The grey area largely comes from which language you operate under. For example, in Python, some coders consider the list to be a primitive type, and thus not an ADT. But in C++, the STL List is definitely an ADT. Many would consider the STL string to be an ADT, but in C# it's definitely a primitive.

To answer your question more directly: Any time you are defining a data structure, be it struct or class, with or without methods, it is necessarily an ADT because you are abstracting primitive data types into some kind of construct for which you have another purpose.

---

An ADT isn't a real type. That's why it's called an ADT. Is 'node' an ADT? Not really, IMO. It can be a part of one, such as a linked list ADT. Is 'this node I just created to contain thingys' an ADT? Absolutely not! It's, at best, an example of an implementation of an ADT.

There's really only one case in which ADT's can be shown expressed as code, and that's as templated classes. For example, std::list from the C++ STL is an actual ADT and not just an example of an instance of one. On the other hand, std::list<thingy> is an example of an instance of an ADT.

Some might say that a list that can contain anything that obeys some interface is also an ADT. I would mildly disagree with them. It's an example of an implementation of an ADT which can contain a wide variety of objects that all have to obey a specific interface.

A similar argument could be made about the requirements of the std::list's "Concepts". For instance that type T must be copyable. I would counter that by saying that these are simply requirements of the ADT itself while the previous version actually requires a specific identity. Concepts are higher level than interfaces.

Really, an ADT is quite similar to a "pattern" except that with ADT's we're talking about algorithms, big O, etc... With patterns we're talking about abstraction, reuse, etc... In other words, patterns are a way to build something that's implementations solve a particular type of problem and can be extended/reused. An ADT is a way to build an object that can be manipulated through algorithms but isn't exactly extensible.

---

Nodes are a detail of implementing the higher class. Nodes don't exist or operate on their own- they only exist because of the need for separate lifetimes and memory management than the initial, say, linked list, class. As such, they don't really define themselves as their own type, but happily exist with no encapsulation from the owning class, if their existence is effectively encapsulated from the user. Nodes typically also don't display polymorphism or other OO behaviours.

Generally speaking, if the node doesn't feature in the public or protected interface of the class, then don't bother, just make them structs.

---

In the context of ADT a node is the data you wish to store in the data structure, plus some plumbing metadata necessary for the data structure to maintain its integrity. No, a node is not an ADT. A good design of an ADT library will avoid inheritance here because there is really no need for it.

I suggest you read the code of std::map in your compiler's standard C++ library to see how its done properly. Granted, you will probably not see an ADT tree but a Red-Black tree, but the node struct should be the same. In particular, you will likely see a lightweight struct that remains private to the data structure and consisting of little other than data.

---

You're mixing in three mostly orthogonal concepts in your question: C++, nodes, ADTs.

I don't think it's useful to try to sort out what can be said in general about the intersection of those concepts.

However, things can be said about e.g. singly linked list nodes in C++.

#include <iostream>

template< class Payload >
struct Node
{
    Node*   next;
    Payload value;

    Node(): next( 0 ) {}
    Node( Payload const& v ): next( 0 ), value( v ) {}

    void linkInFrom( Node*& aNextPointer )
    {
        next = aNextPointer;
        aNextPointer = this;
    }

    static Node* unlinked( Node*& aNextPointer)
    {
        Node* const result  = aNextPointer;
        aNextPointer = result->next;
        return result;
    }
};

int main()
{
    using namespace std;
    typedef Node<int>   IntNode;

    IntNode*    pFirstNode  = 0;

    (new IntNode( 1 ))->linkInFrom( pFirstNode );
    (new IntNode( 2 ))->linkInFrom( pFirstNode );
    (new IntNode( 3 ))->linkInFrom( pFirstNode );

    for( IntNode const* p = pFirstNode;  p != 0;  p = p->next )
    {
        cout << p->value << endl;
    }

    while( pFirstNode != 0 )
    {
        delete IntNode::unlinked( pFirstNode );
    }
}

I first wrote these operations in Pascal, very early eighties.

It continually surprises me how little known they are. :-)

Cheers & hth.,