TransWikia.com

Optimizing a linked list

Code Review Asked by qela on October 27, 2021

I wrote a linked list class and don’t know how to optimize it, please suggest some ideas for optimizing and fixing possible memory leaks.

#define indexTooLarge -1
template <typename T>
class LincedList
{
public:
    LincedList(){}
    template<typename... Types>
    LincedList(T value,Types... values) :  LincedList(values...)
    {
        push_front(value);
    }
    LincedList(T value)
    {
        push_front(value);
    }
    ~LincedList()
    {
        clear();
    }
    void push_back(T value_a)
    {
        if(tail == nullptr)
        {
            tail = new Node(nullptr,value_a);
            head = tail;
            m_size++;
            return;
        }
        tail->next = new Node(nullptr,value_a);
        tail = tail->next;
        m_size++;
    }
    void push_front(T value_a)
    {
        if(head == nullptr)
        {
            head = new Node(nullptr,value_a);
            tail = head;
            m_size++;
            return;
        }
        head = new Node(head,value_a);
        m_size++;
    }
    void clear()
    {
        Node *buffer;
        for(int i = 0;i<m_size;i++)
        {
            buffer = head;
            head = head->next;
            delete buffer;
        }
        m_size = 0;
    }
    void remove(unsigned int index)
    {
        if(index >= m_size)
            throw indexTooLarge;
        Node *currectNode = head;
        for(int i = 0; i < index-1;i++)
            currectNode = currectNode->next;
        Node* buffer = currectNode->next;
        currectNode->next = currectNode->next->next;
        delete buffer;
        m_size--;
    }
    void remove(unsigned int index,unsigned int lenght)
    {
        if(index+lenght >= m_size)
            throw indexTooLarge;
        Node *currectNode = head;
        for(int i = 0; i < index-1; i++)
            currectNode = currectNode->next;
        Node* buffer = currectNode;
        currectNode = currectNode->next;
        for(int i = 0; i < lenght; i++ )
        {
            Node* buffer2 = currectNode;
            currectNode = currectNode->next;
            delete buffer2;
        }
        buffer->next = currectNode;
        m_size -= lenght;
    }
    T& operator[](unsigned const int &index)
    {
        if(index >= m_size)
            throw indexTooLarge;
        if(index == m_size-1)
            return tail->value;
        Node *currectNode = head;
        for(unsigned int i = 0; i < index;i++)
            currectNode = currectNode->next;
        return currectNode->value;
    }
    void operator=(const LincedList &C1)
    {
        head->value = C1.head->value;
        Node *currectNode = new Node(nullptr,C1[1]);
        Node *C1CurrectNode = C1[1];
        head->next = currectNode;
        for(int i = 2; i < m_size; i++)
        {
            C1CurrectNode = C1CurrectNode->next;
            currectNode->next = new Node(nullptr,C1CurrectNode->value);
            currectNode = currectNode->next;
        }
        tail->value = C1.tail->value;
    }
    unsigned int size()
    {
        return m_size;
    }
private:
    struct Node
    {
         Node* next;
         T value;
         Node(Node* next_a, T value_a) : next(next_a) , value(value_a)
         {}
    };
    unsigned int m_size = 0;
    Node* head = nullptr;
    Node* tail = nullptr;
}; 

#include <iostream>
int main()
{
    LincedList<int> ll(0,1,2,3);
    std::cout << ll[1] << std::endl; //writes to console 1
    ll.remove(1); //removes the element at index 1
    std::cout << ll[1] << std::endl; //writes to console 2
    ll.push_back(4);//adds to the end 4
    ll.push_front(5);//adds 5 to the beginning
    std::cout << ll.size() << std::endl; //writes to console 5
    ll.remove(1,2); //remove all 2 to 3 elements
    std::cout << ll[1] << std::endl ; //writes to console 3
    return  0;
}

3 Answers

You should make sure to follow the rule of three/five/zero.

In your case we have a user defined destructor, which clears the list by deleting all nodes. Problems arise now when you make a copy of a list:

LincedList<int> one(1,2);
LincedList<int> two(one); // a copy?

When that scope ends, both lists try to delete the same nodes; resulting in "double free" and thus undefined behavior. (example on ideone)

Therefore you should provide a user defined copy constructor and a user defined copy assignment operator with a suitable implementation. A suitable implementation could be to create copies of all nodes. A suitable implementation could also be to disallow copies of lists being made (by deleting the copy constructor and copy assignment operator). If your lists can be copied, then it makes probably sense to allow list (contents) to be also moved from one list to the other; reducing the needs for copies. Therefore you should then also implement a user defined move constructor and a user defined move assignment operator.

Or, to follow the rule of zero, you could also use std::unique_ptr<Node> instead of a raw pointer to the head of the node as well as std::unique_ptr<Node> instead of a raw pointers to the next nodes. Then memory would be taken care of itself (no need to write a destructor!) and copies would be disallowed.

Answered by Daniel Jour on October 27, 2021

In addition to what Reinderien posted:

Look at std::forward_list

Your linked list is a single-linked list, the closes equivalent in the standard library is std::forward_list. You will notice from the documentation of std::forward_list that it doesn't implement a push_back(), and its erase() function only takes iterators, not indices. All this is to keep this data structure light and focused only on the properties that a single-linked list has: inserting and removing at the head is fast, and you can iterate over it in one direction. There is no operator[] overload.

Slower operations, like finding the node at a given index, are left to other functions such as std::advance(). And this makes it clear that if you want to do something like access random elements, you are better off using a different data structure, such as a std::vector.

Spelling

There are some spelling errors in your code:

  • LincedList -> LinkedList
  • currectNode -> currentNode (and some variants)

Maybe English is not your native language, that's fine. There are some tools that can help you find and fix common spelling errors in source code, like codespell. Consider running them on your code from time to time.

Don't do bounds checking

Well, you asked how to improve performance. In C++ it is normal for standard containers to not do any bounds checking. The burden of bounds checking is placed on the caller. This avoids some overhead every time your functions are called.

Not throwing exceptions also allows code using your class to be compiled without exceptions enabled, which can have various benefits.

Answered by G. Sliepen on October 27, 2021

Spelling

  • LincedList -> LinkedList;
  • currectNode -> currentNode;
  • lenght -> length.

Factor out iteration

Make a private utility method to do this:

    for(unsigned int i = 0; i < index;i++)
        currectNode = currectNode->next;
    return currectNode;

given the number of times you do it.

Const methods

unsigned int size()

should be

unsigned int size() const

and you should offer a similar const wrapper to your operator[].

Answered by Reinderien on October 27, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP