LinkedList mit Node-Implementierung

82141
Yechiel Labunskiy

Im Folgenden finden Sie meine Implementierung von Vorlagen Nodeund LinkedListKlassen. Ich würde es wirklich schätzen, wenn mir jemand Hinweise gibt, was ich verbessern kann.

//LinkedList with SumLists()

#include <iostream>
#include <set>

using namespace std;

template<class T>
class Node
{
public:
    T data;
    Node<T> * next;
    Node<T>(const T& d):data(d), next() {}
    Node<T>(const Node<T>& copyNode) : data(copyNode.data), next() {}

private:
    Node<T>& operator=(const Node<T>&);
};

template<class T>
class LinkedList
{
public:

    Node<T> * head;
    Node<T> * tail;

    LinkedList(const LinkedList& LL);
    LinkedList& operator=(LinkedList byValList);
    LinkedList(): head(NULL), tail(NULL) {}
    LinkedList(Node<T> * newNode) : head(newNode), tail(newNode) {}
    ~LinkedList();

    static LinkedList<int> sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2);

    void insertToTail(T val);
    void insertToHead(T val);
    void print();
    void printBackwards();
};

template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& LL) : head(NULL), tail(NULL)
{
    const Node<T> * curr = LL.head;

    if (!head && curr)
    {
        head = new Node<T>(curr->data);
        tail = head;
        curr = curr->next;
    }

    while (curr)
    {
        Node<T> * newNode = new Node<T>(curr->data);
        tail->next = newNode;
        tail = newNode;
        curr = curr->next;
    }
}

template<class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList byValList)
{
    std::swap(head, byValList.head);
    return *this;
}

template<class T>
LinkedList<T>::~LinkedList()
{
    Node<T> * curr = head;
    while (head)
    {
        head = head->next;
        delete curr;
        curr = head;
    }
}

template<class T>
void LinkedList<T>::insertToTail(T val)
{
    Node<T> * newNode = new Node<T>(val);
    if (tail == NULL)
    {
        newNode->next = tail;
        tail = newNode;
        head = newNode;
        return;
    }
    tail->next = newNode;
    tail = tail->next;
}

template<class T>
void LinkedList<T>::insertToHead(T val)
{
    Node<T> * newNode = new Node<T>(val);
    newNode->next = head;
    head = newNode;
    if (head->next == NULL)
        tail = newNode;
}

template<class T>
void LinkedList<T>::print()
{
    Node<T> * curr = head;
    while (curr)
    {
        cout<<curr->data<<" --> ";
        curr = curr->next;
    }
    cout<<"NULL"<<endl;
}

template<class T>
void LinkedList<T>::printBackwards()
{
    Node<T> * curr;
    LinkedList ReversedList(new Node<T>(head->data));
    curr = head->next;
    while (curr)
    {
        ReversedList.insertToHead(curr->data);
        curr = curr->next;
    }

    curr = ReversedList.head;
    while (curr)
    {
        cout<<curr->data<<" --> ";
        curr = curr->next;
    }
    cout<<"NULL\n";
}

template<class T>
LinkedList<int> LinkedList<T>::sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2)
{
    Node<T>* curr1 = LL1.head;
    Node<T>* curr2 = LL2.head;

    LinkedList<int> ResultList;

    int newData;
    int carry = 0;

    while (curr1 && curr2)
    {
        newData = (curr1->data + curr2->data + carry) % 10;
        carry = (curr1->data + curr2->data + carry) / 10;
        ResultList.insertToTail(newData);

        curr1 = curr1->next;
        curr2 = curr2->next;
    }

    while (curr1 || curr2)
    {
        if (carry)
        {
            if (curr1)
                ResultList.insertToTail(curr1->data + carry);
            if (curr2)
                ResultList.insertToTail(curr2->data + carry);
            carry = 0;
            continue;
        }
        if (curr1)
        {
            ResultList.insertToTail(curr1->data);
            curr1 = curr1->next;
        }
        if (curr2)
        {
            ResultList.insertToTail(curr2->data + carry);
            curr2 = curr2->next;

        }


    }

    return ResultList;
}

int main()
{
    LinkedList<int> LL1(new Node<int>(7));
    LL1.insertToTail(1);
    LL1.insertToTail(6);
    LL1.insertToTail(5);
    LL1.insertToTail(4);

    LinkedList<int> LL2(new Node<int>(5));
    LL2.insertToTail(9);
    LL2.insertToTail(2);

    LinkedList<int> LL = LL1.sumLists(LL1, LL2);
    LL.print();
    LL2.print();
    LL = LL2;
    LL.print();
    LL2.print();

    return 0;
}
Antworten
31
By the way, you can remove `#include ` since it's used nowhere in the code. Morwenn vor 6 Jahren 1

3 Antworten auf die Frage

30
Martin York

Please. Oh please stop doing this.

using namespace std;

If this was a header file you just polluted the global namespace for anybody that uses your file. This will get it banned from any serious project. This is done in textbooks for some reason and is fine for short ten line example programs. But once you get past 10 lines it has issues. Stop using it; it is a bad habbit that will get you into real problems on any decent sized project.

Why is “using namespace std;” considered bad practice?

You do really the standard library is in the namespace std. So it only costs you 5 extra characters to use it.

std::list<T>    myList;

Node is an implementation detail of the list. There is no reason for anybody using the list to know exactly how you implemented. Nor is there a reason to provide them with a Node class (as you will now need to maintain that concept).

template<class T>
class Node
{
public:
    T data;
    Node<T> * next;
    Node<T>(const T& d):data(d), next() {}
    Node<T>(const Node<T>& copyNode) : data(copyNode.data), next() {}

private:
    Node<T>& operator=(const Node<T>&);
};

So I would make Node a private member of LinkedList.

Its not really a copy constructor if you don't copy the next member.

Node<T>(const Node<T>& copyNode) : data(copyNode.data), next() {}

But OK. I can see this as an optimization. But personally I would have used a third constructor.

Node<T>(const Node<T>& copyNode, Node<T>* next)
    : data(copyNode.data)
   , next(next) 
{}

Then you can pass NULL as the second parameter, to initialize next.

So you have disabled the assignment operator:

private:
    Node<T>& operator=(const Node<T>&);

This is correct in C++03. But this is 2014 and C++11 is supported by all modern compilers and most already support C++14. So you should start using the modern version of the language.

    Node<T>& operator=(const Node<T>&) = delete;

Your implementation of linked list uses NULL as a terminator (which is fine). But if you add a fake sentinel value to your list it makes the implementation much easier as you never have NULL pointers (and end points at the sentinel).

In the copy constructor:

    if (!head && curr)

At this point head is always NULL. You just set it two lines above.

The other thing to note about the copy is that it will leak if you throw an exception. Since you don't know what the type of T is you have no idea how it will react to being copied. If halfway through the copy it throws an exception you should clean up any memory allocated so far before letting the exception propagate out of the constructor.

You are on the correct track with the assignment operator.

template<class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList byValList)
{
    // BUT this line is not enough
    //     Assignment should make a copy of all the elements.
    std::swap(head, byValList.head);


    // Usually this is implemented as:
    // Now you need to write a version of swap for this class
    // (both member and free standing)
    byValList.swap(*this);

    return *this;
}

I would write them like this:

template<class T>
LinkedList<T>::swap(LinkedList<T>& rhs) noexcept // swap is supposed to be 
{                                                // free from exception
    std::swap(head,  rhs.head);                  // throwing
    std::swap(tail,  rhs.tail);
}

template<class T>
void swap(LinkedList<T>& lhs, LinkedList<T>& rhs) {lhs.swap(rhs);}

In the destructor:
You don't use curr to do anything useful. Remove it.

    Node<T> * curr = head;

        curr = head;

In your insert methods. I personally would return a reference to *this (see below). But in both your insert methods you check for empty is always a bit weird before assigning the other end. I would break the test for empty into its own method empty() then you can test empty() before doing your special case code.

template<class T>
LinkedList<T>& LinkedList<T>::insertToTail(T val);

This allows you to use operator chaining.

LinkedList<T>  list;
list.insertToTail(1).insertToTail(2).insertToTail(3);

Nothing wrong with a print method. But I would do three additional things. As the print() method does not modify the content of the list it should be marked as const. Rather than always printing to std::cout I would pass the output stream as a parameter (it can default to std::cout when none is provided. I would also write the output operator operator<< as that is the normal way of printing in C++.

template<class T>
void LinkedList<T>::print(std::ostream& stream = std::cout) const;

std::ostream& operator<<(std::ostream& stream, LinkedList<T> const& data)
{
    data.print(stream);
    return stream;
}

That's an expensive print when done backwards.
But once you have the list reversed. Why not re-use your standard print function?

template<class T>
void LinkedList<T>::printBackwards(std::ostream& stream = std::cout) const
{
     LinkedList<T>  rev;
     for(Node<T>* curr = rev.head; curr != NULL; curr = curr->next)
     {    rev.insertToHead(curr->data);
     }
     rev.print(stream);
}

Finally. In the sumLists. Its fine upto the point. where one list is empty. But the second part where one list is empty is over complex and you have a lot of nested ifs. Why not check and do each list individually.

template<class T>
LinkedList<int> LinkedList<T>::sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2)
{
    // First part good.

    // Only one is true.
    // But if you look at the code it is neater.
    // and more self contained.
    while (curr1)
    {
        if (carry)
        {
            ResultList.insertToTail(curr1->data + carry);
            carry = 0;
            continue;
        }
        ResultList.insertToTail(curr1->data);
        curr1 = curr1->next;
    }

    while (curr2)
    {
        if (carry)
        {
            ResultList.insertToTail(curr2->data + carry);
            carry = 0;
            continue;
        }
        ResultList.insertToTail(curr2->data + carry);
        curr2 = curr2->next;
    }
}

You will also notice that the two loops are very similar. So you can break that code into a separate method and call it twice.

template<class T>
LinkedList<int> LinkedList<T>::sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2)
{
    // First part good.

    // Only one is true.
    // But if you look at the code it is neater.
    // and more self contained.
    AddStuffToListOne(curr1, ResultList);
    AddStuffToListOne(curr2, ResultList);

}
Vielen Dank, dass Sie sich die Zeit für eine gründliche Überprüfung genommen haben. Dies wird für mich bei der Verbesserung meiner C ++ - Programmierung sehr hilfreich sein. Yechiel Labunskiy vor 6 Jahren 0
Loki, wozu brauche ich die freistehende Swap-Funktion? Yechiel Labunskiy vor 6 Jahren 0
The free standing swap help for Kernig look-up (AKA ADL look-up). If you write: `swap(ll1, ll2);` where ll1 and ll2 are `LinkedList` Then it will using Kernig look-up to find your swap implementation which is better than the default swap. Martin York vor 6 Jahren 0
Ich bin der Meinung, dass ich Sie seit langem als Mitwirkender auf dieser Website nicht in den Chatroom (http://chat.stackexchange.com/rooms/8595/the-2nd-monitor) eingeladen habe. Fühlen Sie sich frei, zu kommen und mit den Stammgästen zu sprechen. :) syb0rg vor 6 Jahren 0
@LokiAstari Ich habe eine bescheidene Bitte an Sie. Fügen Sie Ihrer Antwort einen Abschnitt hinzu, um den vollständigen Klassencode nach der Überprüfung anzuzeigen. Nur zum Vergleich in beiden. Ihre Beurteilung ist sehr hilfreich und es ist für Anfänger von Vorteil, die Unterschiede im obigen Fragencode zu verstehen. Vielen Dank. Superman vor 4 Jahren 1
@Superman: Nicht in naher Zukunft. Ich bin im Moment etwas überlastet. Aber wenn Sie es tun, werde ich aus meiner Frage darauf verweisen. Martin York vor 4 Jahren 0
Überhaupt kein Problem. Ich mache das definitiv. Im Moment arbeite ich an einer weiteren Überprüfung einer Liste mit Anfängern. Dort könnten Sie meine Kommentare sehen. Ich habe die von Ihnen erläuterte Art und Weise codiert. Ich muss etwas Zeit damit verbringen, um alles zu verstehen. Danke für deine großartige Erklärung. Wenn Sie mich g ++ mit C ++ 11 referenzieren können, bin ich Ihnen dankbar. Ich bin nur wegen der Inkompatibilität der Version mit Fehlern konfrontiert. Ich bin neu in C ++. Superman vor 4 Jahren 0
8
utnapistim

Some observations:

Your data should (probably) be private. Otherwise, an enterprising developer will do this:

LinkedList<int> l;
// naively delete contents of l
delete l.head;

Node is an implementation detail of the list. It makes no sense to define it outside the class.

That means, the code should look like this:

template<class T>
class LinkedList
{
// private:
    struct Node // Node is a private implementation detail
    {
        T data;
        Node *next;
        Node(const T& d):data(d), next() {}
        Node(const Node& copyNode) : data(copyNode.data), next() {}

    private:
        Node& operator=(const Node&);
    };
    Node* head;
    Node* tail;

public:
    // ... rest of code here
};

After making head and tail private, you will need to add iteration and/or data retrieval API to your class.

When designing a class, consider how you will look at it from the perspective of client code, not how it is implemented (i.e. you are implementing a "list of instances of T", not a "list of instances of Node"). That means you should not have a constructor receiving a Node*, but a constructor receiving a T instance.

Your print and printBackwards functions should (probably) receive the output stream as a parameter (then, you can use the same code to print to a std::ostringstream, std::fstream, std::cout and so on).

Your copy&swap implementation of assignment should be written like this:

template<class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList byValList)
{
    using std::swap;        // enable ADL
    swap(*this, byValList); // implementation swaps by moving if there's a
                            // LinkedList<T>::LinkedList<T>(LinkedList<T>&&)
                            // defined; (consider defining it)

    return *this;
}

This function could use a std::move:

template<class T>
void LinkedList<T>::insertToTail(T val)
{
    Node<T> * newNode = new Node<T>(std::move(val)); // <<<<< 
    // ... 
}

For a POD-type T it's fine without it, but what happens if I write

LinkedList<std::string> l;
std::string s{' ', 10000};
l.insertToTail(s); // creates one copy of s for argument, and one for the node
`Implementation Swaps durch Verschieben`, wenn ein Bewegungskonstruktor vorhanden ist. Sonst macht es das durch Kopieren. Standardmäßig gibt es keinen Verschiebungskonstruktor. Martin York vor 6 Jahren 2
@LokiAstari, das hatte ich nicht gewusst (habe eine positive Bewertung :)). utnapistim vor 6 Jahren 0
0
Roni Kupershtok

Ich vermute, es gibt einen Fehler in sumLists:

Der folgende Teil

if (carry)
{
    if (curr1)
        ResultList.insertToTail(curr1->data + carry);
    if (curr2)
        ResultList.insertToTail(curr2->data + carry);
    carry = 0;
    continue;
}

sollte durch ersetzt werden

if (carry)
{
    if (curr1)
    {
        ResultList.insertToTail(curr1->data + carry);
        curr1 = curr1->next;
    }
    if (curr2)
    {
        ResultList.insertToTail(curr2->data + carry);
        curr2 = curr2->next;
    }
}
Hallo, schöner Fang für eine erste Antwort :) Vielleicht würde es auch OP weiterhelfen, wenn du erklärst, was du für den Fehler hältst, würde es auch eine bessere Antwort geben IEatBagels vor einem Jahr 0