linked list program in c++

[Indraseena]

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

 

[Dakka]

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

 

[Indraseena]

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??

 

[babu]

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...

 

[Ben Radford]

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.

 

[Edson Tadeu]

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

 

[Daniel T.]

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.

 

[persenaama]

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.