[a / b / c / d / e / f / g / gif / h / hr / k / m / o / p / s / t / u / v / vg / vm / vmg / vr / vrpg / vst / w / wg] [i / ic] [r9k / s4s / vip] [cm / hm / lgbt / y] [3 / aco / adv / an / bant / biz / cgl / ck / co / diy / fa / fit / gd / hc / his / int / jp / lit / mlp / mu / n / news / out / po / pol / pw / qst / sci / soc / sp / tg / toy / trv / tv / vp / vt / wsg / wsr / x / xs] [Settings] [Search] [Mobile] [Home]
Board
▼ Settings Mobile Home
/g/ - Technology

Name
Options
Comment
Verification
4chan Pass users can bypass this verification. [Learn More] [Login]
File
  • Please read the Rules and FAQ before posting.
  • You may highlight syntax and preserve whitespace by using [code] tags.

08/21/20New boards added: /vrpg/, /vmg/, /vst/ and /vm/
05/04/17New trial board added: /bant/ - International/Random
10/04/16New board for 4chan Pass users: /vip/ - Very Important Posts
[Hide] [Show All]


[Advertise on 4chan]


File: remove_node.jpg (67 KB, 1191x713)
67 KB JPG
> 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.
>>
>>110371230
use case?
>>
>>110371230
C 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.
>>
>>110371230
yeah thats how i would do it too
>>
>>110371271
right, 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
>>
>>110371270
For a singly linked list? Don't know.
>>
File: 1642836206140.jpg (7 KB, 480x360)
7 KB JPG
>>110371355
yeah 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
>>
File: 17749404896920264070.png (43 KB, 900x700)
43 KB PNG
>>110371230
why 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.
>>
>>110371471
Removal from a list is O(1).
>>
File: 17760310715420127097.jpg (934 KB, 912x2048)
934 KB JPG
>>110371504
dropping whole vector is also o1
>>
>>110371270
None
In any language this is just list.remove(thing)
>>
>>110371471
>some fundamental primitive which should be a primitive in the language itself
nothing primitive about a vector
>>
>>110371546
>In any language
In plain C? Are you an indian?
>>
File: 1692186742592941.jpg (59 KB, 1125x1192)
59 KB JPG
>>110371546
>>110371418
Do you have access to <vector> and <array> and any other std functionalities in systems programming? Let's say you are writing a boot loader
>>
File: 1720384939145.jpg (146 KB, 373x430)
146 KB JPG
>>110371552
it'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.
>>
>>110371669
so it's not a primitive
why would you lie on 4chan
>>
>>110371230
this is shit that should be part of a standard library
>>
>No memory is freed
Toy example.
>>
>>110371763
>linked list
>allocates individual nodes
just how indian are you?
>>
>>110371418
>C
>Generic containers
Oh, I see what you did there.
>>
File: 1786670041268358.jpg (257 KB, 1242x1009)
257 KB JPG
>>110371230

That'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.
>>
>>110371613
Yes. 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.
>>
>>110371739
How 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.
>>
>>110371230
Don't care what an ESL thinks.
>>
>>110371230
isn't that an extra ref and deref every loop?
>>
>>110372316
nah it's the same thing
>>
>>110371471
>being a sub-5 genetic refuse nerd fag.
>posts toho
>>
>>110372841
really?
>>
>>110372971
indirect 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?
>>
>>110373035
dumb 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?
>>
>>110373062
sequential data storage with dynamic size
>>
>>110373062
Read the kernel and you'll find out.
>>
>>110373069
you 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 101
Inspiring
>>
>>110371270
>>110371355
>>110373062
They 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.
>>
>>110373129
Deletion will still be painfull, so just use unrolled linked list (if not with basic types, with an index array for each node).
>>
>>110373051
both functions do that



[Advertise on 4chan]

Delete Post: [File Only] Style:
[Disable Mobile View / Use Desktop Site]

[Enable Mobile View / Use Mobile Site]

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.