Circular Doubly Linked List - Segmentation fault: 11

[btoohey4]

I'm trying to implement a circular doubly linked list but I keep getting a segmentation fault: 11 error (I believe it's because of the add and delete functions). I have no idea whether my code is even close, but I can't get past this error to test it properly. This is the class involved:

(Circular_DLList.cc)

#include "Circular_DLList.h"
#include <iostream>
using namespace std;

Circular_DLList::~Circular_DLList()
{
	while(!is_empty())
	{
		delete_from_tail();
	}
}

void Circular_DLList::add_to_tail(int a)
{
	if (is_empty()) {
		tail = new DLLNode(a);
		tail->next = tail;
	}
	else {
		tail->next = new DLLNode(a, tail->next);
	}
}

int Circular_DLList::delete_from_tail()
{
	if(!is_empty()) 
	{
		int a = tail->info;
		tail = tail->prev;
		tail->next = null;
		return a;
	}
	else
	{
		tail = 0;
	}
	return a;
}

bool Circular_DLList::is_in_list(int a) 
{
	for (DLLNode* p = tail; p-> != tail && !(p->info ==a); p = p->next) {
		p->info == a;
	}
	return a;
}

void Circular_DLList::print_list()
{
	for (DLLNode* p = tail->next; p != tail; p = p->next) {
		std:: cout << p->info << " ";
	}
	std::cout << tail->info << std::endl;

}

[dhayden]

I see some code for a doubly linked list, but it doesn't appear to be circular. In a circular list, the last node points back to the first one rather than to NULL.

I see you setting next pointers, but not prev pointers.

I see you setting the tail pointer, but not the head pointer. Any time you find yourself changing the tail pointer, there is probably a case where the head pointer changes too.
- in add_to_tail when adding to an empty list
- in delete_from_tail when deleting the last node in the list.

What is line 43 supposed to do?

Line 50: The program will crash if tail is null (i.e., this list is empty).

[btoohey4]

Thanks heaps for replying
I'm not attempting to point to null, rather trying to set it to null after deleting. Also I'm not supposed to have a head pointer as it's circular, if I need to access head I'm to use tail->next, which is why I'm finding it so tricky.

I'm just going to just delete the last two methods and start again with those.

This is my main class:

int main() {
	Circular_DLList list;

	list.add_to_tail(1), list.add_to_tail(2), list.add_to_tail(3), list.add_to_tail(4);
	
	list.is_in_list(2);
	list.print_list();

	return 0;
}

When I run this, (after commenting out the delete method as it causes the segmentation error) I get an output of '4 1' and can't quite figure out what's causing some to print and others not.

[dhayden]

Can you post Circular_DLList.h? It would help if we could see the definition of DLLNode.

Given that there is only a tail pointer, I have these questions:
Line 17: shouldn't you set tail->prev = tail?

Line 20. If the list isn't empty then you need to update
- the new node's prev and next pointers
- the next pointer of the previous node.
- the prev pointer of the next node.

In delete_from_tail, if the list isn't empty then you need to update the prev pointer of the next node and the next pointer of the previous node.

It may help to create diagrams of this stuff. For example, to insert a node, start with a diagram of the two nodes that you're inserting between. Now with a different color, draw the new node and the new links. Write code to change all the links.