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
Jun 21, 2022 in C++ by Nicholas
 • 7,760 points • 944 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 Jun 21, 2022 by Damon
 • 4,960 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, 2022 in C++ by pranav
 • 2,590 points • 981 views
0 votes
0 answers

Selection sort in C++ (modified) not working for all cases

I was attempting to tweak the selection sort code in C++ in order to test the results.  My updated code is as follows: #include<bits/stdc++.h> using namespace std; int main() { ...READ MORE

Jun 29, 2022 in C++ by Damon
 • 4,960 points • 511 views
0 votes
0 answers

Difference between for loop and the range based loop in C++

The distinction between a for loop and ...READ MORE

Jul 11, 2022 in C++ by Nicholas
 • 7,760 points • 603 views
0 votes
0 answers

Insert object at index of vector c++

I have to add a new item to the existing object vector.  Although I am aware that an iterator must be used, I am not entirely sure how it operates. I need to insert a new item by name in the precise index that I found after some searching into an alphabetically sorted vector.  I have this, then. vector<Person>people; int index =54; Person temp; people.push_back(temp);//insert at end of ...READ MORE

Aug 5, 2022 in C++ by Nicholas
 • 7,760 points • 746 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,020 points • 704 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,020 points • 2,431 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 • 1,465 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,740 points • 1,889 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, 2022 in C++ by Damon
 • 4,960 points • 907 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, 2022 in C++ by Damon
 • 4,960 points • 708 views
webinar REGISTER FOR FREE WEBINAR X
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP
"PMP®","PMI®", "PMI-ACP®" and "PMBOK®" are registered marks of the Project Management Institute, Inc. MongoDB®, Mongo and the leaf logo are the registered trademarks of MongoDB, Inc.