Linked lists?

would anyone know of a good site or souce for a Linked list example?

Thanks

Hi Regan

Will this help?


// linked list
#include <iostream>
using namespace std;
////////////////////////////////////////////////////////////////
struct link //one element of list
{
int data; //data item
link* next; //pointer to next link
};
////////////////////////////////////////////////////////////////
class linklist //a list of links
{
private:
link* first; //pointer to first link
public:
linklist() //no-argument constructor
{ first = NULL; } //no first link
void additem(int d); //add data item (one link)
void display(); //display all links
};
//--------------------------------------------------------------
void linklist::additem(int d) //add data item
{
link* newlink = new link; //make a new link
newlink->data = d; //give it data
newlink->next = first; //it points to next link
first = newlink; //now first points to this
}
//--------------------------------------------------------------
void linklist::display() //display all links
{
link* current = first; //set ptr to first link
while( current != NULL ) //quit on last link
{
cout << current->data << endl; //print data
current = current->next; //move to next link
}
}
////////////////////////////////////////////////////////////////
int main()
{
linklist li; //make linked list

li.additem(25); //add four items to list
li.additem(36);
li.additem(49);
li.additem(64);

li.display(); //display entire list
return 0;
}



JDT

thanks Mr. Jones, thats what i was looking for!!

two more things i'de like to ask:
1. I see you've make a C/c++ tag editor. will you ,by chance, be realeasing a "slick" full tag editor like the VB one? cause i'de like to have it :)\

2. one quetion on the additem method.

void linklist::additem(int d) //add data item
{
link* newlink = new link; //make a new link
newlink->data = d; //give it data
newlink->next = first; //it points to next link
first = newlink; //now first points to this
}

in this method does the line, "link* newlink = new link;" create a pointer called "newlink" that points to a new instance of a "link" object.

well malbe three questions :) What does the "->" do?


thanks again for your time !

Regan

Wow, a C++ question that I can answer.

link* newlink = new link; //make a new link
Declares a variable of type pointer to link struct and initializes it
with a new link struct.

-> is the way of referencing a member of a struct/class from a
pointer to the struct/class, just as . is the way to reference a
member from a struct/class variable.


[I know, I should have let JDT answer, but... ;)]

Hi Regan

Hope that example helped.

I'll send you a copy when its done. I think I just need to add support for */Comment/*style comments and of course run it through some good beta testers. I don't think I'll *release* it since it does not seem to be a very popular tool. I like using it but most people won't. I might pot the source though...


JDT

JDT, if you send me the list of tags I can add C stuff to my codeTag. Also, the method I'm using makes /* */ comments easy, so I could do that. My source will be released once it is beta tested by other experts, gurus, moderators and administrators.

hey guys.

yes, thanks for the example Sam, thats exactly what i needed to get going!

Keith, k i understand now about the pointer *, beautiful thanks. but still a bit hazy on the arrow thin ->. Why wouldn't i just use the "." dot notation. Or is it that i use the -> when ever i want to refernce a memeber of a class or struct, no matter what! An use the "." to reference a method or function in a class?


thanks agian for you time!

Regan

OK, dot is used if the LHS is a normal or reference variable. The -> notation is used when the LHS is a pointer. Eg:
typedef struct {
int x, y;
} POINT;

POINT *lpPoint, vPoint, &refPoint
int value;

value = lpPoint->x;
value = vPoint.x;
value = refPoint.x;
Hope that helps.

Hi Regan

Its been a while since I had to fight my way through the nasty language of C and its derivatives. So forgive me if I am not on the money but I’ll try to explain.

The member-selection operator “.” Is used when you are not referencing a pointer.
The member-selection operator “->” Is used when you are referencing a pointer or address.

Ya, I know how you feel. Those darn pointers. Just wait till you have to deal with ** pointers to pointers. Once you finally make the breakthrough the pointers make sense.

Anyways, run this code and then try to switch operators in main and in the function. You will find that you can’t. In the call to the function I am using the ampersand “&” to send the address to the var instead of declaring a var of a pointer type which is the same thing as a pointer.


#include <iostream>

struct SomeStruct
{
int a;
double b;
};

void SomeFunction(SomeStruct* var);


int main()
{
SomeStruct var;

//The . operator is used since we are not pointing to the object
var.a = 1;
var.b = 1.1;
std::cout << var.a << "\n" << var.b << "\n\n";

SomeFunction(&var);
std::cout << var.a << "\n" << var.b << "\n\n";
return 0;

}

void SomeFunction(SomeStruct* var)
{
//the -> operator is used since we are pointing to the address of the object
var->a = 2;
var->b = 2.1;
}



Looks like banjo beat me to the punch.;) But the good news is, it looks like I might remember more than i thought:D

thanks guys,

with both of your examples; by george i think i've got it! It totally makes sense. But Sam, please don't scare me with that pointer to pointer stuff LOL.

Thanks again guys!

Regan

pointers are scary when it comes to double pointers, usetheforce2, if u still need more references to linked list, let me know (email me or private msg me), ill lend u some of my slides which might help, my email is asrar@joymail.com :)

I like to use a template in my linkedlist.h


// linkedlist.h

#ifndef LINKED_LIST
#define LINKED_LIST

#include <iostream>

template<class DataType> //struct link<DataType>
struct link //one element of list
{
DataType data; //data item
link* next; //pointer to next link
};
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

template<class DataType> //class linklist<DataType>
class linklist //a list of links
{
private:
link<DataType>* first; //pointer to first link
public:
linklist() //no-argument constructor
{ first = NULL; } //no first link
void additem(DataType d); //add data item (one link)
void display(); //display all links
DataType remove();
};
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

template<class DataType>
void linklist<DataType>::additem(DataType d) //add data item
{
link<DataType>* newlink = new link<DataType>; //make a new link
newlink->data = d; //give it data
newlink->next = first; //it points to next link
first = newlink; //now first points to this
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

template<class DataType>
void linklist<DataType>::display() //display all links
{
link<DataType>* current = first; //set ptr to first link
while( current != NULL ) //quit on last link
{
cout << endl << current->data; //print data
current = current->next; //move to next link
}
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

template<class DataType>
DataType linklist<DataType>::remove() // removes the first link of a linked list
{

if (first != NULL)
{
link<DataType> * oldfirst = first;
DataType savedData = first->data; // save first link's data
first = first->next; // set first link to value of second link (remove a link)
delete oldfirst;
return savedData;
}
}

#endif


Then you can create linked lists using:

linklist<int> cool;
linklist<char> neato;
linklist<string> wow;

STL allready has a list class. Please don't re-invent the wheel, unless its a uni assignment and then well you need to do it for some learning purpose.

No need to keep digging up all these old threads. :)

But I am so dumb I can only answer old stuff. Maybe we can start new threads.

JDT your code above is just what I'm looking for and I've found it invaluable to my understanding of linked lists. I was hoping you could update it with a delete method to help us newbies. Also how would I go about changing it to storing words of say 30 chars instead of ints. Would I make a word class or just try change the code for chars? Any source code I get my hands on is using templates.

Thanks in advance.

http://www.cs.colorado.edu/~main/chapter6/

Checkout node2.h and node2.template

It's a little over my head but I'll check it out. Thanks for the help.

If you're still lost, you might want to check out my example here: http://www.visualbasicforum.com/t44228.html

It uses a linked list structure for a hash table. The key in it is a string like you are saying, and it comes with a delete method(which is different since it's a hash table, so not much help here)...so you might want to check it out.