DEV Community

Divyanshu Singh
Divyanshu Singh

Posted on

doubly linked list- implementation, insertion(head and tail), printing, reverse printing and deletion

#include <iostream>
using namespace std;
struct Node
{
    int data;
    Node* next;
    Node* prev;
};
Node* head;
Node* GetNewNode(int x)
{
    Node* newNode = new Node();
    newNode->data = x;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}
void InsertAtHead(int x)
{
    Node* newNode = GetNewNode(x);
    if(head == NULL)
    {
        head = newNode;
        return;
    }
    head->prev = newNode;
    newNode->next = head;
    head = newNode;   
}
void InsertAtTail(int x)
{
    Node* newNode = GetNewNode(x);
    if(head == NULL)
    {
        head = newNode;
        return;
    }
    Node* temp = head;
    while(temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;

}
void print()
{
    Node* temp = head;
    while(temp != NULL)
    {
        cout<<temp-> data<<" ";
        temp = temp->next;
    }
    cout<<endl;
}
void reversePrint()
{
    Node* temp = head;
    while(temp->next != NULL)
    {
        temp = temp->next;
    }
    while(temp != NULL)
    {
        cout<<temp->data<<" ";
        temp = temp->prev;
    }
    cout<<endl;
}
void deleted(int pos)
{
    // Case 1: empty list
    if(head == NULL)
    {
        cout << "List is empty\n";
        return;
    }

    Node* temp = head;

    // Case 2: delete head
    if(pos == 1)
    {
        head = temp->next;

        if(head != NULL)
            head->prev = NULL;

        delete temp;
        return;
    }

    // Traverse to pos-th node
    for(int i = 1; i < pos; i++)
    {
        if(temp == NULL)
        {
            cout << "Invalid position\n";
            return;
        }
        temp = temp->next;
    }

    if(temp == NULL)
    {
        cout << "Invalid position\n";
        return;
    }

    // Re-link neighbors
    if(temp->prev != NULL)
        temp->prev->next = temp->next;

    if(temp->next != NULL)
        temp->next->prev = temp->prev;

    delete temp;
}
int main()
{
    head = NULL;
    InsertAtHead(1);
    InsertAtHead(2);
    InsertAtHead(3);
    print();
    reversePrint();
    InsertAtTail(4);
    InsertAtTail(5);
    InsertAtTail(6);
    print();
    reversePrint();
    deleted(2);
    print();
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)