5
\$\begingroup\$

I made a custom linked list implementation. I am trying to improve my coding style, any remarks or suggestions are welcome.

template<typename T>
class LinkedListElement
{

private:

    T *content_;
    LinkedListElement<T>* next_;
    LinkedListElement<T>* previous_;


public:

    T* getContent() { return content_; }
    LinkedListElement<T>* getNext() { return next_; }
    LinkedListElement<T>* getPrevious() { return previous_; }

    LinkedListElement()
    {
        next_ = nullptr;
        previous_ = nullptr;
        content_ = new T();
    }

    ~LinkedListElement()
    {
        delete content_;
    }

    LinkedListElement(T content, LinkedListElement<T> * next, LinkedListElement<T> * previous)
    {
        next_ = nullptr;
        previous_ = nullptr;

        setContent(&content);
        setPrevious(previous);
        setNext(next);
    }

    void setContent(T *content)
    {
        content_ = new T(*content);
    }

    void setNext(LinkedListElement<T> * next)
    {
        next_ = next;
    }

    void setPrevious(LinkedListElement<T> * previous)
    {
        previous_ = previous;
    }

    LinkedListElement<T>* insert(T content)
    {
        LinkedListElement<T>* newListElement = new LinkedListElement<T>();
        newListElement->setContent(&content);
        newListElement->setNext(getNext());
        newListElement->setPrevious(this);
        setNext(newListElement);
        newListElement->getNext()->setPrevious(newListElement);
        return newListElement;
    }

    void deleteElement()
    {
        if (getPrevious() && getNext())
        {
            getPrevious()->setNext(getNext());
            getNext()->setPrevious(getPrevious());
        }
        else if (!getPrevious() && getNext())
            getNext()->setPrevious(nullptr);
        else if (getPrevious() && !getNext())
            getPrevious()->setNext(nullptr);

        delete this;
    }
};
/**
 *  templated linked list class.
 *  usage: LinkedList<your class>; 
 */
template<typename T>
class LinkedList
{

private:

    LinkedListElement<T>* first_{ nullptr };
    LinkedListElement<T>* last_{ nullptr };

public:

    LinkedListElement<T>* getFirst() { return first_; }
    LinkedListElement<T>* getLast() { return last_; }

    void setFirst(LinkedListElement<T>* first) { first_ = first; }
    void setLast(LinkedListElement<T>* last) { last_ = last; }

    ~LinkedList()
    {
        LinkedListElement<T>* newIndex = nullptr;
        for (LinkedListElement<T>* index = first_; index != last_; index = newIndex)
        {
            newIndex = index->getNext();
            delete index;
        }
        delete last_;
    }


    void add(T content)
    {
        LinkedListElement<T>* newElement = new LinkedListElement<T>(content, nullptr, last_);

        /* adding to an existing list */
        if (first_ != nullptr)
        {
            getLast()->setNext(newElement);
            last_ = newElement;
        } else 
        /* the list was empty, so let's initalize it with this first object */
        {
            first_ = newElement;
            last_ = newElement;
        }
    }
    void remove(T content)
    {
        LinkedListElement<T>* newIndex = nullptr;
        for (LinkedListElement<T>* index = first_; index != last_; index = newIndex)
        {
            newIndex = index->getNext();
            if (*(index->getContent()) == content)
            {
                if (index == first_)
                    first_ = index->getNext();
                if (index == last_)
                    last_ = index->getPrevious();
                index->deleteElement();
            }
        }
    }

    void destroy()
    {
        LinkedListElement<T>* newIndex = nullptr;
        for (LinkedListElement<T>* index = first_; index != last_; index = newIndex)
        {
            newIndex = index->getNext();
            delete index;
        }
    }

    void display()
    {
        for (LinkedListElement<T>* index = first_;; index = index->getNext())
        {
            index->getContent()->display();
            if (index == last_)
                break;
        }
    }
};

Here's my main:

#include "Animal.h"
#include "LinkedListElement.h"
#include "LinkedList.h"

int main(void)
{
    Animal c("tiger");
    Animal b("lion");
    Animal d("cow");

    LinkedList<Animal> animals; 
    animals.add(c);
    animals.add(b);
    animals.add(d);

    animals.remove(c);

    animals.add(Animal("ozelot"));

    animals.display();

    LinkedList<int> integers;

    integers.add(5);

    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

    return 0;
}

And the Animal class I used for testing:

#include <string>

class Animal
{

private:

    std::string name_{ "not set" };

public:
    Animal() = default;
    Animal(std::string name) : name_{ name } {};

    void setName(std::string name);
    std::string getName() { return name_; }

    void display();

    bool operator==(Animal& theOtherAnimal);
    bool compareName(std::string name);
};

#include <iostream>

void Animal::setName(std::string  name)
{
    name_ = name ;
}

void Animal::display()
{
    std::cout << name_ << '\n';
}

bool Animal::operator==(Animal& theOtherAnimal)
{
    if (std::strcmp(name_.c_str(), theOtherAnimal.getName().c_str()) == 0)
        return 1;
    else
        return 0;
}

bool Animal::compareName(std::string name)
{
    if (name_ == name)
        return true;
    return false;
}
\$\endgroup\$
1
\$\begingroup\$

First of all: your coding style seems good to me. I presume that you didn't include all comments as more comments are of course necessary. But the code itself looks OK to me; it is easy to read.

Design issues:

  1. You are allowing direct access to the elements rather than just the content. This allows the user to create any kind of structure, including lists that keep going round.
  2. Instead of going through the elements by exposing them, I think you should create an iterator that allows you to go through the elements and then retrieve the contents.
  3. If you remove the first element with a specific content then you should probably call that function removeFirst. Note that you are combining two things here: searching for an element and removing that element.
  4. Although a linked list is generally not fast when it comes to indexing elements, you could still implement indexing. Keeping the size is definitely a good idea. This is obviously a bit of problem if you allow direct access to the elements.
  5. Functions like display() are dangerous as you don't know the size of the list or its elements (besides that, how do you know that T enables this display() function, am I missing something?).
  6. If you allow direct access to the elements then you may be able to delete the element while an outside user still holds onto a reference to it.

Coding problems:

  1. You are sometimes assigning a null pointer to a variable, even though you immediately assign it to something else directly after. This kind of double assignment is generally not required.
  2. You are sometimes calling public methods from other public methods. This is dangerous if you allow overriding your class.
  3. Sometimes you are calling public methods instead of directly assigning the variables. Calling setNext is not necessary; it won't do anything but setting the next pointer.
\$\endgroup\$
  • \$\begingroup\$ Thanks, Maarten. 1. I see. I suppose there's really nothing in the LinkedListElement class that needs to be public, provided that I define LinkedList as a friend class and not all the methods in LinkedList need to be public either. 2. Not comfortable with iterators yet, but I'll give it a try. 3. yeah, probably a good idea to disentangle find from delete \$\endgroup\$ – Harry Maierhofer May 29 '18 at 18:11
  • \$\begingroup\$ 5. yes, I dont know whether T has a display method or not. I'm having trouble conceptualizing this type of problem, for example I also cant think of a way to look for a specific field value and then delete or sort based on whether it has been found in the content. Tbh, I dont know whether the content class has the comparison operator overridden which I need for the "seek and delete" function either Coding problem 3: my thinking was that at a later point, there might be some checks implemented in setNext. Is it generally not advisable to use public setters from within the class itself? \$\endgroup\$ – Harry Maierhofer May 29 '18 at 18:13
  • \$\begingroup\$ I'd say no. In effective Java Joshua Bloch warns against this kind of code as an override could change the functionality of the method. This however goes as much for any OO language. Personally I think it is a bit overzealous, so it is definitely not the most important part of my advice. You can always extract the functionality of the public method and put it in a private method which you call from the public method. That however does lead to a significant increase in boilerplate code. Note that a lot of input checks may not need to be performed from within the class. \$\endgroup\$ – Maarten Bodewes May 29 '18 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.