Insert Function on Doubly Linked List

Question

So I've got this insert function for a doubly linked list that is working for the most part just up until I try to insert a new node at a given index. I'm having trouble with linking it correctly to the nodes before and after it, if anyone could see why, I keep getting errors when I try to assign one of the points I'll point out in the code:

  void insert(int index, ItemType& item) 
  {

    int pos = 0;
    Node* current = new Node;
    Node* n = new Node;
    n->info = item;
    if (index >= 0 && index <= size)
    {
        if (size == 0)
        {
            head = n;
            tail = n;
            n->next = NULL;
            n->prev = NULL;
            size++;
            return;
        }
        else if (index == 0)
        {
            n->prev = NULL;
            n->next = head;
            head->prev = n;
            head = n;
            size++;
            return;
        }
        else if (index == size)
        {
            n->next = NULL;
            n->prev = tail;
            tail->next = n;
            tail = n;
            size++;
            return;
        }
        else if (index < size/2)
        {
            current = head;
            while(pos != index)
            {
            current = current->next;
            pos++;
            }

        }
        else if (index > size/2)
        {
            int endpos = size - 1;
            current = tail;
            while(endpos != index)
            {
            current = current->prev;
            endpos--;

            }
        }


    n->next = current;
    current->prev->next = n; // HERE is where the code breaks, don't know why.
    n->prev = current->prev;
    current->prev = n;
    size++;


  }
}

So the code breaks at the current->prev->next = n statement stating there is an access violation writing location. So I'm not sure if that is coded right or if I've messed up in pointing assignments in earlier code. If anyone knows why its doing that and can point me in the right direction that would be awesome. Thanks.

Krishna M · Accepted Answer · 2014-03-18 17:29:41Z

1

From my observation,

Your code fails when index = size/2.

When there are two elements(size == 2) and when you try to insert at position 1, then current->prev->next = n; is meaningless

Do one of these changes else if (index <= size/2) or else if (index >= size/2)

answered Mar 18, 2014 at 17:29

Krishna M

1,2152 gold badges18 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

DrackBlagon Over a year ago

Excellent, this was perfect, got it fixed. Thank you so much.

trm · Accepted Answer · 2014-03-18 17:32:10Z

0

If current is the first node in the list, then current->prev will be NULL, so current->prev->next will cause problems. You should check if current is the first item in the list before this line.

Also, your code leaks memory because you are allocating a new Node for current and you do not delete it. Since you are using current to move through the list rather than to create a new node, you should declare it as just

Node* current;

rather than

Node* current = new Node;

answered Mar 18, 2014 at 17:32

trm

4201 gold badge4 silver badges10 bronze badges

Collectives™ on Stack Overflow

Insert Function on Doubly Linked List

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related