top button
Flag Notify
Site Registration

How to create duplicate of each node of a LinkList?

+1 vote
445 views

I have the following code of LinkList and want to add the following two functions, please help me.
removeTwoByTwoegg // Remove two head and two tails nodes
duplicateEachNode // This is make A->B->C to A->A->B->B->C->C

#include <iostream>

using namespace std;

struct nodeType
{
    int info;
    nodeType *next;
};

class linkedListType
{
public:
    linkedListType();
    int listSize();
    bool isEmpty();
    int seqSearch(int);
    void remove(int);
    void insertFirst(int);
    void insertEnd(int);
    void insertAt(int, int);
    void removeAt(int);
    void print();
    void clearList();
    void insertOrdered(int);
    void removeFirst();
    void removeLast();
    void removeLast2();
    int removeOddSumEven();
     ~linkedListType();  

private:
    nodeType *first, *last;
    int length;
};

// This function assumes that the list is NOT empty and first and last elements are NOT odd
int linkedListType::removeOddSumEven()
{
    int sum = first->info;
    nodeType *current = first->next;
    nodeType *trailCurrent = first;

    while(current != NULL)
    {
        if(current->info % 2 == 0)
        {
            sum += current->info;
            trailCurrent = current;
            current = current->next;
        }
        else
        {
            trailCurrent->next = current->next;
            delete current;
            length--;
            current = trailCurrent->next;
        }
    }
    return sum;
}

void linkedListType::removeLast()
{
    if(length == 0)
        cout<<"ERROR: EMPTY LIST" << endl;
    else if(length == 1)
    {
            delete first;
            last = first = NULL;
            length--;
    }
    else
    {
        nodeType *current = first->next;
        nodeType *trailCurrent = first;
        while(current != last)
        {
            trailCurrent = current;
            current = current->next;
        }
        delete current;
        trailCurrent->next = NULL;
        last = trailCurrent;
        length--;
    }
}

void linkedListType::removeLast2()
{
    if(length == 0)
        cout<<"ERROR: EMPTY LIST" << endl;
    else if(length == 1)
    {
            delete first;
            last = first = NULL;
            length--;
    }
    else
    {
        nodeType *current = first;
        while(current->next != last)
            current = current->next;

        delete last;
        current->next = NULL;
        last = current;
        length--;
    }
}

void linkedListType::removeFirst()
{
    if(length == 0)
        cout<<"ERROR: EMPTY LIST" << endl;
    else if(length == 1)
    {
            delete first;
            last = first = NULL;
            length--;
    }
    else
    {
        nodeType *current = first;
        first = first->next;
        delete current;
        length--;
    }
}

linkedListType::linkedListType()
{
    first = last = NULL;
    length = 0;
}

int linkedListType::listSize()
{
    return length;
}

bool linkedListType::isEmpty()
{
    return (length == 0);
}

int linkedListType::seqSearch(int item)
{
    nodeType *current = first;
    int loc = 0;
    while(current != NULL)
    {
        if(current->info == item)
            return loc;
        current = current->next;
        loc++;
    }
    return -1;
}

void linkedListType::remove(int item)
{
    if(isEmpty())
    {
        cout<<"Can not remove from empty list\n";
        return;
    }

    nodeType *current, *trailCurrent;
    if(first->info == item)//delete the first element, special case
    {
        current = first;
        first = first->next;
        delete current;
        length--;
        if(length == 0)
            last = NULL;
    }
    else
    {
        current = first->next;
        trailCurrent = first;
        while(current != NULL)
        {
            if(current->info == item)
                break;
            trailCurrent = current;
            current = current->next;
        }

        if(current == NULL)
            cout<<"The item is not there\n";
        else
        {
            trailCurrent->next = current->next;
            if(last == current) //delete the last item
                last = trailCurrent;
            delete current;
            length--;
        }
    }
}

void linkedListType::insertFirst(int item)
{
    nodeType *newNode = new nodeType;
    newNode->info = item;
    if(length == 0){
        first = last = newNode;
        newNode->next = NULL;
    }
    else{
        newNode->next = first;
        first = newNode;
    }
    length++;
}

void linkedListType::insertEnd(int item)
{
    nodeType *newNode = new nodeType;
    newNode->info = item;
    if(length == 0){
        first = last = newNode;
        newNode->next = NULL;
    }
    else{
        last->next = newNode;
        newNode->next = NULL;
        last = newNode;
    }
    length++;
}

void linkedListType::insertAt(int loc, int item)
{
    if(loc < 0 || loc > length)
        cout<< "ERROR: Out of range" << endl;
    else
    {
        nodeType *newNode = new nodeType;
        newNode->info = item;
        if (loc == 0) //insert at the begining
            insertFirst(item);
        else if (loc == length) //insert at the end;
            insertEnd(item);
        else
        {
            nodeType *current = first;
            for(int i = 1; i < loc; i++)
                current = current->next;
            newNode->next = current->next;
            current->next = newNode;    
            length++;
        }

    }
}

void linkedListType::removeAt(int loc)
{
    if(loc < 0 || loc >= length)
        cout<< "ERROR: Out of range" << endl;
    else
    {
        nodeType *current, *trailCurrent;
        if(loc == 0) //remove the first item
        {
            current = first;
            first = first->next;
            delete current;
            length--;
            if(length == 0)
                last = NULL;
        }
        else
        {
            current = first->next;
            trailCurrent = first;
            for(int i = 1; i < loc; i++)
            {
                trailCurrent = current;
                current = current->next;
            }

            trailCurrent->next = current->next;
            if(last == current) //delete the last item
                last = trailCurrent;
            delete current;
            length--;
        }
    }
}


void linkedListType::print()
{
    nodeType *current = first;
    while(current != NULL)
    {
        cout<<current->info <<endl;
        current= current->next;
    }
}

void linkedListType::clearList()
{
    nodeType *current;
    while(first != NULL)
    {
        current = first;
        first = first->next;
        delete current;
    }
    last = NULL;
    length = 0;
}

void linkedListType::insertOrdered(int item)
{
    nodeType *newNode = new nodeType;
    newNode->info = item;

    if(first == NULL)
    {
        first = last = newNode;
        newNode->next = NULL;
        length++;
    }
    else if(first->info >= item)
    {
        newNode->next = first;
        first = newNode;
        length++;
    }
    else
    {
        nodeType *current = first->next;
        nodeType *trailCurrent = first;

        while(current != NULL)
        {
            if(current->info >= item)
                break;      
            current = current->next;
            trailCurrent = trailCurrent->next;
        }
        if(current == NULL) //insert at the end
        {
            last->next = newNode;
            newNode->next = NULL;
            last = newNode;
            length++;
        }
        else
        {
            trailCurrent->next = newNode;
            newNode->next = current;
            length++;
        }
    }
}

linkedListType::~linkedListType()
{
    clearList();
}

int main()
{
    linkedListType l1;

    l1.insertAt(0, 10);
    l1.insertAt(1, 1);
    l1.insertAt(2, 3);
    l1.insertAt(3, 40);

    l1.print();

    return 0;
}
posted Nov 3, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
It just have some code, not sure what you want to ask what is your problem. Please explain what is your problem so that people should be able to help you.
Modify the linkedListType class you already studied by adding the following member functions to it (so here you are a class developer):

void removeTwoByTwoegg; // this function removes the first two nodes and the last two nodes from the linked list. Be warned that the list has to have AT LEAST 4 nodes in order for this function to execute.

void duplicateEachNode(); // this function duplicates each node on the linked list.
But what is the problem which you are facing, not able to understand your issue.
i want to add this function (   
Modify the linkedListType class you already studied by adding the following member functions to it (so here you are a class developer):

void removeTwoByTwoegg; // this function removes the first two nodes and the last two nodes from the linked list. Be warned that the list has to have AT LEAST 4 nodes in order for this function to execute.

void duplicateEachNode(); // this function duplicates each node on the linked list.(


to Previous code if you can help me to solve it !!!!
OK I got it you want to add two function
removeTwoByTwoegg // Remove two head and two tails nodes
duplicateEachNode     // This is make A->B->C to A->A->B->B->C->C

Please confirm

1 Answer

0 votes

Done limited testing

void linkedListType::duplicateEachNode()
{
    nodeType *current = first;
    nodeType *prev = first;

    while(current != NULL)
    {
        nodeType *newNode = new nodeType;
        current = current->next;
        newNode->info = prev->info;
        prev->next    = newNode;
        newNode->next       = current;
        prev = current;
        length++;
    }
}

void linkedListType::removeTwoByTwo()
{        
  if (length >=4)
  {
    removeLast2();
    removeFirst();
    removeFirst();
  }
}
answer Nov 4, 2013 by Salil Agrawal
why there are no effect in output when we add this function ?!
It works perfect for me, my main function
int main()
{
    linkedListType l1;

    l1.insertAt(0, 10);
    l1.insertAt(1, 1);
    l1.insertAt(2, 3);
    l1.insertAt(3, 40);

    l1.print();
    l1.duplicateEachNode();
    l1.print();
    l1.removeTwoByTwo();
    l1.print();
    return 0;
}

Output
10
1
3
40

10
10
1
1
3
3
40
40

1
1
3
3
really .. thank you very much .. grateful for you :)
Similar Questions
+2 votes

You have a binary tree which consists of 0 or 1 in the way, that each node value is a LOGICAL AND between its children:

      0
   /    \
  0      1
 / \    / \
0   1  1   1

You need to write a code, which will invert given LEAF and put tree in a correct state.

Note: Received by some user over whatsapp, sharing in exact form?

+2 votes

In linux system how can I implement a linklist to communicate between two processes?

...