Doubly Link List | Doubly Link List Functions | Top 15 Doubly Link List Functions

Double Link List C++

Overview:

Double link list complete code in C++,  all basic functions are defined here. A detailed Version will be upload soon.

 

Node.h

#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;

public:

doubleList();

bool isEmpty();

void insertFirst(itemType item);

void insertLast(itemType item);

void insertAfter(itemType ov,itemType nv);

void deleteNode(itemType data);

void deleteFirst();

void deleteLast();

void deleteAfter(itemType ov);

void display();

void reverseDisplay();

void split();

void subSplit(Node* node);

void concate(Node* node1, Node* node2);

void show(Node* node);

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