Ordered singly linked list insert

closed account (4ET0pfjN)
My ordered_insert function crashes when I try to run it, I need help with the pointers but I'm pretty sure the logic is right. It compiles, but crashes when I run the exe.

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
36
37
38
39
40
41
42
43
44
45
46
struct sll_node//Singly linked list node
{
  string data;
  sll_node *next;
};

sll_node *ordered_insert(string node_data, sll_node **front)//fcn returns NULL or updated ptr to front of list
{
  sll_node **prev = NULL; 
  sll_node **cur = front;
  sll_node *newNode = new sll_node;
	
  newNode->data = node_data;
	
  for ( ; *cur != NULL; *prev = *cur, *cur = (*cur)->next )
  {
	//if newNode < front of list
	if ( newNode->data < (*cur)->data && *prev == NULL)
	{
	  newNode->next = *front;
	  *front = newNode;
	  return *front;
	}
	else if ( newNode->data < (*cur)->data && *prev != NULL )
	{
	  (*prev)->next = newNode;
	  newNode->next = *cur;
	  return *front;
	}
 }
	
 //If empty list
 if ( *cur == NULL && *prev == NULL )
	return NULL;
}

int main()
{
 sll_node *front = NULL;
 sll_node *end = NULL;
 if ( ordered_insert("AdA", &front) != NULL )
   cout << "Inserted" << endl;
 else
   cout << "Already in list" << endl;
return 0;
}
Last edited on
You're trying to dereference a null pointer on line 33:
1
2
3
4
 //If empty list
 if ( *cur == NULL && *prev == NULL )
	return NULL;
}

You declared **prev = NULL at the beginning of sll_node, and you never change it, since you are passing *front (which is NULL) to the function, so the value of **cur (A pointer to *front) is NULL and your for loop doesn't run.
I would get rid of the double pointers completely. I have no idea what you're trying to achieve with them.
closed account (4ET0pfjN)
It doesn't work still, it still crashes when I execute it. I think I need to use pointers to pointers since if the node to insert is smallest, I need to modify the original front pointer to point to the new node...So I'm sticking w/ my original code, but not sure what to do now...I hope someone can help out!

Here is new code and function againI forgot to add to insert new node at end if it's node w/ "largest" value:

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
36
37
38
39
40
41
42
sll_node *ordered_insert(string node_data, sll_node **front)//fcn returns NULL or updated ptr to front of list
{
	sll_node **prev = NULL; 
	sll_node **cur = front;
	sll_node *newNode = new sll_node;
	
	newNode->data = node_data;
	
	for ( ; *cur != NULL; *prev = *cur, *cur = (*cur)->next )
	{
		
		//if newNode < front of list
		if ( newNode->data < (*cur)->data && *prev == NULL)
		{
			newNode->next = *front;
			*front = newNode;
			return *front;
		}
		//Else newNode goes somewhere else in list
		else if ( newNode->data < (*cur)->data && *prev != NULL )
		{
			(*prev)->next = newNode;
			newNode->next = *cur;
			return *front;
		}
	
	}//END FOR LOOP
	
	//If empty list
	if ( *cur == NULL && *prev == NULL )
		return NULL;
	
	/*NEW CODE ADDED*/
	//if end of list, then new node is biggest node (in terms of ASCII int values assigned to alphabets)
	if ( newNode->data > (*prev)->data && *cur == NULL )
	{
		(*prev)->next = newNode;
		newNode->next = NULL;
		delete cur; cur = NULL;
	}
}

Last edited on
If you used a double pointer to update the frontnode that you store in your code, how are you going to back track through your data to the stuff stored before frontnode? You don't have any pointers pointing to previous nodes (Since this would be a doubly linked list). I didn't look over all your code, because to be perfectly honest it's quite chaotic, but I think something like this would do the trick:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Insert(Node *first, int new_data)
{
while(first->next != NULL)
{
   if(first->next->data > new_data)
   {
      Node *temp = new Node(new_data);
      temp->next = first->next;
      first->next = temp;
      return;
   }
first = first->next;
}
first->next = new Node(new_data);
}


EDIT: Fixing code.
Last edited on
closed account (4ET0pfjN)
it must take a lot of practice to learn to write elegant code, my code seems too explicit and redundant, i'll look into your solution, thanks.
There is one problem with my code though, and that's if the first node is greater then it won't be replaced. See if you can fix that. I haven't actually been coding for that long, so thanks for saying that. Although I still consider myself a beginner.
Last edited on
closed account (4ET0pfjN)
I've fixed up my code and it works like a charm. I'll take a look at your code and see, Blacksheep. Thanks.

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
sll_node *ordered_insert(string node_data, sll_node **front, sll_node **end)//fcn returns NULL or updated ptr to front of list
{
	sll_node *prev = NULL; 
	sll_node *cur = *front;
	sll_node *newNode = new sll_node;
	newNode->data = node_data;
	
	if ( cur == NULL && prev == NULL ) return NULL;//if empty list

	if ( newNode->data < (cur)->data && prev == NULL)//if new node is smaller than current front node 
	{
		newNode->next = *front;
		*front = newNode;
		return *front;
	}
	
	for ( ; cur != NULL; prev = cur, cur = (cur)->next )//new node goes somewhere else in list
		if ( newNode->data < (cur)->data && prev != NULL )
		{
			(prev)->next = newNode;
			newNode->next = cur;
			return *front;
		}
	
	if ( newNode->data > (prev)->data && cur == NULL )//if end of list, new node must be biggest
	{
		(prev)->next = newNode;
		newNode->next = NULL;
		*end = newNode;
		delete cur; cur = NULL;
		return *front;
	}
}
Last edited on
Topic archived. No new replies allowed.