0
When creating linked lists (singly- or doubly-linked), the elements in the list are known as nodes. A node class defines how these nodes work. Generally, a node will contain a member pointer to the data it represents (which is typically an abstract data type rather than a concrete data class), as well as a pointer to the next node in the list, and the previous node if it is doubly-linked. The list itself maintains a member pointer to the head node in the list, and the tail node if doubly-linked.
In this way, the list is only concerned with the nodes, not the data within those nodes. By the same token the nodes are only concerned with their nearest neighbouring nodes, not the list, nor the data they contain. Similarly, the data is only concerned with itself and other data, it is not concerned with the fact it may be part of a list or a node.
All work concerning nodes can then be delegated to the nodes themselves, while any work relating to the data can be delegated to the data. Thus each class plays a small but clearly defined role within the list; no class does any more than it has to, which greatly simplifies the list interface.
Wiki User
∙ 11y ago
Add your answer:
Earn +20 pts
What is the definition of a list in programming?
A list is data type which implements a linear data sequence container object with elements that are allocated non-contiguously. To navigate a list, we use a node class. A node refers to an element but also refers to the next and previous nodes in the sequence. A simple node may be defined as follows: template<typename T> struct node { T* data; // link to an element (of some type T) node* next; // link to next node node* prev; // link to previous node };
What is the algorithm for inserting values into a queue in c plus plus?
A queue usually infers first in first out (FIFO), therefore new values will need to be inserted after the last node (the tail node) and the queue must maintain pointers to both the head node for extraction and the tail node for insertion, and each node must maintain a pointer to the next node in the queue (singly-linked list). The following code provides a bare-bones implementation of a singly-linked FIFO list, where each value is an integer. In real-life you'd use one of the built-in class templates, otherwise you'd have to re-write the same code to cater for all the different value types you might want to place in a queue (or create your own class template). However, the example serves to show the algorithm that is used to insert new values to the end of a queue. It does not show how to extract the first node from the queue. #include <iostream> using namespace std; class Node { public: Node( int iValue ):m_iValue( iValue ),m_pNext( NULL ){} ~Node(){ if( m_pNext ) delete m_pNext; } Node * GetNext()const{ return m_pNext; } void SetNext(Node * pNext ){ m_pNext = pNext; } int GetValue()const{ return m_iValue; } private: Node * m_pNext; int m_iValue; }; class Queue { public: Queue():m_pFirst(NULL),m_pLast(NULL){} ~Queue(){ if( m_pFirst ) delete m_pFirst; } Node * GetFirst()const{ return m_pFirst; } Node * GetLast()const{ return m_pLast; } void Insert( int iValue ); void ShowAll()const; private: Node * m_pFirst; Node * m_pLast; }; void Queue::Insert( int iValue ) { Node * pNew = new Node( iValue ); if( m_pLast ) m_pLast->SetNext( pNew ); else m_pFirst = pNew; m_pLast = pNew; } void Queue::ShowAll() const { Node * pNode = m_pFirst; while( pNode ) { cout << pNode->GetValue(); if( pNode != m_pLast ) cout << ", "; pNode = pNode->GetNext(); } cout << endl << endl; } int main() { Queue queue; queue.Insert( 2 ); queue.Insert( 1 ); queue.Insert( 3 ); queue.ShowAll(); return( 0 ); }
Write an iterative function to search an element in a binary search tree?
_node* search (_node* head, _key key) { _node* node; for (node=head; node != NULL;;) { if (key == node->key) return node; else if (key < node.>key) node = node->left; else node = node->right; } return node; }
Algoritm for deleting the last element from a list?
Given a list and a node to delete, use the following algorithm: // Are we deleting the head node? if (node == list.head) { // Yes -- assign its next node as the new head list.head = node.next } else // The node is not the head node { // Point to the head node prev = list.head // Traverse the list to locate the node that comes immediately before the one we want to delete while (prev.next != node) { prev = prev.next; } end while // Assign the node's next node to the previous node's next node prev.next = node.next; } end if // Before deleting the node, reset its next node node.next = null; // Now delete the node. delete node;
Is null node equal to leaf node?
No. A leaf node is a node that has no child nodes. A null node is a node pointer that points to the null address (address zero). Since a leaf node has no children, its child nodes are null nodes.
A node with an IP address of 168.34.88.29 belongs to a Class?
Class B Address
What is the pseudo code for returning the top element of a stack?
A stack is a singly-linked list where new elements are added (pushed) to the head, and existing elements are removed (popped) from the head. As such, the stack object need only maintain a pointer to the head node and implement the pop and push methods. A stripped-down implementation in C++ follows: // Forward declaration class stack; // Minimal declaration... class node { friend node * stack::pop(); node * next; }; // Minimal implementation of stack demonstrating pop implementation class stack { node * head; public: node * pop() { // store the head pointer node * popped = head; // update head pointer if not NULL if( head ) head = head.next; // return stored pointer return( popped ); } };
Java program to implement binary search tree?
public class BinaryTreeExample {public static void main(String[] args){new BinaryTreeExample().run();}static class Node{Node left;Node right;int value;public Node(int value) {this.value = value;}}public void run() {Node rootnode = new Node(25);System.out.println("Building tree with rootvalue" + rootnode.value);System.out.println("==========================");printInOrder(rootnode);}public void insert(Node node, int value) {if (value < node.value) {if (node.left != null) {insert(node.left, value);} else {System.out.println(" Inserted " + value +" to left of node " + node.value);node.left = new Node(value);}} else if (value > node.value) {if (node.right != null) {insert(node.right, value);} else {System.out.println(" Inserted " + value + "to right of node " + node.value);node.right = new Node(value);}}}public void printInOrder(Node node) {if (node != null) {printInOrder(node.left);System.out.println(" Traversed " + node.value);printInOrder(node.right);}}}Output of the programBuilding tree with root value 25=================================Inserted 11 to left of node 25Inserted 15 to right of node 11Inserted 16 to right of node 15Inserted 23 to right of node 16Inserted 79 to right of node 25Traversing tree in order=================================Traversed 11Traversed 15Traversed 16Traversed 23Traversed 25Traversed 79
What is the definition of a list in programming?
A list is data type which implements a linear data sequence container object with elements that are allocated non-contiguously. To navigate a list, we use a node class. A node refers to an element but also refers to the next and previous nodes in the sequence. A simple node may be defined as follows: template<typename T> struct node { T* data; // link to an element (of some type T) node* next; // link to next node node* prev; // link to previous node };
What is the algorithm for inserting values into a queue in c plus plus?
A queue usually infers first in first out (FIFO), therefore new values will need to be inserted after the last node (the tail node) and the queue must maintain pointers to both the head node for extraction and the tail node for insertion, and each node must maintain a pointer to the next node in the queue (singly-linked list). The following code provides a bare-bones implementation of a singly-linked FIFO list, where each value is an integer. In real-life you'd use one of the built-in class templates, otherwise you'd have to re-write the same code to cater for all the different value types you might want to place in a queue (or create your own class template). However, the example serves to show the algorithm that is used to insert new values to the end of a queue. It does not show how to extract the first node from the queue. #include <iostream> using namespace std; class Node { public: Node( int iValue ):m_iValue( iValue ),m_pNext( NULL ){} ~Node(){ if( m_pNext ) delete m_pNext; } Node * GetNext()const{ return m_pNext; } void SetNext(Node * pNext ){ m_pNext = pNext; } int GetValue()const{ return m_iValue; } private: Node * m_pNext; int m_iValue; }; class Queue { public: Queue():m_pFirst(NULL),m_pLast(NULL){} ~Queue(){ if( m_pFirst ) delete m_pFirst; } Node * GetFirst()const{ return m_pFirst; } Node * GetLast()const{ return m_pLast; } void Insert( int iValue ); void ShowAll()const; private: Node * m_pFirst; Node * m_pLast; }; void Queue::Insert( int iValue ) { Node * pNew = new Node( iValue ); if( m_pLast ) m_pLast->SetNext( pNew ); else m_pFirst = pNew; m_pLast = pNew; } void Queue::ShowAll() const { Node * pNode = m_pFirst; while( pNode ) { cout << pNode->GetValue(); if( pNode != m_pLast ) cout << ", "; pNode = pNode->GetNext(); } cout << endl << endl; } int main() { Queue queue; queue.Insert( 2 ); queue.Insert( 1 ); queue.Insert( 3 ); queue.ShowAll(); return( 0 ); }
Write an iterative function to search an element in a binary search tree?
_node* search (_node* head, _key key) { _node* node; for (node=head; node != NULL;;) { if (key == node->key) return node; else if (key < node.>key) node = node->left; else node = node->right; } return node; }
How to Print data of all nodes of linked list?
for (node=head; node!=null; node=node->next) printnode(node);
How to find the mirror image of a binary tree?
Refer to http://cslibrary.stanford.edu/110/BinaryTrees.html void mirror(struct node* node) { if (node==NULL) { return; } else { struct node* temp; // do the subtrees mirror(node->left); mirror(node->right); // swap the pointers in this node temp = node->left; node->left = node->right; node->right = temp; } }
Can we use doubly linked list as a circular linked list?
Yes. The tail node's next node is the head node, while the head node's previous node is the tail node.
Algoritm for deleting the last element from a list?
Given a list and a node to delete, use the following algorithm: // Are we deleting the head node? if (node == list.head) { // Yes -- assign its next node as the new head list.head = node.next } else // The node is not the head node { // Point to the head node prev = list.head // Traverse the list to locate the node that comes immediately before the one we want to delete while (prev.next != node) { prev = prev.next; } end while // Assign the node's next node to the previous node's next node prev.next = node.next; } end if // Before deleting the node, reset its next node node.next = null; // Now delete the node. delete node;
Is null node equal to leaf node?
No. A leaf node is a node that has no child nodes. A null node is a node pointer that points to the null address (address zero). Since a leaf node has no children, its child nodes are null nodes.
What is an intrathoracic node?
An intrathoracic node is a node within the chest cavity.
