I am implementing doubly linked list in C++, and I have been trying to make my insert method work without success. The class should contain two node pointers: one to the head of the list, and one to the tail of the list. If the list is empty, they should both point to nullptr. The insert method should take a value at given index and add it to the list, increasing its size with one element. my code is:
#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
I tried to fix all of your methods, probably succeded, at least current test example is printing correct 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]