linked list program in c++

Discussion in 'C++' started by Indraseena, Jan 30, 2006.

  1. Indraseena

    Indraseena Guest

    Hi can anybody send me how to create a linked list program in C++.
    Basically I want to know how a node is handled in c++. I know this in c
    only.

    in c we create a structure and use that structure for ctreating nodes.
    how is this achieved in c++ .

    my c structure is:

    struct node
    {
    int info;
    struct node *link;
    };

    please tell me how do we do this in c++.

    Rgrds
    Indra
     
    Indraseena, Jan 30, 2006
    #1
    1. Advertising

  2. Indraseena

    Dakka Guest

    Indraseena wrote:
    > Hi can anybody send me how to create a linked list program in C++.
    > Basically I want to know how a node is handled in c++. I know this in c
    > only.
    >
    > in c we create a structure and use that structure for ctreating nodes.
    > how is this achieved in c++ .
    >
    > my c structure is:
    >
    > struct node
    > {
    > int info;
    > struct node *link;
    > };
    >
    > please tell me how do we do this in c++.
    >
    > Rgrds
    > Indra
    >

    #include <list>
    ..
    ..
    ..

    there is nothing magical in C++ to implement a linked list. Sure it can
    be done - possibly more elegantly and safer but essentially it is the
    same algorithm no matter what the language.

    If you need a solid and reliable linked list use STL std::list
    --dakka
     
    Dakka, Jan 30, 2006
    #2
    1. Advertising

  3. Indraseena

    Indraseena Guest

    Hi,

    I wanna know the class definition for the linked list. how it is
    created. Will the class contain both information and addres filed in a
    class or how?

    class node
    {
    into info;
    node *link;

    public:
    void create_list();
    void display_list();
    };

    Is this declaration fine??
     
    Indraseena, Jan 30, 2006
    #3
  4. Indraseena

    babu Guest

    I usually create linked list like this:

    struct node
    {
    Data m_data;
    struct node* m_pNext;
    };

    class CList
    {
    public:
    CList();
    ~CList();
    void Create();
    void Add(Data& osData);
    void Display();
    void Delete(Data& osData);
    void Destroy();
    private:
    struct node* m_pHead;
    };

    The implementation will be as per your requirement...
     
    babu, Jan 30, 2006
    #4
  5. Indraseena

    Ben Radford Guest

    babu wrote:
    > I usually create linked list like this:
    >
    > struct node
    > {
    > Data m_data;
    > struct node* m_pNext;
    > };
    >
    > class CList
    > {
    > public:
    > CList();
    > ~CList();
    > void Create();
    > void Add(Data& osData);
    > void Display();
    > void Delete(Data& osData);
    > void Destroy();
    > private:
    > struct node* m_pHead;
    > };
    >
    > The implementation will be as per your requirement...
    >


    It's probably best to use the STL implementation unless you have a
    specific need that requires you to roll your own since it's more
    thoroughly tested. Although it's my opinion that everyone should try
    creating the data structure(s) they use at least once to better
    understand how it works behind the scenes.

    --
    Ben Radford
    "Why is it drug addicts and computer aficionados are both called users?"
     
    Ben Radford, Jan 30, 2006
    #5
  6. Indraseena

    Edson Tadeu Guest

    In C++ you do it this way (assuming you want your own implementation
    instead of the STL one):

    #include <iostream>

    using namespace std;

    template <class T>
    class List {
    protected:
    struct Node {
    Node* next;
    T val;

    // Constructor
    Node() : next(0) {}
    Node(Node *p_next) : next(p_next) {}
    Node(Node *p_next, const T& p_val) : next(p_next), val(p_val) {}
    };

    Node* head;
    static Node c_end;

    public:
    struct iterator {
    Node* node;

    iterator(Node *p_node) : node(p_node) {
    }

    bool operator!=(const iterator& another) {
    return node != another.node;
    }

    void operator++() {
    node = node->next;
    }

    T operator*() {
    return node->val;
    }
    };

    List() {
    head = &c_end;
    }

    iterator begin() {
    return iterator(head);
    }

    iterator end() {
    return iterator(&c_end);
    }

    void push_front(const T& p_val) {
    head = new Node(head, p_val);
    }

    void insert_after(iterator p_where, const T& p_val) {
    p_where.node->next = new Node(p_where.node->next, p_val);
    }
    };

    template <typename T> typename List<T>::Node List<T>::c_end;

    int main()
    {
    List<int> myList;

    myList.push_front(9);
    myList.push_front(5);
    myList.push_front(4);
    myList.push_front(1);
    myList.push_front(3);

    List<int>::iterator it = myList.begin();

    ++it;
    ++it;

    myList.insert_after(it, 1);

    for (List<int>::iterator i = myList.begin(); i != myList.end(); ++i) {
    cout << *i << ", ";
    }
    cout << endl;

    return 0;
    }


    // Output: 3, 1, 4, 1, 5, 9,

    Of course you can improve it a lot, adding a pointer to the tail node,
    push_back's, pointer to previous element (double linked list), etc...
    and as a homework, implement a destructor so that delete is called on
    every element (otherwise it is leaking memory) :)

    Regards,
    Edson
     
    Edson Tadeu, Jan 30, 2006
    #6
  7. Indraseena

    Daniel T. Guest

    In article <>,
    "Indraseena" <> wrote:

    > Hi can anybody send me how to create a linked list program in C++.
    > Basically I want to know how a node is handled in c++. I know this in c
    > only.
    >
    > in c we create a structure and use that structure for ctreating nodes.
    > how is this achieved in c++ .
    >
    > my c structure is:
    >
    > struct node
    > {
    > int info;
    > struct node *link;
    > };
    >
    > please tell me how do we do this in c++.
    >
    > Rgrds
    > Indra


    <http://www.sgi.com/tech/stl/Slist.html> Gives docs and a complete
    implementation of a single-linked list.

    --
    Magic depends on tradition and belief. It does not welcome observation,
    nor does it profit by experiment. On the other hand, science is based
    on experience; it is open to correction by observation and experiment.
     
    Daniel T., Jan 30, 2006
    #7
  8. Indraseena

    persenaama Guest

    Linked list in C++ is better to be written to be datatype agnostic:

    template <datatype>
    class node
    {
    datatype m_data;
    node* m_prev; // double linked list, ofcourse :)
    node* m_next;
    public:
    // ... blabla ...
    };

    This way you can support much more types, usually in C similiar thing
    is written using void* and the error prone and cumbersome ways to work
    with what that implies.

    Btw. the code you posted, is already C++. It is just not advantageous
    to write list class which stores only objects of type int, hence, the
    recommendation to use templates. The standard library does this with
    std::list for example, check it out, pretty neat stuff.

    FWIW, I have alternative std::list -like implementation draft at
    www.liimatta.org, DL fusion the implementation is include/core/list.hpp
    there are some (trivial and biased!) benchmarking results in the fusion
    page on various compilers (with the standard library implementations
    that go with them by default) and architechtures.
     
    persenaama, Jan 30, 2006
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    483
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    472
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    512
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    673
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    759
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page