Link list

[rjain02]

Dear all,
I am working on a link list classwork that my teacher wrote the code for, however this code is not working, I believe there might be some syntax error and have spent some time looking, but to no avail. Please help:


#include <iostream>
#include <stdio.h>
using namespace std;

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

class Linklist{
private:
Link *first;
public:
Linklist(){first = null;}
void additem(int d);
void display();
};

void Linklist:: additem(int d){
Link *newLink = new Link;
newLink -> data = d;
newlink -> next = first;
first = newLink;
};

void Linklist :: display(){
link * current = first;
while(current!= null){
cout<< current -> data;
current = current -> next;
}
};

int main(){
Linklist wu;
wu.additem(25); wu.additem(30);wu.additem(35); wu.display();
}

Also if someone could explain what the code is doing that would be much appreciated.

Thanks

[S6k9GNh0]

1. Use CODE tags please. I beg of you. Use CODE tags...
2. To be quite honest, your teacher fails to really take advantage C++ in this class and is a rather bad example.
3. Let's start with a good explanation. In a linked-list, the objective is to create a string of a certain type of elements connected via pointers. This gives optimized iteration time over arrays and vectors.

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

This piece of code is a poor example in C++ because it doesn't take advantage of an obvious case for templates. However, your class may not "be that far" yet. Any how, the struct here is what I mean by "elements" in the "string of elements".

class Linklist{
private:
Link *first;
public:
Linklist(){first = null;}
void additem(int d);
void display();
};

This is the I guess, the "element handler" class. This class is what handles all of your elements when you need to look at them, delete them, or add to them. Link *first; is the first link in the string of arrays and the only reference you have to your elements. Through this pointer, you are able to fetch all of your other elements in a linear fashion like so:

Link * iterator = first;
while(current != null)
{
   current = iterator->next;
}

Which is similar to what we did in display(). However, this is our first error, which is link * current = first needs to be Link * current = first as capitalization does matter.

As for the second error, there is a semi-colon after the function additem(int d) which needs to be removed.

Third error would be that null isn't a type. You should be able to replace null with 0 however or when checking for pointers, you can use the pointer itself as a condition.

Fourth error would be that the while loop in display() never ends. You need to close the while loop with another bracket.

Also, for compliance-with-C reasons, stdio.h works but its suggested that you use cstdio instead of stdio.h.

I'd also like to suggest against the use of using namespace std;. It's bulky and rather ugly to be fair. To increase compile time that much for the use of one std::cout isn't funny.

As for the entire example, I personally don't like it. Here is my version of this link list example:

#include <iostream>

template<typename X>
struct Link
{
	Link(X _data, Link<X> * _next) : data(_data), next(_next) {}
	X data;
	Link<X> *next;
};

template<typename X>
class LList
{
private:
	Link<X> *_first;
public:
	LList() : _first(NULL) {}

	~LList()
	{
		if (_first) //If we have at least one element.
		{
			Link<X>* pIter = _first;
			Link<X>* pNext;
			do
			{
				pNext = pIter->next;
				delete pIter;
				pIter = pNext;
			}
			while (pNext); //Do we still have something to delete.
		}
	}

	void AddItem(X d)
	{
		Link<X> *newLink = new Link<X>(d, _first); //This is a potential leak...
                //A safer approach would be to use smart pointers.
		_first = newLink;
	}

	void Display()
	{
		Link<X> * iter = _first;
		while (iter)
		{
			std::cout << iter->data << " ";
			iter = iter->next;
		}
	}
	//Please note that in order for this function to work, it needs to be a type that works with std::cout
	//std::cout is not type safe.
};

int main()
{
	LList<int> tmpList;
	tmpList.AddItem(25); tmpList.AddItem(30); tmpList.AddItem(35); tmpList.Display();
}

or

http://codepad.org/YWVs4psI

This essentially does the same thing. Also, please note that the elements given won't display in the order given. This is because, when your using a list, you shouldn't need to know the order of what things are in, which is because you exchange that for iteration speed.

Also, please note that this entire implementation is considered a singly-linked list as compared to a doubly-linked list. The difference is that a singly-linked list can only iterate in one direction and a doubly-linked list can iterate in both directions. I personally don't see the use of a doubly-linked list other than unneeded features. If you need a reason to iterate through both directions, you probably shouldn't be using a list.

[rjain02]

Thank you computerquip. Your explanations have been very helpful. Our class deals with Java, however the professor tells us to use C++. In a curriculum where where have not even learned the basics it is confusing. Hence I am learning some basic level C++, and this site with all its contributers has been a tremendous help!

Regards,
Rahul