C++

Forum

 
Sorted a Linked Node

techjohnny (32)
Need help sorting this constructor:

I know the while loop should include another statement, but a little confused on the rest.
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
 
 void List::AddNode(int addData)
	
{
	// definition of the AddNode function
	nodePtr n = new node;
	
	n->next = NULL;// last element in the list
	n->data = addData;

	
	if (head != NULL) // last value always set to null 
		// if there is already an element in the list.
	{
		curr = head;
		while (curr->next != NULL)
		{
		
				curr = curr->next;
		}
		
		curr->next = n;
	}
	else // we do not have an element in the list
	{
		head = n;
	}
}

;
Mantorr22 (152)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
void List::AddNode(int addData)
	
{
	// definition of the AddNode function
	nodePtr n = new node;
	
	n->next = NULL;// last element in the list
	n->data = addData;
	
	if (head == NULL) // last value always set to null 
		// if there is already an element in the list.
	{
		head = n;
	}
	else
	{
		nodePtr it = head;
		while (it->next != NULL)
		{
			it = it->next;
		}
		it->next = n;
	}
}
techjohnny (32)
This is what worked for me too.

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
47
48
 

void List::AddOrdered(int ordData)

{
	bool found;
	nodePtr n = new node;
	n->data = ordData;
	n->next = NULL;

	if (head == NULL)
	{
		head = n;
		trail = n;
	}
	else
	{
		curr = head;
		found = false;

		while (curr != NULL && !found)
			if (curr->data >= ordData)
				found = true;
			else
			{
				trail = curr; 
				curr = curr->next;
			}
		if (curr == head)
		{
			n->next = head;
			head = n;

		}
		else
		{
			trail->next = n;
			n->next = curr;
			if (curr == NULL)
			
				last = n;
			
			
		}
	}
}

;
Mantorr22 (152)
This is what worked for me too.

It does not. If you really intend to make a SortedList class, remove List::AddNode() and only keep the List::AddOrdered() function. By the way List::AddOrdered() does not look like it does the job, whether the function is actually correct or not.
Last edited on
dhayden (5795)
Although it harder to understand, the code is much easier if you use a headOrNext pointer. This points to head, or the previous node's next pointer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
void List::AddOrdered(int data)
{
    nodePtr *headOrNext;		// points to head, or some node's next pointer
    nodePtr cur;			// current node we're looking at

    // point headOrNext at the nodePtr where the new node should go.
    for (headOrNext = &head; (cur = *headOrNext); headOrNext = &cur->next) {
	if (cur->data > data) break;
    }

    // headOrNext now points to the pointer to the next item.

    nodePtr n = new Node;
    n->data = data;
    n->next = *headOrNext;
    *headOrNext = n;

    if (cur == nullptr) {
	// Inserting at the end. Update tail
	tail = n;
    }
}
Topic archived. No new replies allowed.