> In a 2016 TED interview, Linus Torvalds showed two ways to delete a node from a singly linked list in C to explain what he considers good programming taste.> Most programmers keep track of the previous node and write an extra if statement to handle deleting the head of the list.> Linus showed that you can avoid the entire special case by using a pointer-to-a-pointer (Node **indirect).> Instead of remembering the previous node, you remember the address of the pointer pointing to the current node.> Now it doesn't matter whether you're deleting the first node or the 500th. The same assignment works for both.
>>110371230use case?
>>110371230C is unironically the best language for linked lists because of that trick. If you can't make a pointer to the "next" field of a node, then you're stuck handling the head and/or tail specially.
>>110371230yeah thats how i would do it too
>>110371271right, this is why we use c, the computer does what it does and c provides access to what the computer does. c still needs some upgrades, and the c committee wont do anything until its implemented, so we have to upgrade c with transpilers like https://github.com/loosestrife/c42
>>110371270For a singly linked list? Don't know.
>>110371355yeah singly linked lists are a code smell this guy needs to use generic containers like Vector<typename T> not just for performance but also for documentation
>>110371230why would you ever use a list instead of a vector?i have legit never seen a case list would be so big it wouldn't be better served with a deque.also this "wow look at my optimisations" is small penis behaviour that c/cpp programmers especially love to engage in. wow, on the spot you came up with an optimised form of some fundamental primitive which should be a primitive in the language itself, how cool, this will totally make up for you being a sub-5 genetic refuse nerd fag.
>>110371471Removal from a list is O(1).
>>110371504dropping whole vector is also o1
>>110371270NoneIn any language this is just list.remove(thing)
>>110371471>some fundamental primitive which should be a primitive in the language itselfnothing primitive about a vector
>>110371546>In any languageIn plain C? Are you an indian?
>>110371546>>110371418Do you have access to <vector> and <array> and any other std functionalities in systems programming? Let's say you are writing a boot loader
>>110371552it's a fundamental data structure that people actually use on computers. it should be at least a second class citizen in the language.this is my beef with "apis" like c, ogl or directx being fucking useless wrappers for the machine code. when actually, an api like programming language or graphics library should include all the primitives which are useful for high-level design in said domain. a programming language must have containers, and graphics apis should've been something like unreal's rendering pipeline, not a bunch of fucking calls to the driver. programmers keep doing shit job at making fundamentals.
>>110371669so it's not a primitivewhy would you lie on 4chan
>>110371230this is shit that should be part of a standard library
>No memory is freedToy example.
>>110371763>linked list>allocates individual nodesjust how indian are you?
>>110371418>C>Generic containersOh, I see what you did there.
>>110371230That's cute. Now remember that one of the 50 million Indian Hindpoo invaders that have left India to replace you in your own country, will be responsible for trying to read and understand that code. And they have an average IQ of 45 from thousands of years of inbreeding. You made it less readable and now when Ratjesh fucks up whatever address the pointer was supposed to be pointing to, you're the one who will be woken up at 2 am to fix it.
>>110371613Yes. In rust, alloc works just fine in no_std. In C++ you have a minimum runtime you need to implement as well. Nothing about those things are special, except for C, which is a shit language for retards.
>>110371739How could it be? This is C. You don't have generics and even if you did, you don't have other things like destructors, ownership concepts, etc. you could never generalize something like that function for any singly-linked list.
>>110371230Don't care what an ESL thinks.
>>110371230isn't that an extra ref and deref every loop?
>>110372316nah it's the same thing
>>110371471>being a sub-5 genetic refuse nerd fag.>posts toho
>>110372841really?
>>110372971indirect needs not be dereferenced more than once for each turn of the loop and what you refer to as 'ref' is simple arithmetic addition. are you indian or something?
>>110373035dumb nigger, how do you justify doing a deref every loop? fucking dunning kruger ass retard don't even bother replying actually
usecase for linked lists?
>>110373062sequential data storage with dynamic size
>>110373062Read the kernel and you'll find out.
>>110373069you can use normal stretchy buffer with realloc and it will be much faster due to how caching works in cpus
>in 2016, torvalds learned to program like a freshman who got a C in CS 101Inspiring
>>110371270>>110371355>>110373062They are everywhere in the linux kernel.Some useful properties are that the same object/structure can be in multiple linked lists and no extra array or anything needs to be allocated for each one. This makes it easy to add and remove objects to/from various bookkeeping lists, when dealing with a specific kernel object you are usually already in the right place to add/remove it from lists by modifying just 2 pointers, it's constant time and very little code.Compare to something like arrays where you'd have to manage multiple arrays or vectors or whatever you want to call it, find the pointer to the object in the arrays separately, manage memory for them, maybe do big moves when removing items etc. There is no benefit to it except faster traversal, which is often not the most important, and even that is not faster if you have to actually look at each object and dereference the pointer, which you usually do.Even if you don't need the object to be in multiple lists, and you could use an array with the whole object in it instead of pointers to the objects, the array of objects now has the disadvantage that objects inside may get moved around in memory(depending on the exact implementation). This means you can't have pointers to things inside the object elsewhere.Another pro is that you can easily have items of different sizes in the list, this is also often used in the kernel. It would be awkward in an array of objects and waste space.
>>110373129Deletion will still be painfull, so just use unrolled linked list (if not with basic types, with an index array for each node).
>>110373051both functions do that