Doubts about cPP linked list
I am learning linked lists now. The linked list that the teacher taught us is different from the way it is realized on the Internet. So I want to know what are the advantages and disadvantages of these two implementations, and why the vast majority of people on the Internet are the latter.
teacher"s version:
class List
{
private:
int data;
List *link;
public:
List();
void append(int val);
void insertElement(int pos, int val);
void deleteElement(int val);
void travalList()const; //
void getLength()const;
...
};
online version:
class node
{
public:
int value;
node* next;
//
};
class List
{
private:
node* headnode;
int count;
public:
//
};
you can see that our teacher"s version puts all the operation functions directly in the node class.
so I hope to know the difference between the two implementations, the advantages and disadvantages, and why this kind of implementation is seldom seen on the Internet.
This question is not bad. As a CS (or any other majors) student, skepticism in the class is pretty significant.
and the linked list that the teacher taught us is not the same as the way it is implemented on the Internet.
Yes, your teacher's implementation is uncommon and treats Link and Node as a whole entity, which is not reasonable. Because they are two different classes.
< H2 >
KISS principle < / H2 >
In cPP's OO design, keeping every class/struct simple is an important principle and it requires you to obey separate concerns . This is the first reason you should keep your node's data (and what it point to) in a separation class.
< H2 > List may be empty < / H2 >
It is a good practice to initialize all data member in the constructor (though not required forcefully), so, once you create an object of your List , the size will be 1 (because of the data private member. Mostly, List should be able to be empty. This is the second reason you should keep your node's data (and what it point to) in a separation class.
To solve the problem, you may want to regard the first element ( data ) as length (like @ BecomeBright said), so the list is empty-able, but there still exists problem. Pascal strings actually use this trick (first member records length), but if list member's type is not integral type, the trick is invalid (you should know that list can also be used to store std::string, float, double or other user-defined class/struct, and etc). BTW, the list's length will also not be able to be longer than the maximum value of the type, pascal string's length cannot be longer than 255);
As you can see above, allowing node integrate into the List is not a good practice.
The version on
separates the linked list from the node, and there is a count field in List to record the length of the linked list.
but your teacher's version does not have this field, the alternative method can be: use the 0th node of the linked list to record the length of the linked list, and the storage of the data starts from the first node.
I think there is no difference between the advantages and disadvantages of the two methods, but they are implemented in different ways. You don't have to struggle with such details when learning the linked list. What's more important is to understand the pointers in the linked list, as well as the operation of adding, deleting, changing and querying the linked list.
