Double Link List C++
 |
| Double Link List C++ |
Overview:
#pragma once
typedef int itemType;
#include <iostream>
using namespace std;
class Node
{
public:
itemType data;
Node *prev, *next;
};
List.h
#pragma once
#include "Node.h"
class doubleList
{
private:
Node *head;
void insertFirst(itemType
item);
void insertLast(itemType item);
void insertAfter(itemType
ov,itemType nv);
void deleteNode(itemType data);
void deleteAfter(itemType
ov);
void concate(Node* node1,
Node* node2);
void showReverse(Node* node);
};
List.cpp
#include "DoublyList.h"
doubleList::doubleList()
{
head = NULL;
}
bool doubleList::isEmpty()
{
if (head == NULL)
{
return true;
}
else
{
return false;
}
}
void doubleList::insertFirst(itemType item)
{
Node *n = new Node;
n->data = item;
n->prev = NULL;
if (isEmpty())
{
head = n;
n->next = NULL;
}
else
{
n->next = head;
head->prev = n;
head = n;
}
}
void doubleList::display()
{
if (isEmpty())
{
cout << "\nList Is
Empty\n";
}
else
{
Node *ptr = head;
while (ptr != NULL)
{
cout << ptr->data<<" <--> ";
ptr =
ptr->next;
}
}
cout << endl;
}
void doubleList::insertLast(itemType item)
{
Node *n = new Node;
n->data = item;
n->next = NULL;
if (isEmpty())
{
head = n;
n->prev = NULL;
}
else
{
Node *ptr = head;
while (ptr->next != NULL)
{
ptr =
ptr->next;
}
ptr->next = n;
n->prev = ptr;
}
}
void doubleList::insertAfter(itemType ov, itemType nv)
{
Node *n = new Node;
n->data = nv;
if (isEmpty())
{
cout << "\nList is
Empty\n";
}
else
{
Node *ptr = head;
while (ptr->next != NULL&&ptr->data!=ov)
{
ptr = ptr->next;
}
if (ptr->next == NULL)
{
n->prev = ptr;
n->next = NULL;
ptr->next = n;
return;
}
n->next =
ptr->next;
n->prev = ptr;
ptr->next->prev
= n;
ptr->next = n;
}
}
void doubleList::deleteFirst()
{
if (isEmpty())
{
cout << "\nList Can't
Delete\n";
}
else
{
Node *temp;
temp = head;
head = head->next;
head->prev = NULL;
delete temp;
}
}
void doubleList::deleteLast()
{
if (isEmpty())
{
cout << "\nList Can't
Delete\n";
}
else
{
Node *ptr = head;
while (ptr->next->next!= NULL)
{
ptr =
ptr->next;
}
Node *temp = ptr->next;
ptr->next->prev=
NULL;
ptr->next = NULL;
delete temp;
}
}
void doubleList::deleteAfter(itemType ov)
{
Node* ptr = head,*temp=NULL;
bool Found = true;
if (isEmpty() ||
head->next==NULL)
{
cout << "\nList Is Can't
Delete\n";
return;
}
else
{
while (ptr->next!= NULL)
{
Found = false;
if (ptr->data == ov)
{
temp =
ptr->next;
ptr->next
= temp->next;
ptr->next->prev
= ptr;
delete temp;
return;
}
ptr =
ptr->next;
}
if (ptr->data == ov)
cerr << "\nCan't
Delete\n\n"; return;
if (Found == false)
cerr << "\nData not
Found\n\n";
}
}
void doubleList::reverseDisplay()
{
Node *ptr = head;
while (ptr->next != NULL)
{
ptr = ptr->next;
}
while (ptr != NULL)
{
cout << ptr->data <<" <==> ";
ptr = ptr->prev;
}
cout << endl;
}
void doubleList::split()
{
Node* node1, *
node2,*endPtr=head,*breakPtr=head;
node1 = node2 = NULL;
int count = 1, nodeCount = 1,
totalNode = 0,list1=1;
while (endPtr->next != NULL)
{
endPtr =
endPtr->next;
count++;
}
totalNode = count;
if (count % 2 == 0)
count = count / 2;
else
count = ((count - 1)
/ 2) + 1;
cout << "\nTotal Node In
List: " << totalNode << endl;
cout << "\nTotal Node In
List 1: " << count << endl;
cout << "\nTotal Node In
List 2: " << totalNode-count << endl;
node1 = head;
while (breakPtr->next != NULL && list1 != count)
{
breakPtr =
breakPtr->next;
list1++;
}
node2 =
breakPtr->next;
breakPtr->next =
node2->prev = NULL;
cout << "\nList 1 \n";
this->show(node1);
cout << "\nList 2 \n";
this->show(node2);
cout << "\nList 1
Reverse\n";
this->showReverse(node1);
cout << "\nList 2
Reverse\n";
this->showReverse(node2);
cout << "\nSub-Split List
1\n";
this->subSplit(node1);
cout << "\nSub-Split List
2\n";
this->subSplit(node2);
cout << "\nConcate
List\n";
this->concate(node1, node2);
}
void doubleList::show(Node* node)
{
Node* dataPtr = node;
if (isEmpty())
cerr << "\nList is
Empty\n";
else
{
do
{
cout << dataPtr->data << " <--> ";
dataPtr =
dataPtr->next;
} while (dataPtr != NULL);
cout << "\n";
}
}
void doubleList::showReverse(Node* node)
{
Node *dataPtr = node;
if (isEmpty())
cout << "\nList is
Empty\n";
else
{
while (dataPtr->next != NULL)
dataPtr =
dataPtr->next;
do
{
cout << dataPtr->data << " <--> ";
dataPtr =
dataPtr->prev;
} while (dataPtr != NULL);
cout << "\n";
}
}
void doubleList::concate(Node* node1, Node* node2)
{
Node* endPtr = node1;
if (isEmpty())
cerr << "\nList is
Empty\n";
else
{
if (node1 == NULL)
this->show(node2);
else if (node2 == NULL)
this->show(node1);
else
{
while (endPtr->next != NULL)
endPtr =
endPtr->next;
endPtr->next =
node2;
node2->prev = endPtr;
this->show(node1);
}
}
}
void doubleList::deleteNode(itemType data)
{
Node* ptr = head,*temp=NULL;
if (isEmpty())
cerr << "\nList is
Empty\n";
else if (head->next == NULL&&head->data==data)
{
temp = head;
head = NULL;
delete temp;
return;
}
else if (head->data == data && head->next
!= NULL)
{
temp = head;
head = temp->next;
head->prev = NULL;
delete temp;
return;
}
else
{
while (ptr->next != NULL)
{
if (ptr->data == data)
{
temp = ptr;
ptr->prev->next
= temp->next;
temp->next->prev
= ptr->prev;
delete temp;
return;
}
ptr =
ptr->next;
}
if (ptr->data == data)
{
temp = ptr;
temp->prev->next
= NULL;
delete temp;
return;
}
}
}
void doubleList::subSplit(Node* node)
{
Node* node1, * node2, * endPtr
= node, * breakPtr = node;
node1 = node2 = NULL;
if (isEmpty())
cerr << "\nList is
Empty\n";
else
{
int count = 1, nodeCount = 1, totalNode
= 0, list1 = 1;
while (endPtr->next != NULL)
{
endPtr =
endPtr->next;
count++;
}
totalNode = count;
if (count % 2 == 0)
count = count /
2;
else
count = ((count -
1) / 2) + 1;
cout << "\nTotal Node In
List: " << totalNode << endl;
cout << "\nTotal Node In
List 1: " << count << endl;
cout << "\nTotal Node In
List 2: " << totalNode - count << endl;
node1 = node;
while (breakPtr->next != NULL && list1 != count)
{
breakPtr =
breakPtr->next;
list1++;
}
node2 =
breakPtr->next;
breakPtr->next = NULL;
node2->prev = NULL;
cout << "\nList 1 \n";
this->show(node1);
cout << "\nList 2 \n";
this->show(node2);
cout << "\nList 1
Reverse\n";
this->showReverse(node1);
cout << "\nList 2
Reverse\n";
this->showReverse(node2);
cout << "\nConcate
List\n";
this->concate(node1, node2);
}
}
Main.cpp
#include "DoublyList.h"
int main()
{
doubleList d;
d.insertFirst(5);
d.insertFirst(4);
d.insertFirst(3);
d.insertFirst(2);
d.insertFirst(1);
d.insertLast(6);
d.insertLast(7);
d.insertLast(8);
d.insertAfter(8, 9);
d.insertAfter(9, 10);
cout << "\nOrignal
List\n";
d.display();
cout << "\nReverse of
Orignal List\n";
d.reverseDisplay();
cout << "\nDelete Some
Node\n";
d.deleteFirst();
d.deleteLast();
d.deleteAfter(3);
d.display();
d.reverseDisplay();
cout << "\nSplit\n";
d.split();
system("pause");
}
output
 |
| Double Link List Example |
 |
| Double Link list Example |
0 Comments
Thanks