Hello all,


here is the code I came up with for implementing a circular linked list. I get a segmentation fault when I create the list with just one node. With size > 1 circular list works fine! Im not sure but I think it may have something to do with the head pointer pointing to itself.. any ideas?

#include <stdio.h>
using namespace std;

#ifndef CIRCULARLINKEDLIST_H_
#define CIRCULARLINKEDLIST_H_


class Node 
{
  public:
   char* value;
   Node* next;
   int index;
   Node(int in, char* val,Node* nextNode){
     index = in;
     value = val;
     next = nextNode;
  }

};

class CircularLinkedList 
{
  public:
   Node* head;
   int size;
   CircularLinkedList(){
      head = NULL;
   }
   CircularLinkedList(int capacity){
      size = capacity;
      for (int i = 0; i < capacity; i++)
         add(i,NULL); //add new node value of char* NULL      
   }

  void add(int index, char* value)
  {
     Node* p = head;
     if(NULL == head){ 
        head = new Node(index,value,head);
        return;
     }
     if(p->next == NULL){
        p->next = new Node(index,value,head);
        return;
     }
 
     while(p){
       if(p->next == head){
          p->next = new Node(index,value,head);
          return;
       } 
       p = p->next;
       
     }
  }

  void print()
  {
     Node *p = head;
     while(p){
       printf("-> %d ",p->index);
       p = p->next;
      // if(p == head) return;
     }
  }

  Node* getHead()
  {
     return head;
  }

  ~CircularLinkedList()
   {
      Node* p = head;
      while(p){
         Node* temp = p;
         p = p->next;
         delete temp;
      }
   }
};

#endif /*CIRCULARLINKEDLIST_H_*/

main

CircularLinkedList* list = new CircularLinkedList(1);
Node* p = list->getHead();
p = p->next; // seg fault

Remember that Pointer-to-objects do not get initialized to null implicitly, you have to do that by your self

Hello, and thanks for the quick response!

this if statement is never executed lines 44- 47:
if(p->next == NULL){
p->next = new Node(index,value,head);
return;
}
I should probably remove it.
Is that what you are referring to ?

In your example, you are calling the constructor CircularLinkedList(int), which does not initialize the head pointer. You assume that add() does that, which it should, but that is a bad practice. In any case, there are a number of issues. Whatever you do, make sure that you initialize your member variables in the initialization block, before the body of your class constructors. This will save a LOT of grief. IE, instead of this

Node(int in, char* val,Node* nextNode){
     index = in;
     value = val;
     next = nextNode;
  }
.
.
.
   CircularLinkedList(){
      head = NULL;
   }
   CircularLinkedList(int capacity){
      size = capacity;
      for (int i = 0; i < capacity; i++)
         add(i,NULL); //add new node value of char* NULL      
   }

do this

Node(int in, char* val,Node* nextNode)
  : index(in), value(val), next(nextNode)
  {
  }
.
.
.
   CircularLinkedList() : head(0) {}
   CircularLinkedList(int capacity) : head(0)
   {
      size = capacity;
      for (int i = 0; i < capacity; i++)
         add(i,NULL); //add new node value of char* NULL      
   }

Also, DO NOT USE 'NULL' for generic null pointers in C++. Use the value 0 instead. Why you ask? Because NULL is defined as ((void*)0), and that cast may be a problem in some cases. You are ALWAYS safe to assign 0 to a pointer for a null value. Says so right in the ANSI C++ standard... :-)

not quite, trace through your program. Line 1 is key. The fact that you are getting sef faults means that the pointer p is not valid. Check to make sure that line 40 does executes

>>Because NULL is defined as ((void*)0), and that cast may be a problem in some cases

care to explain...? I never had a problem switching the two.

When you run into that problem, you will discover that you have 10K lines of code to fix... Be safe. Read the ANSI/ISO C++ standard. They are very clear on this point. In the company I was senior/principal engineer at for almost 20 years, we made that part of the company coding standards. We learned early on that there were cases when it was not good. We were developing major enterprise systems in C++ that had to build and run identically on many different hardware and operating system platforms, ranging from PC's with Windows to QNX real-time systems, to just about every Unix variant out there (AIX on PPC, SunOS/Solaris on Sparc, HPUX on PA-RISC and Itanium, Tru64 Unix on DEC Alpha, and SysV on NCR, plus others). This bit us once, and when I pointed out that the Standard is clear on this point, there was no argument from management to change our coding standards to be FIRM on this point. Don't assume that all compilers behave identically - they manifestly do not!

When you run into that problem, you will discover that you have 10K lines of code to fix... Be safe. Read the ANSI/ISO C++ standard. They are very clear on this point.

Chapter and verse, please? 18.1-3 totally contradicts to what you say.

I'll need to look that up in my copy. May be a few days before I can respond.

I appreciate everyone's input and was able to fix my problem. Thanks!

working code:

#include <stdio.h>
using namespace std;

#ifndef CIRCULARLINKEDLIST_H_
#define CIRCULARLINKEDLIST_H_



class Node 
{
  public:
   char* value;
   Node* next;
   int index;
   Node(int in, char* val,Node* nextNode)
   : index(in), value(val), next(nextNode){}

};

class CircularLinkedList 
{

  public:
   Node* head;
   CircularLinkedList() : head(new Node(0,0,0)){
      head->next = head;
   }
   CircularLinkedList(int capacity) : head(new Node(0,0,0)) {
      head->next = head;
      for (int i = 1; i < capacity; i++){
         add(i,0);
      }
   }

  void add(int index, char* value)
  {
     Node* p = head;
     while(p){
       if(p->next == head){
          p->next = new Node(index,value,head);
          return;
       } 
       p = p->next;
       
     }
  }

  void print()
  {
     Node *p = head;
     while(p){
       printf("-> %d ",p->index);
       p = p->next;
     }
  }

  Node* getHead()
  {
     return head;
  }

  ~CircularLinkedList()
   {
      Node* p = head;
      while(p){
         Node* temp = p;
         p = p->next;
         delete temp;
      }
   }
};

#endif /*CIRCULARLINKEDLIST_H_*/
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.