c++鏈表方面疑惑

我現(xiàn)在正在學(xué)習(xí)鏈表。而老師給我們教的鏈表跟網(wǎng)上的實現(xiàn)的方式不一樣。所以我想知道這兩種實現(xiàn)方式有什么優(yōu)劣，為什么網(wǎng)上的絕大部分都是后者。

老師的版本：

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;    // 從頭節(jié)點遍歷輸出鏈表
    void getLength()const;
    ...
};

網(wǎng)上的版本：

class node
{
    public:
        int value;
        node* next;
        //構(gòu)造函數(shù)
};
class List
{
    private:
        node* headnode;
        int count;
    public:
        //成員函數(shù)
};

可以看出我們老師的版本是直接把所有操作函數(shù)都放在了節(jié)點類當(dāng)中。
所以希望能知道這兩種實現(xiàn)方式有什么區(qū)別，有什么優(yōu)劣之分，為什么網(wǎng)上鮮見這種實現(xiàn)方式呢？

回答

編輯回答

墨沫

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

而老師給我們教的鏈表跟網(wǎng)上的實現(xiàn)的方式不一樣。

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.

2018年6月28日 21:06

編輯回答

毀了心

網(wǎng)上的版本把鏈表和結(jié)點兩個類分開了，在List中有count字段可以記錄鏈表的長度。
而你老師的版本沒有這個字段，替代的方法可以是：用鏈表的第0個結(jié)點記錄鏈表長度，數(shù)據(jù)的存放從第1個結(jié)點開始。
我認為這兩種方法不分優(yōu)劣，只是實現(xiàn)的方式不同，學(xué)習(xí)鏈表的時候不用糾結(jié)這種細節(jié)，更關(guān)鍵的是理解鏈表中的指針，以及鏈表增刪改查的操作。

2018年3月3日 18:58