adding at the beginning of linked list!

[corbett]

I've been struggling with linked list for a few days. I've tried performing a few operations. Here is my code. the add_begin() function doesn't seem to work.
Could anyone help me with this.

#include<iostream>

using namespace std;

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

void PrintData(node*S)
{
    while(S!=NULL)
        {   cout<<S->data<<" ";
            S=S->next;
        }
}

void add_begin(node*S,int k)
{
    node*T;
    T=new (node);
    T->data=k;
    T->next=NULL;
    if (S!=NULL) T->next=S;
    S=T;
}



void add_af(node*S,int x, int y)
{
    node*T;
    while (S->data!=x)
        S=S->next;
    T=new(node);
    T->data=y;
    T->next=S->next;
    S->next=T;

}

void add_bef(node*S,int k, int l)
{
    node*T;
    while(S->next->data!=l)
        S=S->next;
    T=new(node);
    T->data=k;
    T->next=S->next;
    S->next=T;
}




void add_end(node*S,node*L,int k)
{
    L=S;
    while(L->next!=NULL)
        L=L->next;
    L->next=new(node);
    L->next->data=k;
    L->next->next=NULL;
}

int main()
{
    int d;
    node*L;
    node*S;
    node*T;
    L=new(node);
    S=new(node);
    cin>>d;
    L->data=d;
    L->next=NULL;
    S=L;
    cin>>d;
      //List Adding
    while(d!=-1)
    {
        T=new(node);
        T->data=d;
        T->next=NULL;
        L->next=T;
        L=T;

        cin>>d;
    }
    PrintData(S);

    cout<<endl;

    add_end(S,L,5);
    PrintData(S);
    add_begin(L,6);
    cout<<endl;
    PrintData(S);
    cout<<endl;
    add_af(S,2,3);
    PrintData(S);
    cout<<endl;
    add_bef(S,45,2);
    PrintData(S);
return 0;
}

[o1vk4iN6]

void add_begin(node*S,int k)
{
    node*T;
    T=new (node);
    T->data=k;
    T->next=NULL;
    if (S!=NULL) T->next=S;
    S=T;
}

You overwrite S with T, so trying to point T->next to S, it'll just be pointing to itself and the data of S is going to be lost as it's overwritten.

You'd need to use a double pointer so you can modify the pointer to the beginning of the list. Or you could create a new node and move the contents of S into it, then fill S with the data supplied (though this is more costly with 2 copies instead of just the one being added).

[LB]

xerzi wrote:

You'd need to use a double pointer

double *double_pointer;

[corbett]

where do i use a double pointer and how? could you write that part?

[o1vk4iN6]

double* pointer_to_double;
ftfy.

[LB]

By that logic you should say "pointer to pointer" and not "double pointer".

[o1vk4iN6]

Lol, L space B, you mad about something ? http://lmgtfy.com/?q=double+pointer


@corbett

You can think of it like this:

typedef Node* Ptr;

void add_begin(Ptr* headNode, int data);

// which is just

void add_begin(Node** headNode, int data);

I would really just create a class named LinkedList and put all the functions in there. Really it's actually what you are doing it just hides the pointer to itself with "this". It's a very C like way of doing it trying to simulate objects.

[LB]

I'm not mad, I'm disappointed.

[Smac89]

I believe this should suffice:

void add_begin( node *&S, const int& k)
{
    node *T(new node);
    T->data = k;
    T->next = S;
    S = T;
}

Or

node *add_begin( node *S, const int& k)
{
    node *T(new node);
    T->data = k;
    T->next = S;
    return T;
}

Or

void add_begin( node **S, const int& k)
{
    node *T(new node);
    T->data = k;
    T->next = *S;
    *S = T;
}