How to insert/delete a node.

[rabster]

I asked sort of similar question before, but well I'm not gonna lie, was really a jacked up linked list http://www.cplusplus.com/forum/general/182652/. So I remade the whole thing and I think this one is A LOT better so far and so here it is. However, I've come across one problem how do I know where certain element in a linked list are? Before I was cycling through the list just to put in or delete the value, which is not good at all. And one of the good thing that lists are good at is insertion and deletion but how exactly? How are you accessing where to put in or remove an element.

#include <iostream>
#include <string>

using namespace std;
class list {
private:
    struct component {
        component* node;
        int info;
    };
    int eleAmount;
    int counter;
    component* head;
    component* tail;
    component* nC;
public:
    list(int value);
    ~list();
    void addnode(int value) {
        eleAmount++;
        nC = new component;
        nC->info = value;
        nC->node = NULL;
        tail->node = nC;
        tail = nC;
    }
    void insertnode(int value, int index) {
        eleAmount++;
        
    }
    void deletenode(int value, int index) {
        eleAmount--;
        
    }
    void showElements() const {
        component* cycle = head;
        while(cycle->node != NULL) {
            cout << cycle->info;
            cycle = cycle->node;
        }
    }
    void showAddresses() const {
        component* cycle = head;
        while(cycle->node != NULL) {
            cout << cycle->node;
            cycle = cycle->node;
        }
    }
    void clearlist() {
        component* destroy;
        while(destroy->node != NULL) {
            destroy = head;
            delete destroy;
            head = head->node;
        }
    }
    bool is_empty() const {
        if(head != NULL) {
            return false;
        }
        else {
            return true;
        }
    }
    int elementAmount() const {
        return this->eleAmount;
    }
};
list::list(int value) {
    counter = 0;
    eleAmount = 1;
    nC = new component;
    nC->info = value;
    nC->node = NULL;
    head = nC;
    tail = nC;
}
list::~list() {
    component* destroy;
    while(destroy->node != NULL) {
        destroy = head;
        delete destroy;
        head = head->node;
    }
    delete head;
    head = NULL;
    tail = NULL;
}
int main() {
    char response;
    int value;
    cout << "Enter in a value to start the list: ";
    cin >> value;
    list A(value);
    cout << "Keep adding in values for the list, and enter in 999 when you are done. ";
    value = 0;
    while(value != 999) {
        cin >> value;
        A.addnode(value);
    }
    A.showElements();
    cin >> response;
    return 0;
}

[Shadowwolf]

A std::list has linear complexity for insertion. This could easily be implemented with a for loop. An example:

component* node = this->head;
for(int i = 0; i < index; ++i)
{
    node = node->next;
 }
newnode->next = node->next;
node->next = neenode;

Of course you should check if index is within range, otherwise it's undefined behavior.

There's no magic involved. Cycling through the list is quite a common implementation for list-like structures. For a double linked list you could check if the index is past halfway and iterate backwards in that case for a better preformance. But for single linked lists this is quite a common solution.

[rabster]

So wait I was doing it correctly in my previous post, because that is what I did?

[Shadowwolf]

I'd probably keep amount as a local variable instead of as a member field, but yes, your approach seems to have linear complexity line the std::list type is guaranteed to at least have.

Another difference is the fact that the links are a separate type from the list now, allowing faster appending (constant time vs linear time). But the insertion is the same .

[YFGHNG]

To answer your question, @OP, that's the disadvantage of linked lists, in that searching must go through at worst, the entire list O(n). Especially since we only see the address of the head node and have to subsequently go through each pointer until we find the address of the value we want.

But after you find said value, inserting and deleting is the easier part where you shift pointers around.

http://www.geeksforgeeks.org/linked-list-vs-array/

[rabster]

Alright so I completed my linked list and well here it is:

#include <iostream>
#include <string>
#include <crtdbg.h>
using namespace std;
class list {
private:
	struct component {
		component* node;
		int info;
	};
	int eleAmount;
	component* head;
	component* tail;
	component* nC;
public:
	list(int value);
	~list();
	void addnode(int value) {
		eleAmount++;
		nC = new component;
		nC->info = value;
		nC->node = NULL;
		tail->node = nC;
		tail = nC;
	}
	void insertnode(const int value, const unsigned int index) {
		try {
			if (index >= eleAmount) {
				throw string("Error cannot insert node between invalid values!");
			}
			eleAmount++;
			nC = new component;
			nC->info = value;
			component* save = head;
			for (int i = 0; i < (index - 1); i++) {
				save = save->node;
			}
			nC->node = save->node;
			save->node = nC;
		}
		catch (string &error) {
			cerr << error << '\n';
		}

	}
	void deletenode(const unsigned int index) {
		try {
			if (index >= eleAmount) {
				throw string("Error cannot insert node between invalid values!");
			}
			eleAmount++;
			component* del;
			component* save;
			del = head;
			for (int i = 0; i < (index - 1); i++) {
				del = del->node;
			}
			save = del->node;
			del->node = save->node;
			delete save;
		}
		catch (string &error) {
			cerr << error << '\n';
		}
	}
	void showElements() const {
		try {
			if (is_empty() != false) {
				throw string("Error cannot print empty list");
			}
			component* cycle = head;
			while (cycle->node != NULL) {
				cout << cycle->info;
				cycle = cycle->node;
			}
			cout << cycle->info;
		}
		catch (string &error) {

		}
	}
	void showAddresses() const {
		component* cycle = head;
		while (cycle->node != NULL) {
			cout << cycle->node;
			cycle = cycle->node;
		}
	}
	void clearlist() {
		try {
			if (is_empty() != false) {
				throw string("Error cannot clear an already empty list!");
			}
			component* destroy;
			while (head->node != NULL) {
				destroy = head;
				head = head->node;
				delete destroy;
			}
			delete head;
		}
		catch (string &error) {
			cerr << error << endl;
		}
	}
	bool is_empty() const {
		if (head != NULL) {
			return false;
		}
		else {
			return true;
		}
	}
	int elementAmount() const {
		return this->eleAmount;
	}
};
list::list(int value) {
	eleAmount = 1;
	nC = new component;
	nC->info = value;
	nC->node = NULL;
	head = nC;
	tail = nC;
}
list::~list() {
	if (is_empty() != true) {
		clearlist();
	}
}
int main() {
	char response;
	int value;
	int index;
	cout << "Enter in a value to start the list: ";
	cin >> value;
	list A(value);
	cout << "Keep adding in values for the list, and enter in 999 when you are done. ";
	value = 0;
	while (value != 999) {
		cin >> value;
		A.addnode(value);
	}
	A.showElements();
	cout << "\nWould you like to insert a node? ";
	cin >> response;
	if (response == 'Y') {
		cout << "Enter the index of where you'd like to insert your node: ";
		cin >> index;
		cout << "Enter the value of your node: ";
		cin >> value;
		A.insertnode(value, index);
	}
	A.showElements();
	cout << "\nWould you like to delete a node? ";
	cin >> response;
	if (response == 'Y') {
		cout << "Enter the index of where you'd like to delete your node: ";
		cin >> index;
		A.deletenode(index);
	}
	A.showElements();
	A.clearlist();
	if (_CrtDumpMemoryLeaks() == 1) {
		cerr << "\nError memory leak\n";
		A.showElements();
	}
	else {
		clog << "\nNo memory leak";
	}
	cin >> response;
	return 0;
}

My question is, is this a perfectly fine linked list. Anything wrong with it?

[Shadowwolf]

I'd decrease the number of elements when you delete an element (deleteNode). You use increment on eleAmount, whereas I think you meant to decrease the variable. And I'd probably append a space between the elements you output in your showElements function (otherwise the output is harder to read), but that's just a tiny detail.

Other than that, it looks fine at first sight. I can't find any large errors in the code you posted. Of course I could be looking over things, so I'd test the code first though.

[cire]

My question is, is this a perfectly fine linked list. Anything wrong with it?

In addition to what Shadowwolf said, nC has no business being a member of the class. You use it as a local variable, so make it local to the functions it is used in.

Exceptions should not be used for ordinary flow control as you are doing here.

Why can't you clear an empty list? It would just stay empty.
Why can't you print an empty list? It would just display nothing.

The exceptions in deletenode and insertnode make sense, but only if they're propagated to the calling code (and some version of std::exception or something derived from it would be much better than throwing a string.)

Why do you have member functions with the word node in them? Client code doesn't care about nodes. It wants to insert, delete or add a value, not a node.

[rabster]

Sorry for really late reply but thanks for all the help guys!