C++

Forum

 
Is This Linked List Function On Point?

JesusFreak43 (20)
Hello. So I created this code for my last project for my CS class, yet I know there are problems with it but I need help analyzing this code. Would this work for dividing a linked list into two sublists at a given node? (By the way, I used a different already given function in this class to use as a sort of template for this function, so that's how I ordered my function.)

By the way, I think in this kind of linked list, the "first" pointer points to the last node, because it is a circular linked list and first->link would then point to the first node in the list. Or at least I think that is how it works.

Here is the function that I created:
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
 
 void divideAt(circularLinkedList<Type> &secondList, const Type& item){
        nodeType<Type> *current; //pointer to traverse the list
        nodeType<Type> *trailCurrent;
    
        
        bool found = false;
        
        if (first == NULL)    //Case 1; list is empty.
            cout << "Can not split an empty list." << endl;
        
        while (current != first && !found)
            if (current->info == item)
                found = true;
        
            else
            {
                found = false;
                trailCurrent = first;
                current = first->link;
                
                while (current != first && !found) {
                    if (current->info == item)
                        found = true;
                    else
                    {
                        trailCurrent = current;
                        current = current->link;
                    }
                }
                
                if (current == first)
                {
                    if (first->info == item)
                    {
                        if (first == first->link)
                            cout << "Cannot split a list with only one node.";
                        else
                        {
                            trailCurrent->link = first->link;
                            (secondList.first)=current;
                            current->link = current;
                            
                        }
                        
                        
                    }
                    else
                        cout << "The item to split at is not in the list." << endl;
                }
                else
                    if (current->info == item)
                    {
                        
                        trailCurrent->link = first->link;
                        secondList.first = first;
                        secondList.first->link = current;
                        first = trailCurrent;
                    }
                    else
                        cout << "The item to split at is not in the list." << endl;
            } //end else
        
        
    }



Here is the function that creates a linked list when you are creating a linked list in main:

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
 
void insertNode(const Type& newitem)
    {
        nodeType<Type> *current; //pointer to traverse the list
        nodeType<Type> *trailCurrent; //pointer just before current
        nodeType<Type> *newNode;  //pointer to create a node
        
        bool  found;
        
        newNode = new nodeType<Type>; //create the node
        
        newNode->info = newitem;   //store newitem in the node
        newNode->link = NULL;      //set the link field of the node
        //to NULL
        
        if (first == NULL)  //Case 1    e.g., 3
        {
            first = newNode;
            first->link = newNode;
            count++;
        }
        else
        {
            if (newitem >= first->info)//e.g., 25 > 3
            {
                newNode->link = first->link;
                first->link = newNode;
                first = newNode;
            }
            else
            {
                trailCurrent = first; //e.g., 1 < 3
                current = first->link;
                found = false;
                
                while (current != first && !found)
                    if (current->info >= newitem)
                        found = true;
                    else
                    {
                        trailCurrent = current;
                        current = current->link;
                    }
                
                trailCurrent->link = newNode;
                newNode->link = current;
            }
            
            count++;
        }//end else
    }




Basically, I am just looking for feedback on the function I created (divideAt). Any feedback, both uplifting and constructive criticism would be helpful. Thank you!

-AC
salem c (3700)
> if (first == NULL) //Case 1; list is empty.
Maybe you should return, rather than carrying on.

> while (current != first && !found)
current is uninitialised.

11 while (current != first && !found)
...
21 while (current != first && !found) {
Your logic is way too complicated.

1
2
3
4
5
6
7
8
9
 
        while (current != first && !found) {
            if (current->info == item)
                found = true;
            else
            {
                trailCurrent = current;
                current = current->link;
            }
        }

This just chases down the list, until it cycles back to the start, or a match is found.

If found, then do your splitting.
Topic archived. No new replies allowed.