Deleting node from linked list

[electroRF]

Hi,

When deleting Node from linked list, there's actually a memory left which no-one will ever use until the "head" of the list is freed.

Isn't it a problem?

Are there ways to overcome it?

Thank you.

 

[KeepItSimpleStupid]

Unless you have a way to manage memory consider your linked list as two linked lists or as one linked list with

One is active and the other is where you add new items:

e.g.
000: Item #1 Link flag: 0
100: Item #2 Link Flag:0
200: Item #3 Link Flag:-1
300: Item #3 Link Flag: -1


Flag of -1 could indicate an unused link, the first -1 is the start of the unused.
Maintain the address of the start of the used link: 000 in this case and maintain the the last linked address. of 100. Then the next link is the free or where you might put the new stuff.

Yes, you have to manage the list and you need to have a linked and unused linked sections of memory. Adding to your linked list requires you to update the pointers to point to a free link and also update the free links.

Memory management is more of an operating system issue.

 

[NorthGuy]

If you have a heap, you allocate each element of linked list separately and assume that the memory manager is good enough to handle this.

If you don't have a heap, you create an array of elements (too bad if your elements are of different size) . Array must be big enough to hold the whole list. Each element of the list contains an index of the next element in the list (and an index of the previous one in case of double-linked list) and data. Then you do as KISS suggested. You initialize your array so that all the elements are linked together - this is the list of your free elements. When you need to allocate a new element, you simply get the first element from the "free list", remove it from the "free list" and insert it into your working list. When you need to free an element, you remove it from your working list and insert as a first element of the "free list"

e.g. 3 element array with indices 1,2,3.

After intialization:

Free->1
1->2
2->3
2->NULL

Working->NULL

After insert one element into the working list (element 1 removed from Free and added to Working):

Free->2
2->3
3->NULL

Working->1
1->NULL

After inserting an element to the tail of working list (element 2 removed from Free and added to Working):

Free->3
3->NULL

Working->1
1->2
2->NULL

After inserting an element to the head of working list (element 3 removed from Free and added to Working):

Free->NULL

Working->3
3->1
1->2
2->NULL

If you want to allocate more, you generate an error because Free list is empty.

After removing an element from the middle of working list (element 1 removed from Working and added to Free):

Free->1
1->NULL

Working->3
3->2
2->NULL

With this technique, you can use several working lists within the same array.

 

[electroRF]

guys,
thanks a lot!!

great inputs