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

Question

Nodes are useful for implementing ADT, but is node itself an ADT? How to implement "node"? Wikipedia uses a simple old structure without methods in its (short) article on nodes. I googled node to try to find a comprehensive article about them, but basically I found articles that discussed more complex data types implemented with nodes.

What is node? Should the node have methods for binding to other nodes or should it be left to everything that belongs to the nodes? Should node be its own standalone class? Or is it enough to include it as an internal structure or inner class? Are they too general to even discuss this?

Answer 1

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

In terms of data structures, a node usually means one basic unit of data, which (usually) is linked to other units, forming a large data structure. A simple data structure that demonstrates this is a linked list. A linked list is just a chain of nodes, where each node is connected (via a pointer) to the next node. The end of the node has a null pointer.

Nodes can create more complex structures, such as a graph, where any one node can 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 related nodes is a graph. (The linked list and tree are also graphs.)

In terms of comparing the concept of “node” with object-oriented concepts such as classes, in C ++ it is usually customary to have a data structure class (sometimes called a container) that internally does all the work on individual nodes. For example, you might have a class called LinkedList . The LinkedList class would then have an internal (nested) class representing a separate Node, such as LinkedList::Node .

In some rougher implementations, you can also see node itself as the only way to access the data structure. Then you have a set of functions that work on nodes. However, this is more common in C programs. For example, you may have a struct LinkedListNode , which is then passed to functions such as void LinkedListInsert(struct LinkedListNode* n, Object somethingToInsert);

In my opinion, the object-oriented approach is excellent because it better hides implementation details from the user.

Answer 2

Typically, you want to leave node operations to the fact that they own ADT. For example, a list should be able to navigate through its own nodes. No node is required for this feature.

Think of node as a simple data bit that supports ADT.

Answer 3

ADT is not a real type. That's why he called ADT. Is the 'node' ADT? Not really, IMO. It can be part of one, for example, a linked ADT list. Is 'this node I just created to contain thingys' ADT? Absolutely not! This is, at best, an example of an ADT implementation.

In fact, there is only one case in which ADT can be displayed as code, and that as template classes. For example, the std :: list from C ++ STL is the actual ADT, not just an example of an instance of one. std::list<thingy> , on the other hand, is an example of an ADT instance.

Some may say that a list that can contain anything that obeys some interface is also an ADT. I would not agree with them. This is an example of an ADT implementation that can contain a large number of objects, which everyone must obey a specific interface.

A similar argument can be made about the requirements of std :: list "Concepts". For example, type T must be copied. I would step back from this, saying that these are just the requirements of the ADT itself, while the previous version actually requires specific identification. Concepts of a higher level than interfaces.

Indeed, ADT is very similar to a “template”, except that with ADT we are talking about algorithms, big O, etc. With templates, we talk about abstraction, reuse, etc ... In other words, templates are a way to create something that implementations solve a particular type of problem and can be extended / reused. ADT is a way to create an object that can be manipulated using algorithms, but is not extensible.

Answer 4

In the strict sense, any assembly of one or more primitive types into a set, usually with member functions for working with data, is an abstract data type.

The gray area is heavily dependent on the language you work in. For example, in Python, some coders consider a list to be a primitive type and therefore not an ADT. But in C ++, the STL list is definitely an ADT. Many people think that the STL line is ADT, but in C # it is definitely a primitive.

To answer your question more directly: every time you define a data structure, whether it is a structure or a class, with or without methods, it is mandatory ADT, because you are abstracting primitive data types into some kind of construct for which you have a different target.

Answer 5

In the context of ADT, a node is the data that you want to save in the data structure, as well as some plumbing metadata necessary to maintain the integrity of the data structure. No, node is not an ADT. A good ADT library design avoids inheritance here because it is not necessary.

I suggest you read the std::map code in your standard C ++ compiler library to see how this is done correctly. Of course, you probably won't see the ADT tree, but the Red-Black tree, but the node structure should be the same. In particular, you will most likely see a lightweight structure that remains private to the data structure and consists of a few other than the data.

Answer 6

Nodes are top-level implementation details. Nodes do not exist or work on their own - they exist only because of the need to use separate lives and manage memory than the original, say, linked list, class. Thus, they do not really define themselves as their own type, but, fortunately, exist without encapsulation from the owner class if their existence is effectively encapsulated from the user. Nodes usually also do not display polymorphism or other OO behavior.

In the general case, if node is not present in the public or secure interface of the class, then do not worry, just create their structs.

Answer 7

You mix three basic orthogonal concepts in your question: C ++, nodes, ADT.

I do not think it is useful to try to figure out what can be said at all about the intersection of these concepts.

However, we can say, for example, about the nodes with a single connection 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 in the early 80s.

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

Cheers and hth.,