Inserting an element in doubly linked list

Question

I more or less get the basic idea behind single linked list, but having trouble with inserting elements in a doubly linked list. Basically I am having trouble linking prev and next pointers to the appropriate nodes. Thanks in advance for help. Here is how my code looks like.

LinkedList.h

template <class T>
class LinkedList{
      protected:
        LinkedListNode<T>* head;
      public:
        LinkedList():head(NULL){}
        ~LinkedList();
        void insert(const T& x);
};


//inserting
template <class T>
void LinkedList<T>::insert(const T& x) {
 LinkedListNode<T>* head = new LinkedListNode<T>(head->prev, x, head->next);
 if(head != NULL){
         head->prev = head->next;
         head->next = head;
  }       
}

LinkedListNode.h

class LinkedListNode{
      protected:
        LinkedListNode<T>* prev;
        T value;
        LinkedListNode<T>* next;
        LinkedListNode(LinkedListNode<T>* p, const T& x, LinkedListNode<T>* n):prev(p), value(x), next(n) {}
        ~doublyLinkedListNode();
        template <class S> friend class doublyLinkedList;
};

I tried modifying the insert function as following, but it gave segmentation fault. What is wrong with my implementation?

template <class T>
void LinkedList<T>::insert(const T& x) {
 LinkedListNode<T>* head;
 if(head == NULL){
        head->value = x;
        head->prev = NULL;
        head->next = head;

 }
else{   LinkedListNode<T>* newnode;
        newnode->value = x;
        newnode->prev = head->next;
        newnode->next = newnode;
        head = newnode;
 }

To start with, do it on paper with arrows for the pointers. Secondly, don't create your own list when you have std::list. — Some programmer dude
– Some programmer dude, Commented Oct 6, 2012 at 16:15
@JoachimPileborg Minor point: It's great to create your own list. You just shouldn't use it (except of course testing it). — user395760
– user395760, Commented Oct 6, 2012 at 16:15
In your latest code for insert, you declare a local variable head when there's already a member variable head. Later, when you say head, the compiler can't guess which one you mean (or rather, it guesses wrong). — Beta
– Beta, Commented Oct 6, 2012 at 16:42

Zeta · Accepted Answer · 2012-10-06 16:49:14Z

You're a victim of variable shadowing.

Lets have a look at your original version:

//inserting
template <class T> void LinkedList<T>::insert(const T& x) {
   LinkedListNode<T>* head = new LinkedListNode<T>(head->prev, x, head->next);
   // ...

We're going to dissect the first instruction of your function:

   LinkedListNode<T>* head; // not initialized value
   new LinkedListNode<T>(head->prev, x, head->next); // oh oh....

head is a new variable and your original this->head is shadowed. But even if you fix this problem, the initial this->head is still NULL and thus this->head->prev will result in a segmentation fault. You fix the latter in your second version, but only there's still something wrong:

template

void LinkedList<T>::insert(const T& x) {
 LinkedListNode<T>* head; // #1
 if(head == NULL){
        // #2
        head->value = x;
        head->prev = NULL;
        head->next = head;

 }
else{   LinkedListNode<T>* newnode;
        newnode->value = x;
        newnode->prev = head->next; // #3
        newnode->next = newnode;    // #3
        head = newnode;
 }

The first error (#1) is, again, variable shadowing. #2 is again a segmentation fault, since you didn't allocate memory for your head.

#3 are logical errors. The previous node should be the head itself, and the node following a node shouldn't be the node itself.

Collectives™ on Stack Overflow

Inserting an element in doubly linked list

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related