Sorted link lists

I've been trying to get this nightmare of a function to work for over a week now.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

ListRetVal  CSortedList::InsertItem(const ListItemType  &newItem)
{

	//still broken

	    // Create a new node
	ListItemNode* newLNode = new ListItemNode();
	newLNode->value = newItem;
	newLNode->next = NULL;

	if(m_headPtr == NULL)
	{
		//listempty
		m_numItems = 0;
		m_headPtr = newLNode;
	}
	


	m_numItems++;
	return LIST_SUCCESS;
}


above works
I can't think of a way to keep the list in order. Every time I try it creates duplicates out of order.

below is my failing implementation

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

ListRetVal  CSortedList::InsertItem(const ListItemType  &newItem)
{

	if((m_headPtr == NULL) || (m_headPtr->value) > newItem)
	{
		ListItemNode * newLNode = new ListItemNode;	//declaring new node
		newLNode->value = newItem;
		newLNode->next = m_headPtr;
		m_headPtr = newLNode;
		

	}
	else if(m_headPtr->next == NULL)
	{
		ListItemNode * newLNode = new ListItemNode;
		m_headPtr->next = newLNode;
		newLNode->value = newItem;
		newLNode->next = NULL;
	}
	else
	{
		ListItemNode * travelLNode;
		ListItemNode * tailLNode;
		travelLNode  = m_headPtr;
		
		//travels looking for less than, or ==
		while(travelLNode->next != NULL)
		{
			 tailLNode = travelLNode;
			 travelLNode = travelLNode->next;

			if (travelLNode->value == newItem)
			{
			//	return LIST_DUPLICATE;
			 break;
			}
		 
			if ( (travelLNode->value > newItem) )
			{
				ListItemNode * newLNode = new ListItemNode;	//declaring new node
				newLNode->value = newItem;
				newLNode->next = travelLNode;

				tailLNode->next = newLNode;


			}
			else if (travelLNode->next == NULL)
			{
				ListItemNode * newLNode = new ListItemNode;	//declaring new node
				newLNode->value = newItem;
				newLNode->next = travelLNode->next;
				travelLNode->next = newLNode;
			}

		}
		
	}

	m_numItems++;
	return LIST_SUCCESS;
}

reply timeout.
Last edited on
Just use narakus solution below.
Last edited on
This is untested but should work.
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
ListRetVal  CSortedList::InsertItem(const ListItemType  &newItem)
{
    // Create a new node
	ListItemNode* newLNode = new ListItemNode();
	newLNode->value = newItem;
	newLNode->next = NULL;

	if(m_headPtr == NULL)
	{
		//listempty
		m_numItems = 0;
		m_headPtr = newLNode;
	}
	else//list not empty
	{
		ListItemNode *prev, *current = m_headPtr;
		while(current != NULL && current->value < newItem)
		{
			prev = current;
			current = current->next;
		}
		if(current->value == newItem)//I assume you dont want duplicates
			return LIST_DUPLICATE;
			
		prev->next = newNode;
		newNode->next = current;
	}
	
	m_numItems++;
	return LIST_SUCCESS;
}
Topic archived. No new replies allowed.