Data structures

In the previous post we have seen how to implement a singly linked list in C++. Let us implement doubly linked list today. The difference between SLL and DLL is, DLL has two pointers in each node. One pointer points to next node and the other points to the previous node. Also, we can have two external pointers - one pointer to first node of list - head and the other pointer pointing to last node of the list - tail. So let us write structure node and class dlist. struct node { int val; struct node * next; struct node * prev; }; class d_list { private: node * head; node * tail; public: d_list(); void append ( int val); void display (); void insert_beg ( int n); node * find_node ( int n); bool delete_node ( int n); }; We have written a class with basic operations like append, display, find and delete etc. Two functions which are not needed when compared to linkedlist class are find_last() and find_previous(). Saves ...

I came across this question in the net. Given a binary search tree, convert this into a sorted doubly linked list. Do not create any nodes, but just modify the links. Just like a DLL, binary tree node also has two links. But they are named left and right. What if we assume left is previous link and right is next link? OK, we don't even have to modify the structure of the nodes. Next important part is "sorted". We need a sorted DLL. Don't you get the idea now. Which traversal visits the nodes in ascending order or gives sorted output? In order traversal! That's right. So we need to visit the nodes in in-order traversal, store previous node in a static variable, and link this previous node to the next node visited using previous (left) and next(right) links. Now how do we determine the head of DLL? It should be the tree-minimum. So we can find tree minimum and set this as head. Or we can use in order traversal and set the node which has no previous node visited as h...

Deletion operation in DLL is simpler when compared to SLL. Because we don't have to go in search of previous node of to-be-deleted node.  Here is how you delete a node Link previous node of node of to-be-deleted to next node. Link next node of node of to-be-deleted to previous node. Free the memory of node of to-be-deleted Simple, isn't it. The code can go like this. prevnode = delnode->prev; nextnode = delnode->next; prevnode->next = nextnode; nextnode->prev = prevnode; free(delnode); And that is it. The node delnode is deleted. But we should always consider boundary conditions. What happens if we are trying to delete the first node or last node? If first node is to be deleted, its previous node is NULL. Hence step 3 should not be used.  And also, once head is deleted, nextnode becomes head . Similarly if last node is to be deleted, nextnode is NULL. Hence step 4 is as strict NO NO. And we should set prevnode to tail. After we put these things together, we have...

Doubly Linked List is a list where each node has two links - one to the next node and another to the previous node. Because of two links , operations on this list are considerably easie r . But t here is an overhead of one more pointer in each node. First we need to have a node for the list. As I mentioned earlier, the node will have data - in this case a simple integer and two pointers. struct node { int n; struct node * next; struct node * prev; }; typedef struct node * NODEPTR; We have type def ined NODEPTR as we will be use it often. Next we have to define two pointers - head of the list and tail of the list. And let us not forget to initialize them to NULL. int main () { NODEPTR head,tail; head = tail = NULL ; Our create_node function will be similar to that of singly linked list . Only difference is we have to initialize newnode->prev as well . To NULL. L et us write functions to insert a node to  list. Let ...