Answer to Question #265015 in C++ for ZAIN

Question

Question #261249

Using the node from task 2, implement a class called DLL with following functionalities

1. insert a node at first ,

2. overload to Insert a node at last

3. overload to Insert at specified position of double linked list. E.g if the position number is 6, it is inserted between node at position 5 and 7. If position number is greater than the size of list.

1.      eliminate duplicates from doubly linked list

2.      delete a node from first,

3.      overload to delete a node from last

4.      overload to delete at specified position of double linked list. E.g if the position number is 6, it is deleted from between node at position 5 and 7. If position number is greater than the size of list, it is prompted that the position number does not exist and therefore is being deleted from the end.

5.      Make a sub menu to Merge 2 doubly list. Let there be 2 lists L1, L2

a.      Press 1 to append L1 to L2.

b.      Press 2 to append L2 to L1.

c.      Press 3 to merge L1 and L2 in sorted order.

Answer 1

#include<iostream>
#include<algorithm>
using namespace std;

struct Node
{
	int data;
	struct Node *prev;
	struct Node *next;
	Node(int _data) :data(_data), prev(NULL), next(NULL) {}
};


class DLL
{


	Node *Head;
	Node *Tail;
	int sizeList;
public:
	DLL() :Head(NULL), Tail(NULL), sizeList(0) {}
	void Insert(int value)
	{
		struct Node *p = new Node(value);
		if (sizeList == 1)
		{
			p->next = Head;
			Head->prev = p;
			Tail = Head;
			Head = p;
		}
		else if (Head != 0)
		{
			p->next = Head;
			Head->prev = p;
			Head = p;
		}
		else
		{
			p->next = Head;
			Head = Tail = p;
		}
		sizeList++;
	}
	void Delete()
	{
		struct Node *p = Head;
		Head = p->next;
		delete p;
		sizeList--;
	}
	void Insert(int value, struct Node *root)
	{
		struct Node *p = new Node(value);
		if (Head != 0)
		{
			p->prev = Tail;
			Tail->next = p;
			Tail = p;
		}
		else
		{
			p->prev = NULL;
			Head = Tail = p;
		}
		sizeList++;
	}
	void Delete(struct Node *root)
	{
		struct Node *p = Tail;
		Tail = p->prev;
		delete p;
		sizeList--;
	}
	void Insert(int value, int pos)
	{
		struct Node *p = new Node(value);
		if (pos >= sizeList)
		{
			if (Head != 0)
			{
				p->prev = Tail;
				Tail->next = p;
				Tail = p;
			}
			else
			{
				p->prev = NULL;
				Head = Tail = p;
			}
		}
		else
		{
			int i = 1;
			struct Node *t = Head;
			while (i != pos)
			{
				i++;
				t = t->next;
			}
			p->next = t->next;
			t->next->prev = p;
			t->next = p;
		}
		sizeList++;
	}


	void Delete(int pos)
	{
		if (pos >= sizeList)
		{
			struct Node *p = Tail;
			Tail = p->prev;
			delete p;
		}
		else
		{
			int i = 1;
			struct Node *p = Head;
			while (i != pos)
			{
				i++;
				p = p->next;
			}
			p->prev->next = p->next;
			p->next->prev = p->prev;
			delete p;
		}
		sizeList--;
	}


	void DeleteDup()
	{
		if (Head == NULL || Head->next == NULL)return;
		
		struct Node *p , *p2;
		for (p = Head; p != NULL; p = p->next)
		{
			p2 = p->next;
			while (p2 != NULL)
			{
				if (p->data == p2->data)
				{
					struct Node *next = p2->next;
					if (Head == p2)Head = p2->next;
					if (p2->next != NULL)p2->next->prev = p2->prev;
					if (p2->prev != NULL)p2->prev->next = p2->next;
					delete p2;
					sizeList--;
					p2 = next;
				}
				else
					p2 = p2->next;
			}
		}
	}
	void Display()
	{
		struct Node *p = Head;
		int i = 0;
		while (i<sizeList)
		{
			cout << p->data << " ";
			p = p->next;
			i++;
		}
	}
	void MergeDLL(const DLL &dll)
	{
		Tail->next = dll.Head;
		dll.Head->prev = Tail;
		Tail = dll.Tail;
		sizeList += dll.sizeList;
	}
	void sortDLL()
	{
		int swapped, i;
		struct Node *p;
		struct Node* lptr = NULL;
		if (Head == NULL)return;
		do
		{
			swapped = 0;
			p = Head;
			while (p->next != lptr)
			{
				if (p->data > p->next->data)
				{
					swap(p->data, p->next->data);
					swapped = 1;
				}
				p = p->next;
			}
			lptr = p;
		} while (swapped);
	}
};


void Menu()
{
	cout << "\nPress 1 to append L1 to L2"
		<< "\nPress 2 to append L2 to L1"
		<< "\nPress 3 to merge L1 and L2 in sorted order"
		<< "\nPress 0 to exit"
		<< "\nYour choice: ";
}
int main()
{
	struct Node *root = NULL;
	DLL dl;
	cout << "Insert at first:\n ";
	dl.Insert(1);
	dl.Insert(4);
	dl.Insert(8);
	dl.Insert(5);
	dl.Display();
	cout << endl;
	cout << "Insert at last:\n ";
	dl.Insert(56, root);
	dl.Display();
	cout << endl;
	cout << "Insert at position greater than size:\n ";
	dl.Insert(90, 11);
	dl.Display();
	cout << endl;
	cout << "Insert 7 at existent position 2:\n ";
	dl.Insert(7, 2);
	dl.Display();
	cout << endl;
	cout << "Delete from head:\n ";
	dl.Delete();
	dl.Display();
	cout << endl;
	cout << "Delete from last:\n ";
	dl.Delete(root);
	dl.Display();
	cout << endl;
	cout << "Delete from pos greater than size:\n ";
	dl.Delete(20);
	dl.Display();
	cout << endl;
	cout << "Make duplicate 1 and 4 at list:\n ";
	dl.Insert(4);
	dl.Insert(1, root);
	dl.Display();
	cout << endl;
	cout << "Delete duplicate from list:\n ";
	dl.DeleteDup();
	dl.Display();
	DLL L1, L2;
	L1.Insert(2);
	L1.Insert(7);
	L1.Insert(11);
	L1.Insert(89);
	L1.Insert(3);
	L2.Insert(6);
	L2.Insert(4);
	L2.Insert(55);
	L2.Insert(14);
	cout << "\nTwo lists:\n";
	L1.Display();
	cout << endl;
	L2.Display();
	int num;
	Menu();
	cin >> num;
	switch (num)
	{
		case 1:
			L2.MergeDLL(L1);
			L2.Display();
			break;
		case 2:
			L1.MergeDLL(L2);
			L1.Display();
			break;
		case 3:
			L1.sortDLL();
			cout << "\nL1 after sort:\n ";
			L1.Display();
			L2.sortDLL();
			cout << "\nL2 after sort:\n ";
			L2.Display();
			break;
	}
}