insert method for doubly linked list C

0 votes

I am creating a doubly linked list in C++ and have been unsuccessful in getting my insert method to operate. 

The class should have two node pointers: one to the top of the list and one to the bottom. 

They should both point to nullptr if the list is empty. 

The insert method should add a value at the specified index to the list, increasing its size by one member. 

My code is as follows:

#include <iostream>
#include <vector>
using namespace std;

struct Node
{
    int value;
    Node *next;
    Node *prev; //previous node pointer
    Node(int v) : value(v), next(nullptr), prev(nullptr) {}
};

class LinkedList
{
private:
    Node *head;
    Node *tail;
    Node *prev;

    Node *get_node(int index)
    {
        if (index < 0 or index >= size)
        {
            throw range_error("IndexError: Index out of range");
        }

        Node *current = head;
        for (int i = 0; i < index; i++)
        {
            current = current->next;
        }
        return current;
    }

public:
    int size;
    LinkedList()
    {
        head = nullptr;
        tail = nullptr;
    }

    int length()
    {
        Node *current = head;
        int count = 0;

        while (current != nullptr)
        {
            count++;
            current = current->next;
        }

        cout << "Length of list is " << count << endl;
        return count;
    }

    void append(int value)
    {
        Node *new_node = new Node(value);

        if (head == nullptr)
        {
            head = new_node;
            head->prev = nullptr;
            new_node->next = tail;
        }
        else if (tail == nullptr)
        {
            tail = new_node;
            new_node->next = nullptr;
        }
    }

    void print()
    {
        Node *current = head;
        Node *prev;
        cout << "[";
        if (current->next == NULL)
        {
            cout << current->value;
            cout << "]";
        }
        else
        {

            while (current->next != nullptr)
            {
                cout << current->value;
                cout << ", ";
                prev = current;
                current = current->next;
            }
            cout << current->value << "]" << endl;
        }
    }

    ~LinkedList()
    {
        Node *current;
        Node *next;

        current = head;

        while (current != nullptr)
        {
            next = current->next;
            delete current;
            current = next;
        }
    }

    int &operator[](int index)
    {
        return get_node(index)->value;
    }

    void insert(int val, int index)
    {
        Node *current = new Node(val);
        Node *prev = get_node(index - 1);
        Node *next = current->next;
        prev->next = current;
    }
};

int main()
{
    LinkedList a;
    a.append(1); // Appending elements to list
    a.append(2);
    a.append(3);
    a.append(4);
    a.append(5);
    a.print(); // [1, 2, 3, 4, 5]
    a.insert(3, 1);
    a.print(); 
};

This gives me the error

libc++abi.dylib: terminating with uncaught exception of type std::range_error: IndexError: Index out of range
Abort trap: 6
6 days ago in C++ by Nicholas
• 2,360 points
11 views

1 answer to this question.

0 votes

I attempted to repair all of your methods, and I believe I succeeded; at least, the current test example prints the proper answer:

#include <iostream>
#include <vector>
using namespace std;

struct Node
{
    int value;
    Node *next;
    Node *prev; //previous node pointer
    Node(int v) : value(v), next(nullptr), prev(nullptr) {}
};

class LinkedList
{
private:
    Node *head;
    Node *tail;

    Node *get_node(int index)
    {
        if (index < 0)
            throw range_error("IndexError: Index out of range");

        Node *current = head;
        for (int i = 0; i < index; i++) {
            if (!current)
                break;
            current = current->next;            
        }

        if (!current)
            throw range_error("IndexError: Index out of range");

        return current;
    }

public:
    LinkedList()
    {
        head = nullptr;
        tail = nullptr;
    }

    int length()
    {
        Node *current = head;
        int count = 0;

        while (current != nullptr)
        {
            count++;
            current = current->next;
        }

        cout << "Length of list is " << count << endl;
        return count;
    }

    void append(int value)
    {
        Node *new_node = new Node(value);

        if (head == nullptr)
        {
            head = new_node;
            tail = head;
        }
        else
        {
            tail->next = new_node;
            new_node->prev = tail;
            tail = new_node;
        }
    }

    void print()
    {
        Node *current = head;
        cout << "[";
        if (current->next == NULL)
        {
            cout << current->value;
            cout << "]";
        }
        else
        {

            while (current->next != nullptr)
            {
                cout << current->value;
                cout << ", ";
                current = current->next;
            }
            cout << current->value << "]" << endl;
        }
    }

    ~LinkedList()
    {
        Node *current;
        Node *next;

        current = head;

        while (current != nullptr)
        {
            next = current->next;
            delete current;
            current = next;
        }
    }

    int &operator[](int index)
    {
        return get_node(index)->value;
    }

    void insert(int val, int index)
    {
        Node *node = new Node(val);
        if (index == 0) {
            if (!head) {
                head = node;
                tail = head;
            } else {
                node->next = head;
                head->prev = node;
                head = node;
            }
        } else {
            Node *prev = get_node(index - 1);
            Node *next = prev->next;
            prev->next = node;
            node->prev = prev;
            node->next = next;
            if (next)
                next->prev = node;
            if (prev == tail)
                tail = node;
        }
    }
};

int main()
{
    LinkedList a;
    a.append(1); // Appending elements to list
    a.append(2);
    a.append(3);
    a.append(4);
    a.append(5);
    a.print(); // [1, 2, 3, 4, 5]
    a.insert(3, 1);
    a.print(); 
};

Output:

[1, 2, 3, 4, 5]
[1, 3, 2, 3, 4, 5]
answered 6 days ago by Damon
• 3,380 points

Related Questions In C++

0 votes
1 answer

The Definitive C++ Book Guide and List

For Beginner (includes those without coding experience) Programming: ...READ MORE

answered Jun 6 in C++ by pranav
• 2,320 points
21 views
0 votes
1 answer

Declare abstract class in c++

An abstract class is one that is intended to be used as a base class .  At least one pure virtual function exists in an abstract class.  A pure virtual function is declared in the class declaration by using a pure specifier (= 0) in the declaration of a virtual member function. Here is an example of an abstract class: class AB { public: virtual void f() ...READ MORE

answered May 31 in C++ by Damon
• 3,380 points
19 views
0 votes
1 answer

What data structure is inside std::map in C++?

An associative container is std::map. The standard's ...READ MORE

answered May 31 in C++ by Damon
• 3,380 points
19 views
0 votes
1 answer

C++ `this` pointer

Pointer variables are used to store the ...READ MORE

answered May 31 in C++ by Damon
• 3,380 points
13 views
0 votes
1 answer

setuptools: build shared libary from C++ code, then build Cython wrapper linked to shared libary

There is a seemingly undocumented feature of setup that ...READ MORE

answered Sep 11, 2018 in Python by Priyaj
• 58,080 points
190 views
0 votes
1 answer

setuptools: build shared libary from C++ code, then build Cython wrapper linked to shared libary

There is a seemingly undocumented feature of setup that ...READ MORE

answered Sep 21, 2018 in Python by Priyaj
• 58,080 points
1,368 views
0 votes
1 answer

How to pass large records to map/reduce tasks?

Hadoop is not designed for records about ...READ MORE

answered Sep 25, 2018 in Big Data Hadoop by Frankie
• 9,830 points
787 views
0 votes
1 answer

Invalid method parameters for eth_sendTransaction

params needs to be an array, try {"jsonrpc":"2.0","method":"eth_se ...READ MORE

answered Sep 28, 2018 in Blockchain by digger
• 26,720 points
581 views
0 votes
1 answer

Simple linked list in C++

This is the most basic example I can think of in this situation, and it has not been tested.  Please keep in mind that this violates some C++ best practises and deviates from the norm (initialize lists, separation of declaration and definition, and so on).  But those aren't topics I can discuss here. #include <iostream> using namespace std; class LinkedList{ ...READ MORE

answered Jun 2 in C++ by Damon
• 3,380 points
15 views
0 votes
1 answer

The Definitive C++ Book Guide and List

Introductory, no previous programming experience Book Author(s) Description review C++ Primer* * Not ...READ MORE

answered Jun 14 in C++ by Damon
• 3,380 points
9 views
webinar REGISTER FOR FREE WEBINAR X
Send OTP
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP