Monday, December 15, 2008

Insert and Delete operations on Double Linked List

struct Node
{
Node* Prev;
Node* Next;
int data;
};

void InsertNode(Node** ppNode, int num)
{
if(*ppNode == NULL)
{
*ppNode = new Node();
(*ppNode)->data = num;
(*ppNode)->Next = NULL;
(*ppNode)->Prev = NULL;
return;
}
Node * pTemp = *ppNode;
while(pTemp->Next != NULL)
pTemp = pTemp->Next;
pTemp->Next = new Node();
pTemp->Next->data = num;
pTemp->Next->Prev = pTemp;
pTemp->Next->Next = NULL;
return;
}
void Display(Node *pNode)
{
while(pNode)
{
cout<<" "<data;
pNode = pNode->Next;
}
}
bool DeleteNode(Node** ppNode, int num)
{
bool bVal = false;
Node * pTemp = *ppNode;
//If the node is head then the head has to be reset
if((*ppNode)->data == num)
{
pTemp = pTemp->Next;
pTemp->Prev = NULL;
delete(*ppNode);
*ppNode = pTemp;
bVal = true;
}
else
{
while(pTemp)
{
if(pTemp->data == num)
{
pTemp->Prev->Next = pTemp->Next;
pTemp->Next->Prev = pTemp->Prev ;
delete pTemp;
bVal = true;
return bVal;
}
pTemp = pTemp->Next;
}
}
return bVal;
}

void ReverseList(Node** ppNode)
{
if((*ppNode == NULL)||((*ppNode)->Next == NULL))
return;
//Use 2 more pointers
Node* pastNode = *ppNode, *currentNode = NULL;
*ppNode = (*ppNode)->Next;
pastNode->Next = NULL;

while(*ppNode)
{
currentNode = *ppNode;
*ppNode = (*ppNode)->Next;

// Insert node at the front of
// the temporary list
currentNode->Next = pastNode;
currentNode->Prev = NULL;
pastNode->Prev = currentNode;
pastNode = currentNode;
}

// Update head with the temporary
// list
*ppNode = pastNode;
}
int _tmain(int argc, _TCHAR* argv[])
{
Node * Head = NULL;
InsertNode(&Head,10);
InsertNode(&Head,20);
InsertNode(&Head,30);
InsertNode(&Head,40);
InsertNode(&Head,50);
InsertNode(&Head,55);
InsertNode(&Head,60);
Display(Head);
DeleteNode(&Head,10);
DeleteNode(&Head,55);
Display(Head);
ReverseList(&Head);
Display(Head);
return 0;
}

No comments: