C++

Forum

 
Insertion into linked list failing

TheJJJunk (181)
I am trying to insert into a linked list, but when I insert two numbers and the second number is smaller than the first, I get a segmentation fault. There is an error with prev->next = newPtr, but I'm not sure why.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
 void List::insert(ListItemType& newItem)
{
   ListNode *newPtr = new ListNode;
   ListNode *prev   = new ListNode;
   ListNode *cur    = new ListNode;

   prev = NULL;
   cur  = head;

   int newLength = getLength() + 1;
   size = newLength;

   newPtr->item = newItem;

   if (head == NULL)
   {
      newPtr->next = head;
      head = newPtr;
   }

   else
   {
      while (cur != NULL && newPtr->item > cur->item)
      {

         prev = cur;
         cur  = cur->next;
      }
     
      newPtr->next = cur;
      prev->next = newPtr; //segmentation fault
     
   }
} // end insert
Last edited on
vlad from moscow (6539)
I think you do not understand what you are doing. For example why are you allocating memory in this code snip?!!!

1
2
3
 
   ListNode *newPtr = new ListNode;
   ListNode *prev   = new ListNode;
   ListNode *cur    = new ListNode;

TheJJJunk (181)
prev and cur are ListNodes used to traverse the list. newPtr is a list node used to store the new item.

I'm trying to make this a sorted insert.
Last edited on
TheJJJunk (181)
Solved.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
void List::insert(ListItemType& newItem)
{

   ListNode* newNode = new ListNode;
   newNode->item = newItem;

   ListNode* prev = new ListNode;
   prev = NULL;
   ListNode* cur = new ListNode;
   cur = head;

   while (NULL!= cur && cur->item < newNode->item)
   {
      prev = cur;
      cur = cur->next;
   }

   if (NULL == prev)
   {
      head = newNode;
   }

   else
   {
      prev->next = newNode;
   }
   newNode->next = cur;
}
vlad from moscow (6539)
You solved nothing.
One more for the advanced programmers as you why are you allocating memory?!!!

1
2
3
4
 
   ListNode* prev = new ListNode;
   prev = NULL;
   ListNode* cur = new ListNode;
   cur = head;


What is the great sense of these allocations if after that you are assigning pointers NULL?!!!

TheJJJunk (181)
How else to traverse the list?
Betray1st (6)
Like vlad said, the allocations are useless. You don't need to allocate memory if the pointer is just pointing to another node and not holding any data. All you need to traverse the list is two pointers:

1
2
3
4
 

   ListNode* prev = NULL;
   ListNode* cur = head;
Topic archived. No new replies allowed.