C++ linked list

I am looking for some reference on how to develop a source code in C++ to implement a linked list (of a set of numbers). The requirement also includes sorting the list in ascending order. Can anybody point me to some useful reference either online or in text book. Thanks a lot in advance.



Gina


Comments

  • : I am looking for some reference on how to develop a source code in C++ to implement a linked list (of a set of numbers). The requirement also includes sorting the list in ascending order. Can anybody point me to some useful reference either online or in text book. Thanks a lot in advance.

    :

    : Gina

    :



    first think about it, a linked list looks like

    this

    ob->next->next->next->NULL



    to insert and not sort we recursively serach each

    element till we get to the end like so



    void insert(int i)

    {

    if(next)

    next->insert(i);

    else { next = new LinkedList(i); //assuming the

    //constructor takes the data the list holds

    }

    This will result in

    LinkedList ll(some_val);

    ll->insert(5);



    ll->next->insert(5);

    ll->next->next->insert(5);

    ll->next->next->next->insert(5);

    considering this is the end

    ll->next->next->next->data = 5;

    //will be the result



    to sort we can look at an example



    ob_with_val(3)->ob_with_val(7)->NULL



    so its a linked list with length 2



    if we do insert (5)



    we are going to start at element one and say

    is the value of the next node greater than that

    of the value I need to insert



    if it is we need to put a new node in between

    the one where in, and the next one

    so the new nodes next will = the current nodes next

    it hard to show not in person but

    ob(5)->ob(9) and we want to insert 6

    we want to do this

    ob(5) -> ob(9)

    ob(5) -> ob(6) -> ob(9)

    we can do this with temp storage and hold next

    in a temp, make the next = new node, and

    make the new nodes next = the temp



    the code looks like this



    void insert(int i) {

    if(next) {

    if(next->data > i) { //considering data is

    //the stored number



    LinkedList temp = next; //store the next

    //so it can be reattached



    delete(next); //free up the memory



    next = new LinkedList(i); //put the

    //inserted value in its place

    next->next = temp; //and put the greater

    //previously stored value after it

    }

    else next->insert(i);

    //search this->next->next

    //because next is too small

    //so search val belong further down

    //***i bet your confused after that.***



    } //if(next) //there is no next node

    else next = new LinkedList(i); //its null so

    //put the value there

    }



    the only problem with this is that this wont take care of the fist value

    so we will have to find out which one is first



    we can do this with a static var



    static int pos_counter = 0;



    and in the constructor



    which looks like this



    LinkedList(int n) {

    next = NULL;

    data = n;

    pos = pos_counter++;

    }



    so the first element->pos will = 0;



    so we can say



    if(pos == 0 && i < data) { //it belongs here

    int temp_num = data; //meaning the beginning

    this->data = i; //i is the insert data

    insert(temp); //let insert find its spot

    }



    we also now have a tool to find the size



    from this if you can't make a linked list

    its probably because I make stuff really

    confusing, i've never seen this in any book either, data structures are easy to make if you just think about how it'll work, the most important tool in programming is the pencil and paper!!!

    and think of the pointer this as meaning



    this_node;

    so in a member function think of data

    as this_nodes->data



    also you'll need an assignement operator



    anways it'll look something like this

    class LinkedList {

    public:

    LinkedList(int i);

    ~LinkedList(){

    if(next) delete next; //forgot to mention

    //this

    }



    LinkedList operator=(LinkedList& ll);



    protected:

    LinkedList * next;



    int data; //or whatever, float, class Object

    //id make it a template but that would just

    //confuse things



    int pos;



    static int pos_counter;

    };



    and i probably forgot 50 things, but this should work.. :)










Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories