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.