2

I'm doing this homework exercise with simple linked lists in C with nodes having the following structure:

typedef struct lista { int num; struct lista * next; } nodo;

So the exercise asks us to traverse the list and if we find two nodes such that node1->num == P and node2->num == Q, we delete all nodes between them and also them.

The "easy" way of doing this is by just making the previous node of the one that holds P point to the node that comes after the one that holds Q (Let's assume for the sake of the exercise that the node holding Q is not the last one).

But I know this is wrong...the now unused nodes are still occupying memory. I have to use free() somehow but I don't what pattern or best practice to use here.

EDIT: Previously I wrote keeping an array. This would not work as I don't know how long the list will be...so I would need to create another simple linked with each node holding the pointer to the ones that will be deleted, correct?

Improve this question

    1 Answer 1

    Reset to default
    4

    Almost there! You have a linked list:

    HEAD ---> P ---> x ---> x ---> Q ---> TAIL

    You re-link part of the list (HEAD -> TAIL) to remove some nodes:

    HEAD -------------------------------> TAIL ^ P ---> x ---> x ---> Q -----'

    The removed nodes still exist and still form a linked list. You code can keep a reference to the P node, then iterate through this linked list and free the removed nodes. But note that the TAIL is shared between the two linked lists, so you have to stop deleting nodes when the TAIL is reached.

    Pseudocode:

    node* head = ...; node* q = ...; node* p = head->next; node* tail = q->next; // re-link head->next = tail; // clean up old nodes while (p != tail) { node* next = p->next; free(p); p = next; }

    Linked lists are not often used in “real” software engineering because arrays are typically much more efficient. But this ability to quickly change some pointers and still have an old version of the data around can be very useful, for example in a concurrent program or in functional programming.

    Improve this answer
    3
    • Thanks @amon for the clarification! For further clarification...what is used in real life in case we don't know the data size beforehand?? As far as I know for now, arrays in C are static. How do software engineers deal with this?
      – 4d4143
      CommentedOct 12, 2021 at 10:40
    • 1
      @4d4143 You can malloc() an amount of memory that is probably large enough. If the capacity is exhausted, you can realloc() this buffer to a larger size. If you can use C++, std::vector implements this strategy. While resizing is expensive, it is rare in practice (the typical algorithm is to double the size of the buffer each time it is exhausted). Accessing data in contiguous buffers is so much more efficient than linked lists on modern CPUs. For data that is too large for RAM (e.g. databases), a btree data structure is often used which combines arrays+links.
      – amon
      CommentedOct 12, 2021 at 11:07
    • 2
      @4d4143 To complement amon's explanation - so, for list-like collections, you'd typically just use something like std::vector. However, you might encounter linked-lists and tree-like structures in other guises; e.g. UI controls that contain child controls (that in turn contain child controls, etc.) are a tree, and any concrete path down (or up) that tree is basically a linked-list (e.g. searching for a parent of specific type is like searching for a specific node). Knowing a little bit about these data structures can be useful if you can recognize these things "hiding in plain sight".
      – Filip Milovanović
      CommentedOct 12, 2021 at 11:40

    Start asking to get answers

    Find the answer to your question by asking.

    Ask question

    Explore related questions

    See similar questions with these tags.