Singly LinkList in C using Linus Torvalds Way



A while back Linus Torvalds answered questions on Slashdot.

One of the answers was on the subject of understanding of pointers:

At the opposite end of the spectrum, I actually wish more people understood the really core low-level kind of coding. Not big, complex stuff like the lockless name lookup, but simply good use of pointers-to-pointers etc. For example, I’ve seen too many people who delete a singly-linked list entry by keeping track of the “prev” entry, and then to delete the entry, doing something like

if (prev)
prev->next = entry->next;
else
list_head = entry->next;

and whenever I see code like that, I just go “This person doesn’t understand pointers”. And it’s sadly quite common.

People who understand pointers just use a “pointer to the entry pointer”, and initialize that with the address of the list_head. And then as they traverse the list, they can remove the entry without using any conditionals, by just doing a “*pp = entry->next”

I tried his way and found it actually works!!! Needless to say it gave me a pain in neck to understand what exactly is going on.

To make this more clear I wrote a program in c++ for singly linked list and used the above method to delete a value.

Everytime I run this program I feel so amazed because I didn't mention any special cases and it works just fine.

Have a look on my code:
#include
using namespace std;
struct box{
int data;
box *next;
};
box *root = nullptr;
box* getNode(int val){
box *temp = new box;
temp->data = val;
temp->next=nullptr;
return temp;
}
void insert_ll(int val){
box *newnode = getNode(val);
if(root == nullptr)
root = newnode;
else{
box *trav = root,*pre;
while(trav!=nullptr){
pre=trav;
trav=trav->next;
}
pre->next = newnode;
}
}
void print_ll(box *refr){
box *trav = refr;
while(trav!=nullptr){
cout << trav->data << " ";
trav = trav->next;
}
}
void remove_ll(int val){
box **pp = &root;
box *trav = root;
while(trav){
if(trav->data == val)
*pp = trav->next;
pp=&trav->next;
trav=trav->next;
}
}
int main(){
for(int i=0;i<10;i++)
insert_ll(i);
print_ll(root);
remove_ll(0);
cout << endl;
print_ll(root);
remove_ll(2);
cout << endl;
print_ll(root);
cout << endl;
remove_ll(9);
print_ll(root);
return 0;
}

OUTPUT:

0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 3 4 5 6 7 8 9
1 3 4 5 6 7 8

If you are having problems understanding it, let me suggest some YouTube videos:

https://youtu.be/t5NszbIerYchttps://youtu.be/0ZEX_l0DFK0https://youtu.be/1s0w_p5HEuY

Also, if you wish to see the TED talk where Linus mentions about this, the link to that video is:

https://youtu.be/o8NPllzkFhE

Suhaib Bin Younis | @suhaibbinyounis

Post a Comment

Post a Comment (0)

Previous Post Next Post