-1

I'm currently working on some of my code. I'm trying to learn how the "List Class" from the STL library works under the hood. I can't seem to quite understand the process of removing a node from a list made by the user. Is there any information that is accessible that would better help me wrap my head around this problem.

#include <iostream>
#include <string>


using namespace std;

class Node {
public:
    string todos;
    Node* next;


    Node(string todos) {

        this->todos = todos;
        next = NULL;
    }

};

void print_list(Node* head) {

    Node* temp = head;
    while (temp != NULL) {
        cout << temp->todos << " ";
        temp = temp->next;
    }
}

Node* takeinput() {
    string var;
    int num;
    

    Node* head = NULL;
    Node* tail = NULL;

    cout << "Please enter 5 Todo tasks. " << endl;

    cout << endl;

    cout << "If you would like to exit this prompt please enter 'End' " << endl;

    cout << "If you would like to enter an item onto the list please press 1 " << endl;

    cout << endl;


    cin >> num;

    while (var != "End") {
        
        if (num == 1) {
            Node* newNode = new Node(var);
            
            if (head == NULL) { 
                head = newNode;
                tail = newNode;

            }

            else {
                tail->next = newNode;
                tail = tail->next;
            }
        }
        cin >> var;
        if (num == 2) {

        }
    }
    return head;
}

int main()
{
    string hello;

    Node* head = takeinput();
    

    print_list(head);



}
John
  • 1
  • 1
    The best way I know of to figure out linked lists is to visualize them by drawing pictures. A lot of pictures. For every operation, draw out what each step needs to look like in order to maintain a coherent list and not drop any of the nodes or links too soon. – user4581301 Sep 21 '22 at 18:13
  • 1
    Also consider making a linked list class rather than a bunch of free functions. This generally helps organize the code and encapsulate the nodes to protect them from misuse. – user4581301 Sep 21 '22 at 18:16
  • Tip: In C++ use `nullptr` in preference to C's typeless `NULL`. You should also avoid `using namespace std` as the `std::` separator is intentional. – tadman Sep 21 '22 at 18:21
  • I apologize for being ignorant, but what do you mean by misuse? – John Sep 21 '22 at 18:21
  • Tip: Learn about [constructor lists](https://en.cppreference.com/w/cpp/language/constructor) which can make for more minimal, less buggy code. – tadman Sep 21 '22 at 18:22
  • If you're going to remove an item from a list, which may necessarily alter the head, you may want to have a parent structure that captures the `head` and `tail` properties, then pass that around. Right now you have a lot of disjointed code here, with your "input" function doing way, way more than it advertises. It actually manages insertion, structuring, and more. It *should* focus on input exclusively, delegating the rest to other functions, like some `List` `append()` function. – tadman Sep 21 '22 at 18:25
  • [How do I properly delete nodes of linked list in C++](https://stackoverflow.com/questions/22121257/how-do-i-properly-delete-nodes-of-linked-list-in-c) should help you out. The **Alternative Using Pointer To Pointer** community addition is the best way to do this, but can be a bit of a mind-twister if you're still struggling with pointers. – user4581301 Sep 21 '22 at 18:57
  • Apologies for missing the earlier comment about what I meant by misuse. Here's an easy example: Say you traverse through the list and provide the user a pointer to the node the user was looking for. Say that now that the user's got it, they no longer need it and simply `delete node;`, destroying the list by mistake. Or they figure they can insert it somewhere else in the list without removing it first, once again breaking the list. A good linked list never lets the user touch a node or even see how the list operates on the inside. – user4581301 Sep 22 '22 at 01:07
  • If the user has to write code that works with the list's implementation details it's harder to make changes to the list later without also having to change the user code. That means it's harder to fix bugs or outright replace the list if you find a better data structure for the job. – user4581301 Sep 22 '22 at 01:09

1 Answers1

1

I'm trying to learn how the "List Class" from the STL library works under the hood.

std::list is a doubly linked list with user specified type for node data.

For Visual Studio, it is a circular linked list with a dummy node, where dummy.next is a pointer to the first node and dummy.prev is a pointer to the last node, and where first_node.prev and last_node.next point to the dummy node. There is a list size and optional user defined allocator (for nodes). There is support for iterators with operator overloading. std::list::end() returns an iterator to the dummy node (note that iterators can't be null). std::list::splice() allows nodes to be moved within a list or from one list to another.

std::list::sort() should be a bottom up merge sort for linked lists, but starting with Visual Studio 2015, it was changed to a less efficient top down merge sort for linked list when it was switched to be iterator based. If interested, link to example bottom up version:

`std::list<>::sort()` - why the sudden switch to top-down strategy?

The source code for std::list is ~2000 lines. I recommend starting off with just basic double linked list code.

rcgldr
  • 27,407
  • 3
  • 36
  • 61
  • I will also strongly recommend a very good understanding of C++. Standard library code can get really weird, really fast. Plus because it typically ships with a particular compiler and sometimes for a particular target platform, the library is in a unique position to exploit what would otherwise be fatal amounts of Undefined Behaviour. – user4581301 Sep 21 '22 at 21:51
  • @user4581301 - Visual Studio STL code base started off shared with HP and written by P.J. Plauger (Dinkumware) dating back to 1994 (it's listed at the end of each include file), and unlikely to have any compiler specific quirks. – rcgldr Sep 22 '22 at 01:39
  • Groovy. Dinkumware. That is a notable exception since it was independently developed. Yeah, most of my warning won't apply in that case. – user4581301 Sep 22 '22 at 01:42