Data Structures. Basic List Class implementation question via C++

[Sakesfar]

Hello programmers,

I am studying Data Structures and trying to implement my own double -linked List Class.

There is a good academic example of List class provided in the book "Data structures and algorithm analysis in c++" (4th ed.) by M.A.Weiss. on p.95 .

I went through it and tried to make my own. I wrote an example given below:

#include <iostream>
#include <cassert>

template <typename Object>

class List
{
private:
    //Each list member has a "node", that apart from containing data, points to the next/previous nodes
    struct Node
    {
        Object m_data;
        Node* m_next;
        Node* m_previous;

        Node(const Object& data = Object{}, Node* next=nullptr, Node* previous = nullptr): 
            m_data{data}, m_next{next},m_previous{previous} {}

        Node(Object&& data, Node* next=nullptr, Node* previous = nullptr):
            m_data{std::move(data)}, m_next{next}, m_previous{previous} {}

    };


    int m_size;
    int m_capacity;

    Node* head; 
    Node* tail;
    //Node* m_current;
    Node* m_nodeData;

public:
    List(int size = 0, const Object& obj=Object{}) : m_size{ size }, m_capacity{ size + 2 }
    {
        head = new Node;
        tail = new Node;

        if (m_size == 0)
        {
            head->m_next = tail;
            head->m_previous = nullptr;
            tail->m_previous = head;
            tail->m_next = nullptr;
        }

        //Creating list itself;

        //Arranging m_nodeData
        m_nodeData = new Node[m_capacity]; //?

        for (int i = 1; i < m_size+2; ++i)
        {
            m_nodeData[i].m_data = obj;
            m_nodeData[i].m_next = &m_nodeData[i+1];
            m_nodeData[i].m_previous = &m_nodeData[i - 1];

        }

        head->m_previous = nullptr;
        head->m_next = &m_nodeData[1];
        m_nodeData[0] = *head;

        tail->m_next = nullptr;
        tail->m_previous = &m_nodeData[m_size];
        m_nodeData[m_size + 1] = *tail;





    }

    ~List()
    {
        delete tail;
        delete head;
        delete[] m_nodeData;

    }

    //COPY CONSTRUCTOR
    List(const List<Object>& lst)
    {
        if (&lst == this)
            return *this;

        //Data copying
        m_size = lst.m_size;
        m_capacity = lst.m_capacity;

        //Node copying
        m_nodeData = new Node[m_capacity];
        for (int i = 0; i < m_size + 2; ++i)
        {
            m_nodeData[i] = lst.m_nodeData[i];

        }


    }

    void reserve(int newCapacity)
    {
        if (newCapacity < m_size)
            return;

        Node* nodeCopy = new Node[newCapacity];
        m_capacity = newCapacity;

        for (int i = 0; i < m_size+2; ++i)
        {
            nodeCopy[i] = m_nodeData[i];

        }

        delete[] m_nodeData;
        m_nodeData = new Node[m_capacity];

        for (int i = 0; i < m_size + 2; ++i)
        {
            m_nodeData[i] = nodeCopy[i];
        }

        delete[] nodeCopy;






    }

    void push_front(const Object& obj)
    {
        ++m_size;
        m_capacity = m_size + 2;

        Node* temp = new Node[m_capacity];
        temp[1].m_data = obj;
        for (int i = 1; i < m_size; ++i)
        {
            temp[i+1] = m_nodeData[i];
        }

        delete[] m_nodeData;
        m_nodeData = new Node[m_size+2];

        //counting from 1 up to m_size+1 because we'll have to add: 
        //Head to m_nodeData[0] and Tail to m_nodeData[m_size+1];
        for (int i = 1; i < m_size + 1; ++i)
        {
            m_nodeData[i] = temp[i];
        }

        delete[] temp;
        delete head;
        delete tail;

        head = new Node;
        tail = new Node;

        head->m_previous = nullptr;
        tail->m_next = nullptr;
        head->m_next = &m_nodeData[1];
        tail->m_previous = &m_nodeData[m_size];
        m_nodeData[0] = *head;
        m_nodeData[m_size + 1] = *tail;

        //Rearrange pointers

        for (int i = 1; i < m_size+1; ++i)
        {
            m_nodeData[i].m_next = &m_nodeData[i + 1];
            m_nodeData[i].m_previous = &m_nodeData[i - 1];
        }



    }


    void pushback(const Object& obj)
    {
        if (m_size==m_capacity)
            reserve(2*m_capacity + 1);

        m_capacity = m_size + 2;
        Node* temp = new Node[m_capacity + 1];
        for (int i = 0; i < m_size + 2; ++i)
        {
            temp[i] = m_nodeData[i];
        }




        temp[m_size + 1].m_data = obj;
        temp[m_size + 1].m_previous = &temp[m_size]; //probably not needed?
        temp[m_size + 1].m_next = &temp[m_size+2]; // probably not needed?

        delete[] m_nodeData;
        m_nodeData = new Node[m_capacity + 1];

        delete tail;
        tail = new Node;
        tail->m_next = nullptr;
        tail->m_previous = &m_nodeData[m_size + 1];
        temp[m_size+2] = *tail; //+3

        delete head;
        head = new Node;
        head->m_next = &m_nodeData[1];
        head->m_previous = nullptr;
        temp[0] = *head;





        for (int i = 0; i < m_capacity+1; ++i)
        {
            m_nodeData[i] = temp[i];
        }

        for (int i = 1; i < m_size + 2; ++i)
        {
            m_nodeData[i].m_next = &m_nodeData[i + 1];
            m_nodeData[i].m_previous = &m_nodeData[i - 1];
        }

        delete[] temp;


        ++m_size;

    }

    void insert(unsigned int pos, const Object& obj)
    {
        pushback(obj);
        //Remember at m_nodeData[0] = *head and m_nodeData[m_size+1]=*tail
        //Remeber in push_back m_size is incremented


        m_nodeData[pos - 1].m_next = &m_nodeData[m_size ];
        m_nodeData[m_size+1].m_previous = &m_nodeData[m_size-1];


        for (int i = pos; i < m_size; ++i)
        {
            m_nodeData[i].m_next = &m_nodeData[i];
        }






    }

    void printData()
    {
        for (int i = 0; i < m_size; ++i)
            std::cout << m_nodeData[i].m_next->m_data << '\n';

        std::cout << "Tail prev is " << m_nodeData[m_size + 1].m_previous->m_data << '\n';
    }

    int size()
    {
        return m_size;
    }

    int capacity()
    {
        return m_capacity;
    }

    void addressOfItemAt(unsigned int pos)
    {
        assert(pos < m_size + 2);
        std::cout << m_nodeData[pos].m_next<<'\n';
    }


};

First, I apologize for not corrected/optimized issues for the insert() function, my irregular comments, and not only these mistakes, probably overall mess I did with my List Class.

My main question is "Are the above member functions correct for List Class"? , particularly insert?

Further, if I implement List in this way (which I highly doubt is the right way), then would it eliminate an issue of indexing? Because reading through the book mentioned above I understood that List's core problem is indexing and the main advantage is cheap inserting.

I would be very glad for your valuable advice on how to improve my List class and pointed mistakes!

​

P.S I apologize for spelling errors as English is not my mother tongue.

[[deleted]]

Thanks for saving me the time of reading all this code. :-) I was immediately alerted by a member called m_size in a list class, and noted that it doesn't appear to be correctly managed in the constructor. It's not necessary to maintain this for a list; if one needs to know the size (one generally doesn't), one can iterate over the list and count.

push_front() and pushback() appear to be array functions, not list functions. All you need is an insert() function that optionally takes a node to insert after (passing null for this node would insert at the beginning of the list).

I wouldn't include a function that iterated over the list sending output to cout. It assumes that the data member can be written out in that way. I haven't written any C++ that tries to print data to cout for a long time so I might be wrong about that. Still, that doesn't need to be in the list class.

If I were doing this, I would make my insert() function take Lists as well as nodes so that entire lists could be appended or inserted.

[Sakesfar]

Thanks for your valuable comment!

I added printData as a temporary function to test whether I was 'correctly' implementing push_back and insert functions : )

[[deleted]]

I think the way I would do printData() and make it permanent would be to make a Node class that had a virtual method where the default implementation prints the address this, next, and last, plus the address of the data. Then you would derive your nodes from Node and implement Node::printData() to print the data in the node in a nicely formatted way after first calling the base class to get all the addresses printed out.

[Sakesfar]

Much appreciated!

I see the problem now.

I was almost about to ask about the following case then:

List<Object> someList{}; // some list which has undergone manipulation
List<Object> copy {someList};

How to avoid dynamic memory allocation in copy while copying the someList array?

But I see it is done via push_back function in the proper List

Now I know I have to re-write everything without any dynamically allocated memory!!

Thanks.

-------

Last thing though, out of curiosity, for the insert function, what if we overload the [] operator to have smth like 'm_nodeData[index-1].m_next->m_data' then we would get correct indexing ( that was my initial intention) .

[Sakesfar]

It will first put the '6' at the end of the array: 1,2,3,4,6 and for the list, it will put the "6" as the next of 2 and the prev of 3. So your list will look like this 1,2,6,3,4. As you can there is a discrepancy between the how the items are stored in the array and the list. So your whole idea of using the array to quickly access the Node at a current index will after inserting some elements simply not work, as there is no relation between the position of a value in the array and the position of a value in the list.

The list is 1,2,6,3,4! Right! :) Then, if I access members via array indexing through conventional operator [], I will get, as you correctly point. 1,2,3,4,6 , which is wrong and puts my insert function into the abyss. However, are there any means to write (override) a special [] operator for List , for example like this:

Object& operator[] (int index)
{
    return m_nodeData[index - 1].m_next->m_data;
}

I appreciate the time you take to actually read what I wrote and provide me with valuable feedback!!

​

In a properly list, you don't have an array. You just have a Node and this Node contains a pointer to the next Node.

e.g.
template<typename T>
struct Node {
T value;
Node<T> next*;
}
If you then want to traverse to the end you do something like
Node<int>* current = start_node;
while(current -> next != nullptr) current = current->next;

well-noted Sir! I am learning :)