Adding node in front of linklist

Question

I have implemented linklist as below,

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

void initNode(node* head, int data)
{
    head->data = data;
    head->next = NULL;
}

void addNode(node* linkList, int data)
{
    node* newnode = new node;
    newnode->data = data;
    newnode->next = NULL;

    while (linkList)
    {
        if (linkList->next == NULL)
        {
            linkList->next = newnode;
            return;
        }
        linkList = linkList->next;
    }
}

void insertFrontNode(node* linkList, int data)
{
    node* newnode = new node;
    newnode->data = data;
    newnode->next = linkList;
    linkList = newnode;
}

void DisplayLinkList(struct node* linkList)
{
    int i = 1;
    while (linkList)
    {
        cout << "Linklist(" << i << ") " << linkList->data << endl;
        linkList = linkList->next;
        i++;
    }
}


int main()
{
    node* linkList  =new node;
    initNode(linkList, 5);
    addNode(linkList, 10);
    addNode(linkList, 30);
    insertFrontNode(linkList, 12);  
    DisplayLinkList(linkList);


    cin.get();
    return 0;
}

My question is, when i initialise linklist in initNode or add node in addNode, the changes are reflected in linkst pointer which i am passing thru argument. but If i am adding node infront in insertFrontNode, changes are not reflecting in the linklist pointer.

Why? and what is difference?

Answer 1

You are doing fine.You are modifying the head of your linked list but not updating it to your outer world.So when you are calling DisplayLinkList it is called with the old head pointer which is why the changes are not reflecting. Check the below code:

void insertFrontNode(node** linkList, int data)
{
    node* newnode = new node;
    newnode->data = data;
    newnode->next = *linkList;
    *linkList = newnode;
}

int main()
{
    node* linkList = new node;
    initNode(linkList, 5);
    addNode(linkList, 10);
    addNode(linkList, 30);
    insertFrontNode(&linkList, 12);
    DisplayLinkList(linkList);


    cin.get();
    return 0;
}

Above code,not only add the node at the front but also updates the head pointer such that display functions get the new updated head pointer.

Answer 2

You might find that adding a list (slist, single linked list) structure around your list will help (and make both add at head and add a tail O(1) operations).

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

struct slist
{
    node* head;
    node* tail;
};

void addHead(slist* linkList, int data)
{
    //new list node
    node* newnode = new node;
    newnode->data = data;
    newnode->next = NULL;

    newnode->next = linkList->head;
    linklist->head = newnode->next;
}

void addTail(slist* list, int data)
{
    //new list node
    node* newnode = new node;
    newnode->data = data;
    newnode->next = NULL;

    if( list->tail ) {
        list->tail->next = newnode;
    }
    list->tail = newnode;
}

void DisplayLinkList(struct slist* linkList)
{
    int i = 1;
    node* link = linklist->head;
    while (link)
    {
        cout << "Linklist(" << i << ") " << link->data << endl;
        link = link->next;
        i++;
    }
}

int main()
{
    slist* linkList=new slist;
    addTail(linkList, 5);
    addTail(linkList, 10);
    addTail(linkList, 30);
    addHead(linkList, 12);  
    DisplayLinkList(linkList);
    return 0;
}