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
CodePudding user response：
Well the obvious problem in insert is that it calls get_node which tests the size member but nothing updates size anywhere.
However, fundamentally, your append function is wrong. It should be a class invariant that a linked list is either empty and has both its head and tail be nullptrs, or it should have a valid head and a valid tail.
Your append function does not enforce this invariant. It tries to work on two cases, one where the head is null and another where the tail is null. Ask yourself if those two cases are meaningful.
Rewrite append such that a list either is empty or has a valid head and tail.
CodePudding user response：
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]