Code Review:Linked List

[Script Coder]

Having started C++ programming two days ago and never reading C++ before, I have no idea what my code should look like. I do have 5 years experience in Python and so am no stranger to liked lists. I just want to know if this would be considered good C++ code. It compiles perfectly on Mingw g++, and I have run basic tests on the functions. All I want is a code review. Any and all critique is both wanted and welcome. Thanks in advance :)

<List.h>

struct node
		{
			node *next, *prev;
			int i;
		};

class List
	{
		node *start, *end;
		public:
		List();
		int operator[](int pos);
		void append(int i);
		int pop();
		void place(int i, int pos);
		void del(int pos);
		int length();
	};

List.cpp

#include "List.h"

List::List()
	{
		start=new node;
		start->next=0;
		start->prev=0;
		start->i=0;
		end=start;
	}

void List::append(int i)
	{
		end->next=new node;
		end->next->prev=end;
		end=end->next;
		end->i=i;
		end->next=0;
		start->i++;
	}

int List::operator[](int pos)
	{
		if((start->i)<pos)
		{
			return(0);
		}
		node *current=start;
		for(int i=pos;i>-1;--i)
		{
			current=current->next;
		}
		return(current->i);
	}
	
int List::pop()
	{
		int temp=end->i;
		end=end->prev;
		delete (end->next);
		end->next=0;
		start->i--;
		return(temp);
	}

void List::place(int j, int pos)
	{
		node *temp;
		if((start->i)<pos)
		{
			return;
		}
		node *current=start;
		for(int i=pos;i>-1;--i)
		{
			current=current->next;
		}
		temp->i=j;
		temp->next=current;
		temp->prev=current->prev;
		current->prev->next=temp;
		current->prev=temp;
		start->i++;
		return;
	}

void List::del(int pos)
	{
		if((start->i)<pos)
		{
			return;
		}
		node *current=start;
		for(int i=pos;i>-1;--i)
		{
			current=current->next;
		}
		current->prev->next=current->next;
		current->next->prev=current->prev;
		delete current;
	}

int List::length()
	{
		return(start->i);
	}
	
int main(int agrc, char* args[])
	{
          //test code
	}

[ne555]

void List::append(int i)
	{
//...
		start->i++;
	}

¿eh? ¿what's 'i' for?

[Script Coder]

The start node's i value stores the number of elements in the list

[vlad from moscow]

It is very bad coding style. I wonder did you indeed 5 years program in Python?! I looked through only the header

struct node
		{
			node *next, *prev;
			int i;
		};

class List
	{
		node *start, *end;
		public:
		List();
		int operator[](int pos);
		void append(int i);
		int pop();
		void place(int i, int pos);
		void del(int pos);
		int length();
	};

What is it style coding?! Also I do not understand why structure Node is not a nested struct of class List? Do clients have direct access to it? Also subscripting operator function shall have a const visavi. I advice to see the interface of the standard class std::list.

[zb0S216C]

I can list multiple flaws in your code that would turn your hair grey from trying to find them. I was going to list them, until I saw this:

Script Coder wrote:

"Having started C++ programming two days ago and never reading C++ before, I have no idea what my code should look like."

Then why did you attempt to implement a linked list? While LLs are simple to understand, they are an absolute pain to implement and maintain, especially in C++. I recommend learning C++ before implementing a LL.

_Wazzak

[Script Coder]

Python does not have structs, so its new for me, but i'll be sure to change it...thank you for the critique, anything else...also what would be a good project for me next, to improve my skill?

[Vlykarye]

You should seriously read a book or something. Haha.
If you want to improve your skill, improve your knowledge first.

[Script Coder]

I can list multiple flaws in your code that would turn your hair grey from trying to find them

could you please list them, i learn most from my mistakes, that is why i attack hard challenges, so that i can make more mistakes and thus learn more :)

[zb0S216C]

Script Coder wrote:

"could you please list them"

If you say so:

1) node lacks a constructor & destructor
2) List::operator[] isn't being used correctly. A user would expect a node.
3) There are no checks for NULL; a heap corruption and/or access violation waiting to happen.
4) List lacks a destructor. A fatal mistake.
5) There's no documentation at all. It's hard to determine what you intend to accomplish in each function.

Clearly, you're in desperate need of a book. Don't take this the wrong way, but you're not impressing anybody. 2 days is no where near enough time. In that time frame, you should be implementing basic programs, such as a calculator, or a shop till simulator. Python is far from C++.

_Wazzak

[vlad from moscow]

could you please list them, i learn most from my mistakes, that is why i attack hard challenges, so that i can make more mistakes and thus learn more :)

For example how to determing that a list is empty? What iwill length() return for newly created list?!
Why does not Node have a constructor? There are many questions to your design of list.

[Script Coder]

Thank You guys for all your help. Just to defend myself a bit (i feel a bit attacked, maybe its just me) :

List::operator[] isn't being used correctly. A user would expect a node.

In my second post, I said that i would make node internal to List, therefore the user, will only know that it is a list of ints, they aren't able to touch anything of type "node", hence no NULL checks...i handle all the node code myself.

And sorry, i do have a hard time documenting my code, and also I did not know a struct could have a constructor and deconstructor. And could anyone suggest basic program ideas that involve maths, physics, db's, ect. that don't have GUIs

[Vlykarye]

It's not just you. Vlad is a bit of a heated person. Just the way he is. Don't feel ashamed or anything. Like you said, you learn from mistakes. The best people to point out mistakes are the harsh critical ones. You just need to be tough enough to take the hits.

And Framework and I are just looking out for you. Learning by example and mistake is good. But you should really try learning as much as you can from books and tutorials before jumping into a hells problem.

[ne555]

The start node's i value stores the number of elements in the list

If you want to store the list size, you may want to store in the list. However that's not practical to maintain (check out splice)
Think what you will need to do if you want to store strings instead of numbers.
Edit: Using an "empty" node as a header it is not so bad idea, but then don't allocate it dynamically.

Framework wrote:

2) List::operator[] isn't being used correctly. A user would expect a node.

No, a user shouldn't know that node exists. He stores things in the list, and expect to receive that things.
How the list manage that (if it wraps on another structure) it's irrelevant.

Edit: You may want to edit the elements, so return a reference instead (for the non-const version). Still, using that operator to iterate through the list will be awful. O(n^2)


On List::place, temp is an invalid pointer

[Vlykarye]

No, a user shouldn't know that node exists. He stores things in the list, and expect to receive that things.
How the list manage that (if it wraps on another structure) it's irrelevant.

But it is very relevant if he wants to learn how to properly code. What if he needs someone to change something for him?

Also. How do you guys get the person's name above the quote?

[zb0S216C]

ne555 wrote:

"No, a user shouldn't know that node exists. He stores things in the list, and expect to receive that things. How the list manage that (if it wraps on another structure) it's irrelevant."

No, judging by the use of node::i, he's using it to store the offset of the node. That said, List::operator[] returns the offset of a node. Surely, a user would expect data or a node, not a index. Look at an array. The sub-script operator returns a value from the array, not the element's offset.

Additionally, there's many potential access violations just waiting to happen.

Vlykarye wrote:

"How do you guys get the person's name above the quote?"

When you use quote tags, make sure the opening tag resembles this: [quote=Username].

_Wazzak

[ne555]

[quote=name]text[/quote]

I don't get what you are trying to say. ¿May to provide an example?

[Script Coder]

node::i holds the data, there is no stored offset into the list. Could you guys please give simple example projects that have to do with math and physics that you feel would be appropriate?

ne555 wrote:

May to provide an example

source code:

<quote=ne555>May to provide an example</quote>

just replace '<' with '['

[Script Coder]

I have altered my program, unfortunately I have not yet added comments yet. If there is an unclear piece of code I will explain it. Once again, all critique is wanted, no matter how harsh. Thanks in advance.

List.h

class List
	{
		struct node
		{
			node *next, *prev;
			int i;
			node(List::node* n, List::node *p, int i);
		};

		node *start, *end;
		int size;
		public:
		List();
		~List();
		int operator[](int pos);
		void append(int i);
		int pop();
		void place(int i, int pos);
		void del(int pos);
		int length();
	};

List.cpp

#include "List.h"
#include <iostream>

List::node::node(node* n, node *p, int j)
	{
		next=n;
		prev=p;
		i=j;
	}
	

List::List()
	{
		start=new node(0,0,0);
		end=start;
		size=0;
	}

List::~List()
	{
		node *current=start, *next=start->next;
		int j=size;
		for(int i=0;i<=j;i++)
		{
			delete current;
			current=next;
			if(current->next!=0)
			{
				next=current->next;
			}
		}	
	}
void List::append(int i)
	{
		end->next=new node(0,end,i);
		end=end->next;
		size++;
	}

int List::operator[](int pos)
	{
		if((size)<pos)
		{
			return(0);
		}
		node *current=start;
		for(int i=pos;i>-1;--i)
		{
			current=current->next;
		}
		return(current->i);
	}
	
int List::pop()
	{
		int temp=end->i;
		end=end->prev;
		delete (end->next);
		end->next=0;
		size--;
		return(temp);
	}

void List::place(int j, int pos)
	{
		if((size)<pos)
		{
			return;
		}
		node *current=start;
		for(int i=pos;i>-1;--i)
		{
			current=current->next;
		}
		node *temp= new node(current,current->prev,j);
		current->prev->next=temp;
		current->prev=temp;
		size++;
		return;
	}

void List::del(int pos)
	{
		if((size)<pos)
		{
			return;
		}
		node *current=start;
		for(int i=pos;i>-1;--i)
		{
			current=current->next;
		}
		current->prev->next=current->next;
		current->next->prev=current->prev;
		delete current;
	}

int List::length()
	{
		return(size);
	}
	
int main(int agrc, char* args[])
	{
	}

Also i don't know how to make the node deconstructor :)

[naraku9333]

node doesn't need a destructor. Just my opinion but, overloading operator[] gives the impression of random access, which linked lists do not have.

[Script Coder]

How do i know if it needs one or not? Is there anything else wrong with my program?