c++链表方面疑惑

Question

我现在正在学习链表。而老师给我们教的链表跟网上的实现的方式不一样。所以我想知道这两种实现方式有什么优劣，为什么网上的绝大部分都是后者。

老师的版本：

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;
    ...
};

网上的版本：

class node
{
    public:
        int value;
        node* next;
        //构造函数
};
class List
{
    private:
        node* headnode;
        int count;
    public:
        //成员函数
};

可以看出我们老师的版本是直接把所有操作函数都放在了节点类当中。
所以希望能知道这两种实现方式有什么区别，有什么优劣之分，为什么网上鲜见这种实现方式呢？

Answer 1

This question is not bad. As a CS(or any other majors) student, skepticism in the class is pretty significant.

而老师给我们教的链表跟网上的实现的方式不一样。

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.

KISS principle

In c++'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.

List may be empty

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, e.g. 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.

Answer 2

网上的版本把链表和结点两个类分开了，在List中有count字段可以记录链表的长度。
而你老师的版本没有这个字段，替代的方法可以是：用链表的第0个结点记录链表长度，数据的存放从第1个结点开始。
我认为这两种方法不分优劣，只是实现的方式不同，学习链表的时候不用纠结这种细节，更关键的是理解链表中的指针，以及链表增删改查的操作。