Category: Linked List

Remove Duplicates from an Unsorted single linked list

void SLList::removeDuplicates()
{
    if(header)
    {
        Node *temp, *curChkNode, *last;
        temp=curChkNode=header;
        int curVal=0, length=0, counter=0;
        length=sllLength();
        cout<<"\nThe length of the list is:\t"<<length;
        while(counter!=length && curChkNode)
        {
            temp=curChkNode->next;
            curVal=curChkNode->data;
            while(temp)
            {
                if(curVal==temp->data)
                {
                    cout<<"\nA DUPLICATE IS PRESENT FOR:\t"<<curVal;
                    last->next=temp->next;
                }
                last=temp;
                temp=temp->next;
            }
            curChkNode=curChkNode->next;
            counter++;
        }   
    }
    else
    {
        cout<<"\nThe list is empty\n";
    }
    return;
}

Advertisement

Design a doubly linked list and perform the following operations: 1)Add nodes to both front and rear 2)Display the list, 3)Delete nodes at front.tail and nth position

#include

using namespace std;

class Node
{
    public:
    int data;
    Node *prev, *next;
    Node()
    {
        data=NULL;
        prev=NULL;
        next=NULL;
    }   
};

class dll
{
    private:
        Node *header;
    public:
        dll(){
            header=NULL;
        }
        void createList();
        void displayList();
        void insertEnd();
        void deleteFirstNode();
        void deleteLastNode();
        void deleteNthNode();
};

void dll::deleteFirstNode()
{
    if(header)
    {
        Node *temp;
        temp=header;
        header=temp->next;
        header->prev=NULL;
        delete temp;
    }
    else
    {cout<<"\nThe list is empty!\n";}
    return;
}

void dll::deleteLastNode()
{
    if(header)
    {
        Node *temp, *last;
        temp=header;
        while(temp)
        {
            last=temp;
            temp=temp->next;
        }
        last->prev->next=NULL;
        delete last;
        delete temp;       
    }
    else
    {cout<<"\nThe list is empty!\n";}
    return;
}

void dll::deleteNthNode()
{
    if(header)
    {
        Node *temp, *last;
        temp=header;
        int position=0, counter=0;
        cout<<"Enter the node position that you want to delete: \t";
        cin>>position;
        if(position>=0)
        {
            while(counter!=position && temp)
            {
                last=temp;           
                temp=temp->next;
                counter++;
            }
            if(temp)
            {
            cout<<"\nThe node that you want to delete has value:\t\n"<data;
            last->prev->next=temp;
            temp->prev=last->prev;
            delete last;           
            }
            else{cout<<"\nThe list does not contain that many elements\n";}
        }
    }
    return;
}

void dll::insertEnd()
{
    if(header==NULL)
    {
        createList();
    }
    else
    {
        Node *newNode, *temp, *last;
        newNode=new Node;
        cout<<"Enter the value for the node:\t";
        cin>>newNode->data;
        temp=header;
        while(temp)
        {
            last=temp;
            temp=temp->next;
        }
        newNode->next=NULL; //newNode is the new last node
        newNode->prev=last;
        newNode->prev->next=newNode;           
    }
    return;
}

void dll::createList()
{
    int in_val;
    Node *temp;
    temp=new Node;
    cout<<"Enter the value for the node:\t";
    cin>>temp->data;
    if(header == NULL)
    {
        //This is the first node in the double linked list
        temp->next=NULL;
        temp->prev=NULL;       
    }
    else
    {
        //If this is a new node at the front of an already populated linkedlist
        temp->next=header;
        temp->next->prev=temp;
        header=temp;
    }
    header=temp;
    return;
}

void dll::displayList()
{
    Node *temp, *last;
    temp=header;
    cout<<"Display the list from first to last using the NEXT pointer.\n";
    while(temp)
    {   
        cout<data<<"\t"<<endl;
        last=temp;
        temp=temp->next;
    }
    /*if(last)
    {
        cout<<"Display the list from last to last using the PREV pointer.\n";
        while(last)
        {
            cout<data<<"\t"<<endl;
            last=last->prev;       
        }
    }*/
}

void main()
{
    cout<<"******This is a Doubly Linked List Demo******"<<endl;
    int choice=0;
    dll objDLL;
    do{
        cout<<"Enter the opration you want to perform: ";
        cout<<"\n1). Add a node at front of the list";
        cout<<"\n2). Display a node";
        cout<<"\n3). Add a node at end of the list";
        cout<<"\n4). Delete the node at head of the list";
        cout<<"\n5). Delete the node at tail of the list";
        cout<<"\n6). Delete the node at nth position of the list";
        cout<<"\n7). Exit\t";
    cin>>choice;
    switch(choice)
    {
        case 1: objDLL.createList(); break;
        case 2: objDLL.displayList(); break;
        case 3: objDLL.insertEnd(); break;
        case 4: objDLL.deleteFirstNode();break;
        case 5: objDLL.deleteLastNode();break;
        case 6: objDLL.deleteNthNode();break;
        case 7: exit(0);
        default: cout<<"\n Invalid operation/input detected. Please try again later.";
    }   
    }while(choice!=7);
}   

Creating a Stack using Linked List.

The operations to be supported:

1. PUSH

2. POP

3. Check if Empty

4. Check if Full

//I have just created the skeleton. Exception handling is not put in yet.

#include
using namespace std;

class stack
{
    public:
        stack();
        ~stack();
        void Push(int inData);
        int Pop();
        void display();
        bool IsEmpty();
    protected:
        typedef struct nodeT
        {
            int data;
            struct nodeT *next;   
        }node;
        node *firstElement;
};

//Class method implementation now
stack::stack()
{
    firstElement = NULL;
    return;
}

stack::~stack()
{
    node *next;
    while(firstElement)
    {
        next=firstElement->next;
        delete firstElement;
        firstElement=firstElement->next;
    }
    return;
}

void stack::Push(int inData)
{
    node *newNode = new node;
    newNode->data=inData;
    newNode->next=firstElement;
    firstElement = newNode;
    return;   
}

//Note that the Pop operation is intended to return the data stored in the top most node and free

//that space in the stack
int stack::Pop()
{
    node *nodeToPop;
    int data;
    nodeToPop=firstElement;
    firstElement=firstElement->next;
    data=nodeToPop->data;
    delete nodeToPop;
    return data;
}

bool stack::IsEmpty()
{
    if(!firstElement) return 1;
    else return 0;
}

void stack::display()
{
    node *ptr;
    ptr=firstElement;
    if(ptr)
    {
        cout<<"The stack elements are: "<<endl;
        while(ptr)
        {
            cout<data<<endl;
            ptr=ptr->next;
        }   
    }
    else
    {
        cout<<"There are no elements in the stack!!!!"<<endl;
    }
}

void main()
{
    stack objStack;
    int indata=0, choice=1;
    while(choice!=0)
    {
        cout<<"Stack Operations Main Menu: 1.Push 2.Pop    3.IsEmpty 4.IsFull 0.Exit"        

<<endl;
        cin>>choice;
        switch(choice)
        {
            case 0:
                exit(1); //Normal program Termination
            case 1:
                cout<<"Enter the number to Push: ";   
                cin>>indata;
                objStack.Push(indata);
                break;
            case 2:
                if(!objStack.IsEmpty())
                {
                cout<<"The number popped from the stack is: "<<objStack.Pop()       

            <<endl;
                }
                else {cout<<"Cannot pop from an empty stack!!!"<<endl;}
                break;
            case 3:
                cout<<"Checking if the stack is empty…";
                if(objStack.IsEmpty())
                {
                    cout<<"The stack is empty."<<endl;
                }
                else
                {
                    cout<<"The stack is not empty"<<endl;;
                }
                break;
            case 4:
                //TO Do
            default:
                cout<<"Illegal Action. Please try again!!!"<<endl;
        }
        objStack.display();
        cin.get();
    }   
}

Create/Delete/Insert – Single Linked List

#include

using namespace std;

struct node{int data; struct node *next;};

struct node* createlist()
{
    node *temp, *firstNodePtr, *last;
    int intNumOfNodes=0;
    firstNodePtr = (node*)malloc(sizeof(node));
    temp=firstNodePtr;
    cout<<"Enter the number of nodes you want in the list: ";
    cin>>intNumOfNodes;
    if(intNumOfNodes!=0)
    {
        while(intNumOfNodes!=0)
        {
            temp->next = (node*)malloc(sizeof(node));
            cin>>temp->data;
            last=temp;
            temp=temp->next;
            intNumOfNodes–;
        }
        last->next=NULL;
        delete(temp);       
    }
    else
    {
        firstNodePtr = NULL;
    }
    return(firstNodePtr);
}

void display(struct node *header)
{
    node *ptr = header;
    cout<<endl<<"The list is: " ;
    while(ptr !=NULL)
    {
        cout<data<<" ";
        ptr=ptr->next;
    }
}

void deleteHeader(struct node **ptrHeader)
{
    node *current,*temp;
    current=*ptrHeader;
    temp=current->next;
    *ptrHeader = temp;
    current=NULL;
    display(*ptrHeader);           
}

void deleteTail(struct node **ptrHeader)
{
    node *last, *temp;
    temp=*ptrHeader;
    while(temp->next)
    {
        last=temp;
        temp=temp->next;
    }
    last->next=NULL;
    temp=NULL;
    display(*ptrHeader);   
}

void deleteANode(struct node **header, char choice)
{
    if(choice == ‘h’)
    {
        cout<<"You have chosen to delete the header node!!!"<<endl;
        deleteHeader(header);
    }
    else if(choice == ‘l’)
    {
        cout<<"You have chosen to delete the last node!!!"<<endl;
        deleteTail(header);
    }
    else
    {
        node *temp, *last;
        int counter=0, intPos=0;
        temp=*header;
        cout<<"Enter the position of the node that you want to delete."<<endl;
        cin>>intPos;
        while(counter!=intPos)
        {
            last=temp;
            temp=temp->next;
            counter++;
        }   
        last->next = temp->next;
        delete(temp);
        display(*header);       
    }
}

void main()
{
    node *headerPtr;
    node **ptrHeaderPtr;
    char choice;
    headerPtr = createlist();
    if(headerPtr)
    {
        ptrHeaderPtr = &headerPtr;
        display(headerPtr);
        cout<<"Which node do you want to delete? (h/p/l): ";
        cin>>choice;
        deleteANode(ptrHeaderPtr, choice);
        //display(headerPtr);
    }
    else {cout<<"You enterd a 0 value for list size. Exiting…";}
}

Find the nth Element from last in a linked list.

/*
Find the nth Element from last in a linked list.
*/

#include

using namespace std;

struct node{int data; struct node *next;};

struct node* createlist()
{
    node *nodeHolder,*pointerToTheFirstNode, *temp;

    int elementCount=0;
    pointerToTheFirstNode = (node*)malloc(sizeof(node));
    temp=pointerToTheFirstNode;
    cout<<"Enter the number of elements you want in the list:    ";
    cin>>elementCount;
    cout<<endl;

    while(elementCount!=0)
    {
    temp->next=(node*)malloc(sizeof(node));
    cout<<"Enter the elements for the nodes:    ";
    cin>>temp->data;
    nodeHolder=temp;   
    temp=temp->next;
    elementCount–;
    }
    nodeHolder->next =NULL;
    free(temp);
    return pointerToTheFirstNode;
}

void display(struct node *headerPointer)
{

    node *ptr;
    ptr = headerPointer;
    cout<<endl<<"The list that we just created is:    ";
    while(ptr!=NULL)
    {
        cout<data<<" ";
        ptr=ptr->next;
    }
    cout<<endl;
}

int lenlist(struct node *header)
{
    node *ptr;
    int len=0;
    ptr=header;
    while(ptr!=NULL)
    {
        len=len+1;
        ptr=ptr->next;
    };
    return len;
}

void findElementFromLast(struct node *header, int intPos)
{
    node *ptr;
    ptr=header;
    int matchPos=0;
    int listLen = lenlist(ptr);
    cout<<"The length of the list is:    "<<listLen<<endl;
    cout<<"The element that is at "<< intPos <<" from the last node will be at "<<listLen-intPos<< " from the first node."<<endl;

    while(ptr!=NULL)
    {
        matchPos=matchPos+1;
        if(matchPos ==     (listLen-intPos))
        {
            cout<<"The value of the node that is at "<< intPos <<"th position from last is: "<data;
        }
        ptr=ptr->next    ;
    }
}

void main()
{
    node *header;
    int intPosFromLast=0;

    header=createlist();
    display(header);

    cout<<"Enter the position element that you want to find in the list we just created:    ";
    cin>>intPosFromLast;
    findElementFromLast(header,intPosFromLast);
}

Find the nth Element in a linked list.

/*
Find the nth Element in a linked list.
*/

#include

using namespace std;

struct node{int data; struct node *next;};

struct node* createlist()
{
    node *nodeHolder,*pointerToTheFirstNode, *temp;

    int elementCount=0;
    pointerToTheFirstNode = (node*)malloc(sizeof(node));
    temp=pointerToTheFirstNode;
    cout<<"Enter the number of elements you want in the list:    ";
    cin>>elementCount;
    cout<<endl;

    while(elementCount!=0)
    {
    temp->next=(node*)malloc(sizeof(node));
    cout<<"Enter the elements for the nodes:    ";
    cin>>temp->data;
    nodeHolder=temp;   
    temp=temp->next;
    elementCount–;
    }
    nodeHolder->next =NULL;
    free(temp);
    return pointerToTheFirstNode;
}

void display(struct node *headerPointer)
{

    node *ptr;
    ptr = headerPointer;
    while(ptr!=NULL)
    {
        cout<data<<" ";
        ptr=ptr->next;
    }
    cout<<endl;
}

void findElement(struct node *header, int intPos)
{
    node *ptr;
    int matchPos=0;
    ptr=header;
    while(ptr!=NULL)
    {
        matchPos=matchPos+1;
        if(matchPos == intPos)
        {
            cout<<"The value at the node at position "<< intPos << " is: "<data;
        }
        ptr=ptr->next    ;
    }
}

void main()
{
    node *header;
    int intPos=0;

    header=createlist();
    display(header);

    cout<<"Enter the position element that you want to find in the list we just created:    ";
    cin>>intPos;
    findElement(header,intPos);
}

Write a function to reverse a linked list.

/*
    Write a function to reverse a linked list. No double pointers please.
*/

#include

using namespace std;

struct node{int data; struct node *next;};

struct node* createlist()
{
    int counter=0;
    node *first, *temp, *last;
    first = (node*)malloc(sizeof(node));
    temp=first;
    cin>>temp->data;
    cout<<"Please enter the number of elements in the list that you want:    ";
    cin>>counter;
    while(counter!=0)
    {
    temp->next=(node*)malloc(sizeof(node));
    cout<<"Enter node data:    ";
    cin>>temp->data;
    last=temp;
    temp=temp->next;
    counter–;
    }
    last->next =NULL;
    delete(temp);
    return first;
}

void display(struct node *header)
{
    node *ptr;
    ptr=header;
    cout<<"The list now looks like:    ";
    while(ptr!=NULL)
    {
        cout<data<<"    ";
        ptr=ptr->next;
    }
    cout<<endl;
}

int lenlist(struct node *header)
{
    node *ptr;
    int len=0;
    ptr=header;
    while(ptr->next!=NULL)
    {
        len=len+1;
        ptr=ptr->next;
    };
    return len;
}
struct node* reverselist(struct node *header)
{
    int counter=5, tempHolder=0;
    node *temp, *ptr,*prev, *last;
    prev=NULL;
    ptr=header;
    //Obtain the length of the linked list
    counter=lenlist(header);
    while(counter!=0)
    {
        while(ptr->next!=NULL && ptr!=last)
        {
            if(ptr!=NULL)
            {
                tempHolder=ptr->data;
                ptr->data=(ptr->next)->data;
                (ptr->next)->data=tempHolder;
                prev=ptr;
            }
            else
            {
                cout<<"IF YOU SEE THIS, THE CODE IS FAULTY. The value of ptr is NULL for counter value "<<counter<<endl;
            }
            ptr=ptr->next;
        };
        ptr=header;
        last=prev;
        counter–;
    }
    return header;       
}

void main()
{
    node *header, *latest;
    node *header1;
    header=createlist();
    display(header);
    latest=reverselist(header);   
    display(latest);
}

Linked list problems

/*
You have two “set” of numbers represented by “two” linked lists, where each node contains a single digit.
Write a function that adds the two numbers “in the corresponding nodes” and returns the sum as a “third” linked list

*/

#include
using namespace std;

struct node{int data;struct node *next;};

void display(struct node *header)
{
    cout<<endl;
    node *ptr;
    ptr=header;
    cout<<"The list is:    ";
    while(ptr!=NULL)
    {
        cout<data<<"    ";
        ptr=ptr->next;
    }
}

struct node* createlist()
{
    int counter=0;
    node *first, *last, *temp;
    first= (node*)malloc(sizeof(node));
    temp=first;

    cout<<"Enter the number of elements:    ";
    cin>>counter;
    while(counter!=0)
    {
        temp->next=(node*)malloc(sizeof(node));
        cout<<"The node data is:    ";
        cin>>temp->data;
        last=temp;
        temp=temp->next;       
        counter–;
    }
        last->next=NULL;
        return first;
}

struct node* createlist(node *pointer3,int nodevalue)
{
    node *ptr;
    ptr=pointer3;
    if(ptr==NULL)
    {
        node *temp;
        temp=(node*)malloc(sizeof(node));
        temp->data=nodevalue;
        return temp;
    }
    else
    {
        node *last;
        last=pointer3;
        pointer3->next=(node*)malloc(sizeof(node));
        pointer3=pointer3->next;
        pointer3->data=nodevalue;
        return pointer3;
    }   
}

struct node* addlinkedlist(struct node *header1, struct node *header2)
{
    cout<<endl;
    node *firstlist,*secondlist, *pointer3, *baseptr;

    firstlist=header1;
    secondlist=header2;
    pointer3 = NULL;   

    while(firstlist !=NULL && secondlist !=NULL)
    {

        if(pointer3==NULL)
        {
            baseptr = createlist(pointer3,firstlist->data    + secondlist->data);
            pointer3=baseptr;
        }
        else   
        {
            pointer3 = createlist(pointer3,firstlist->data    + secondlist->data);           
        }

        secondlist=secondlist->next;
        firstlist= firstlist->next;
    }
    return baseptr;
}

void main()
{
    cout<<"You have two set of numbers represented by two linked lists, where each node contains a single digit.";
    cout<<"Write a function that adds the two numbers in the corresponding nodes and returns the sum as a third linked list";
    node *header1, *header2, *header3;
    header1 = createlist();
    header2=createlist();
    display(header1);
    display(header2);
    header3= addlinkedlist(header1, header2);
    display(header3);   
}