Learning about linked lists/doubly linked lists in a course. It seems to be a bullshit learning exercise. Do any of you actually use linked lists? Are they even used for anything practical?
>>80340743Your operating system uses them. The runtime of your favorite programming language uses them. You are approaching the peak of mount stupid.
>>80340792Holy fuck. I was just told it was an alternative to an array.
>>80340845It's an alternative to an array list. An array is a much more primitive concept than lists.
>>80340743I use them all the time because C lacks of a STL
>>80340743They are a trick around memory management for variable storage. If you haven't learned about compute complexity yet, don't worry about the fact that there is a million ways to do the same thing.
>>80340743Yep. I had a case where we needed to increment a list in an arbitrarily large collection of lists, based on certain conditions. There were a few different collections that we could use, but they all required some complicated holding a tracking indices. So a collection of linked lists, where we could just call an .increment method seemed much easier to me.Don't think I explained that very well.
.increment
>>80340845You were told that it's an alternative to an array (which isn't entirely correct) and still thought it was stupid academia practice bs? Really?
>>80340743Just use a hash map lolololololo
not really although they're used for a few things, but if it takes you more than 30 seconds to grasp you're too low IQ to be a programmer anyway
>>80340891Depends on what you are doing. If you don’t need quick searches then hashmap doesn’t make any sense and it’s just bloat. For example if you made a queue you’d probably just use a linked list it’d be dumb as fuck as fuck to use a hashmap.
>>80340743Think about how a data structure will look like when you don't order them into next and prev instead use left_child and right_child. Linked list is the entry point in learning tree like data.
>>80341184If I made a queue I'd use a heap so I could prioritize
>>80340743bruh it's shitthe std library implementation sucks if it doesn't 100% cover your use case and it rekts the data locality principle of optimization so you think you're being 420iq programmer possessed by god but you might as well be a pythonfagso you just get fucked in the ass performance wise compared to just removing and shifting an array.
They're one of the most common data structures around you dense fuck.
>>80340792Member when Bjarne Stroustrup said we should avoid LL?
>>80340743I’ve used them many times in my career. Babby’s first data structure. You don’t need them if you’re only interested in being a low income code monkey They are like arrays in the sense that they’re a way of maintaining lists. They’re better in the sense that they have cheaper insertions. Also a good use case for recursion
>>80340883Me too, was it for an OS class in denmark?
>>80340845Absolutely not.Arrays operate on the stack with a fixed length, while linked lists and vectors operate as allocated memory on the heap with flexible size. Personally I don't really use linked lists in C, because seeking to the point of the list just to get a certain node's data is inefficient. So I use my own vector implementation (since libc doesn't have one standard) so I can use it like a resizable array with direct insertion and deletion.
>>80341731No https://www.geeksforgeeks.org/variable-length-arrays-in-c-and-c/
>>80341759>NoVariable sized lengths != flexible and resizable lengthsint a = 5;int arr[a];you can't resize arr after it's declared. Sure, if a was something passed to a function, the array would be different length each time it's declared, but it's still fixed length.
>>80341801When you use a vector class it is just an abstraction using arrays under the hood.
>>80340743Everything in that course, assuming it's a data structures course, is used heavily everywhere.
>>80341828No, it's not that simple. Arrays are ALWAYS on the stack, they are local variables that get deleted once whatever block they were declared in goes out of scope. In an array, each member is directly in front of the other in memory. The array variable itself is just a pointer to the beginning member at 0, which is why pointers are the same as arrays. arr[2] is the same as arr+2Linked lists are chains of allocated chunks of memory, they are do not need to be directly in front of each other, because each node's struct has the pointer to the next node. While vectors do indeed have an array of pointers to whatever data they hold, that is still an array of allocated memory at different position of memory on the heap. The array is just used to easily look up each pointer
>>80341731not defining the length of the array as a variable pleb
>>80341929Lmao its still fixed length, what are you arguing about. Do you think if you change the variable that the array size will change too, don't be a dumb dumb
>>80341911>Arrays are ALWAYS on the stackNo you’re a brainlet int* a = malloc(sizeof(int)*N); Is heap allocated. Only the pointer goes on the stack. The array goes on the heap
>>80341970You are being language lawyered faggot. Pointers aren't arrays, not even if they point to a contiguous section of memory.
>>80341911Do you know what the stack is?
>>80341731>Personally I don't really use linked lists in C, because seeking to the point of the list just to get a certain node's data is inefficient. So I use my own vector implementation so I can use it like a resizable array with direct insertion and deletion.Moving data around on every insert/delete, invalidating pointers to elements, and calling realloc() is not exactly free. If you don't need the random access a linked list may be more efficient, not less.>>80341759VLAs are basically abandonware at this point, and tend to conflict with runtime stack-checking and static analysis. I would avoid them unless you're working on embedded or kernel stuff where you can't rely on or don't have a malloc equivalent.>>80341911>No, it's not that simple. Arrays are ALWAYS on the stackAn array is just a sequence of items of (usually) the same type. Being resizable or not, residing on the stack or heap, is irrelevant. Some languages have "static" and "dynamic" arrays and terms like "vector" are reserved for mathematical types. The C family does not define programming.
For queues I normally use this. Guess you could use an array though. They're easier to work with that arrays or vectors for some problems.
>>80341984Arrays are *always* pointers in c. Brackets are just a convenient way of dereferencinga[5]=6;And(*(a+sizeof(int)*5))=6;Are functionally identical. Try it yourself.
I was under the impression that lists in most programming languages were just linked lists?
>>80340743>Do any of you actually use linked lists?All the time, they're probably the most common "datastructure" if stretching that term hard.
>>80342036More typically lists are arrays with some abstraction to make them seem more dynamic than they are. Linked lists typically have hidden costs that they don’t teach in your intro class that have to do with the cacheing structure of your machine and the minimum dynamically allocatable block.
>>80342030No, you fucking retard. Arrays are a completely separate C-language construct as specified in the standard. They are also implicitly convertible to pointers so that you can dofoo a[5];foo* b = a;without the compiler telling you to go suck a bag of dicks. It doesn't matter what the underlying operations are in this context. An array is an array and a pointer is a pointer.
foo a[5];foo* b = a;
>>80340891what's life like post-op anon?
>>80342066use the language for more than a week you fucking retard, the only difference between int a[5];andin a=malloc(sizeof(int)*5);is that the malloc version is on the heap, they're both arrays.
int a[5];
in a=malloc(sizeof(int)*5);
You need them for binary trees. Never used either of them except for the time I took the algorithms and data structure class in uni
>>80342036They're usually linked lists. Some of the languages that struggle with memory and performance provide alternatives based on arrays like Java's ArrayList.
>>80341970I meant explicitly declared arrays, because >>80341759 was implying the fact you could declare them with variable lengths meant they were somehow equally flexible as lists.
>>80342066They’re the same type bub. If what you were saying was true and one was on the stack and the other was on the heap, then assigning b to a in your example would require an expensive copy. In fact it does not. Because they both type foo*, so you’re only copying your machine’s native pointer size. And moreover, they’re both referencing the same block of memory after you copy the pointer. (Ie the copy is shallow)
>>80342086I've been using C for longer than you have been alive you little shit. You have never read a single page of the standard and you are embarrassing yourself.
>>80342117you're both embarrassing yourselves, sperging out about semantics
>>80342112Nice way to miss the point of the post, nigger. God I fucking hate zoomer shitters.
>>80342066Arrays are always pointers but pointers are not always arrays
>>80342141>made two contradictory impossible statements about the language>missing the point Kek lrn2code
>>80342066They're the same and this concept has an entire chapter (chapter 5) dedicated to itself in K&R
>>80342144> Arrays are always pointers but pointers are not always arraysIn C they kinda are because their memory model is built on arrays. So any time you’ve got a pointer you can always buffer overrun it using the bracket operator. (It is why C has such poor security)
>>80342165Almost the same. Unlike pointers arrays can't be reassigned to point to something else.
>>80342184Well yeah that's what I meant. Arrays have guaranteed allocated memory for them in the next address, but any random pointer doesn't and can be accesing illegal memory by being incremented and deref'd with [], therefore it should not be treated like an array and use []
>>80342213*unless it's an array on the stack or vector on the heap
>>80342213Any array can be accessing illegal memory too. Character strings are notorious for this
>>80342227No what I mean is you can't expect any pointer to have allocated memory in front of it
>>80342218Vector is a c++ class. When you heap allocate an array. It is still just an array. Fwiw you should very rarely put an array on the stack as you’ll easily smash your stack doing that
>>80340743Theyre quite nice for their simplicity and ease to grow dynamically - but a brainlet like you need not worry about that
>>80342243Yeah but the stack is way faster than the heap so it has it's advantages for small shit, if it's something huge then chances are it's something used frequently in the program in which case any sane programmer would have it as persistent data on the heap
>>80340743they are very useful in functional programming. defining combinators using recursion on lists is very natural.
>>80342243It's probably far worse to have them on the heap today assuming you're not allocating every single buffer separately as an attacker will have more access to state.
>>80340866An array list uses a linked list. An array in its most basic form is just contiguous memory.
>>80342354>An array list uses a linked list.???
>>80340743its very helpful. you should try to learn what you can do with it before trying to mastering/understanding/practicing.
>>80342354Do you mean a linear *dynamic* array?
>>80342301It is actually pretty rare to have functions that are compute heavy but not memory intensive. (At least compute heavy to the point that you need to optimize a c program)
>>80342117>I've been using C for longer than you have been alive you little shit>still doesn't think pointers are arrayseither you're larping (100% chance) or you have a learning disorder
>>80342471Pointers aren't arrays. They're references to memory. You can represent an array using a pointer to it's first element, but that's not the same thing.
ITT: Babby programmers trying to find their way out of Dunning-Kruger valley. Holy shit this place is crammed full of retards with zero actual experience.
Can't you just malloc to have an array on the heap? And resizing is just realloc, and if it fails then malloc + memcopy.
>>80340743>are they even usedDepends on the language you use and what exactly you're doing. Most high level (modern) languages have dynamic size arrays so lists don't have to be used as "an alternative to arrays" and you'll never see them used in such a way.
>>80342518>Pointers aren't arrays. They're references to memory.Arrays are just references to memory, anon
>>80342604No, an array is a particular usage of memory.A collection of wood and nails isn't a house. People aren't piles of meat.
>>80342621>an array is a particular usage of memoryA pointer is a particular usage of memory
>>80341671>They’re better in the sense that they have cheaper insertions.Insertion and removal. That's the point that most of this Thread mises.>>80340743>Are they even used for anything practical?A good example is distributing units of work to a threadpool, where concepts like work stealing can get really expensive (to the point that it's not even worth it and you're better off just letting some threads idle) with large arrays.
>>80342754>Insertion and removal>remowal?You still need to traverse the list to remove an element
>>80342764>You still need to traverse the list to remove an elementFor insertion/removal in the middle of the list, yes. When dispatching to i.e. a pool of worker threads, 99% of the time you'll insert on one end and remove from the other end. With lists, that means updating 2-3 values - depending on the type of list (single- or double-linked). With arrays, one of those two operations requires shifting every single element by one position.
>>80342940>99% of the time you'll insert on one end and remove from the other endThats assuming what people will do with it. Thats not how it works
>>80342940If you’re only inserting and removing at the ends you can use a ring buffer for O(1) performance
>>80340743>It seems to be a bullshit learning exerciseYou shouldn't have this attitude mate it isn't going to help you at all.
>>80342161what level of sperg do you have to be in order for both of you to continue this conversation
>>80342956Even if your use case involves insertion/removal in the middle, it's still updating a few pointers vs. shifting the position of all elements after the spot. Traversion is usually pretty cheap in comparison, as it's read-only.>>80342958If you don't need the option to insert/remove in the middle and can live with a constant size (i.e. blocking insertion until a spot is available), then yes - a ring buffer will perform even better.
>>80343097>cheap in comparison, as it's read-onlyYour intuition about performance is wrong. Reading is slower than writing, because reading blocks. Writing can be deferred. And random access is slower than sequential access.Both operations are O(n) - in the linked list, you need to iterate the list, and in the array you need to shift elements. But the array will be faster by a constant factor because it's sequential instead of random access.
>>80343097>If you don't need the option to insert/remove in the middleA ring buffer will still be faster even with insertion in the middle.Copying n sequential values is vastly quicker than following n randomly scattered pointers.
>>80343148>Reading is slower than writing, because reading blocks. Writing can be deferred.Writing involves some type of memory barrier, unless you're in a single-threaded environment. Which you shouldn't be if you care about performance, as it's $current_year and even low-end hardware is 4t or more.
>>80340845>I was just told it was an alternative to an arraythey are capable of the same things, but investigate their time complexities. if they aren't teaching you that, jfc the zoomer controlled future is bleak
>>80340743use python/perl and forgot all this shita internet browser for 17 lineshttps://gitlab.com/SSS8555/python_g6_client
>>80342030look up array decay
>>80343683this kills the brainlet
imagine using pajeet lists instead of vectors
>this thread
I've programmed professionally for 5 years and have never used a linked list once. It's a cute learning exercise though.
>>80341695No, it was a problem that came up recently at my job.
>>80341911In C, arrays declared outside of main are in the heap. Arrays declared inside main are on the stack. And if you use malloc its in the heap.
>>80340743newby questionwhy would you use a linked list over an array?
>>80345077Strings in many languages.
>>80345077This is true in C but not in other languages with dynamic array sizes>Cheap and easy to extend>Not a fixed size>Can be modified to be more feature rich (see single vs double vs circular linked lists)
>>80342086sizeoff(arr) will give you the actual memory usage of the array, but sizeof(ptr) will just give you the size of the pointer. They are very similar but not the same.
>>80345077Big structs can be handled faster via linked lists, since you don't have to move the memory to sort the list.
>>80345117you forgot>dogshit iteration performance>>80345736>array of pointers>???>profit
>>80340891Any hash map that stores multiple values to one key is using a linked/doubly linked list.
Sometimes I feel bad about how much I’m progressing on my degree then I read threads like this and remember that /g/ is full of self taught retards who don’t understand basic concepts and feel better about myself
>>80345992A lot of them will use an array. For example if your hashes have a range of 256, you can allocate an N*256 array, to give you N space in each bucket.
>>80340743No they're useless in all cases.
>>80340743There's always a better option than a linked list.
>>80341406> he doesn't make his own faster implementationlook at this retard
>>80340743>Do any of you actually use linked lists?No but it's a good way to learn about pointers/references.
>>80345077You often see them in metadata, for example scatter-gather DMA headers. In that case you’re building a dynamic data structure that needs to be connected flexibly and you’re not concerned with the performance of your list traversal.
>>80345992Not always. Pooling can be done with arrays. Just the only problem is if one of the pools fill up you have to rehash. Linked list pooling doesn’t have this problem but slightly slower because you get cache misses. If you are pretty confident you won’t fill up pools then array is fine
>>80346194*Another example is the PCIe extended capability space. It has a linked list for storing device capability and configuration structures
>this threadwhen will /g/ stop being retarded?
>>80340743Linked lists CAN be faster than whatever your language standard library offers you, but only in small hobby projects. They're also useful when used as a ring buffer on very low level. In most cases you won't have any benifit cause the List your language offers you include hard-to-implement features like preallocating, indexing and garbage collection and all kinds of heuristic algorithms that make access faster
>>80346142That's not true, what if my goal was to create a discontinuous block of related pieces of memory linked together with pointers that has worse performance as it grows??
Why are you guys dissing linked lists so bad?It's not useless.>The inode (index node) is a data structure in a Unix-style file system that describes a file-system object such as a file or a directory. Each inode stores the attributes and disk block locations of the object's data. File-system object attributes may include metadata (times of last change, access, modification), as well as owner and permission data.
>>80342377lurk/study more
>>80346309They are retarded. They think it’s faster because you don’t get cache misses but instead you run into issues of reallocations bringing your whole computer to a halt.
>>80346309Still, if you're working with a garbage collected language or a language that offers a standard library, you should prefer using that instead of programming your own
>>80346330Obviously this is true but this doesn’t make linked list bad or worthless. Just means you should use built in data structures when they are available
Data structures are pointless, who needs variables anyways, constants are a constant waste of time, sequential circuits were a mistake, combinational circuits are useless, who needs to know how to process math problems, addition is pointless, who needs numbers anyways!
>>80346330If you are working on embedded system, lists are your friends.
>>80346395If you are using linked list in an embedded system you are dumb as fuck. What circle of hell are you in if you are writing embedded code that has dynamic memory. Horrible practice.
>>80346395If you're working on embedded systems, chances are Wind River or whatever you're building on already offers you a great list implementation
>>80346440>>80346395Please don’t use dynamic memory in embedded systems.
>>80346472You don't even need dynamic memory, the adequate library will map the RAM you need and just give you an abstraction that feels like dynamic memory
>>80346534If you are doing this you don’t need a linked list then. You would just be using an array with some abstraction layer. You are writing an embedded systems it should be 100% deterministic.
Looks like I got outted as an embedded retard
>>80346558> You are writing an embedded systems it should be 100% deterministic.Interrupts are unavoidable
>>80346584Interrupts are deterministic. You can calculate the max memory allocation from pushing shit on the stack and the max time delay caused by interrupts stacking on top of each other pretty easily so you won’t miss any deadlines on your system. So you could find out what’s the worst case scenario for memory allocation and “latency”. If you have dynamic memory this is not possible or is way more difficult.
>>80346656Where can I learn about this so I don't embarrass myself next time
>>80346656>Interrupts are deterministicLol no. That is definitionally the opposite of true. They’re manageable but not deterministic. And fwiw dynamic memory allocation is far more predictable
>>80346703Calculating the worst case for dynamic memory is impossible. IF IT IS then you wouldn’t be dynamically allocating shit and just allocate the worst case amount of memory you will need to allocate statically. It makes 0 sense to dynamically allocate memory in an embedded system.
>>80340743>Learning about linked lists/doubly linked lists in a course. It seems to be a bullshit learning exercise. Do any of you actually use linked lists? Are they even used for anything practical?Do not try to consider "linked list" as some kind of specific structure, it's an abstraction to a container that can do few things - element can be added/removed/modified anywhere without moving too much stuff around, and can be traversed in either direction but indexing without additional supporting structure is impossible.Examples are multiple and plentiful. Just try to start from the problem you want to solve not from algorithm name. For example try to find efficient way of keeping a list of tasks to do.
>>80342377this retard is talking about implementation details of java arraylist and linkedlisthe probably thinks it's the general rule for arrays and lists>>80346314java is not the only language in existence, you should lurk/study more
>>80346703And yes interrupts are deterministic if you don’t miss use them. they take a deterministic amount of time do shit and deterministic amount of memory. So it’s true they aren’t 100% deterministic probably by the textbook definition but they are deterministic in the sense of what actually matters ie finding out you won’t run out of memory and finding out you won’t miss deadlines.
>>80346731It is similar to interrupts in the sense that both contain an overflow case. You can have more interrupts than your stack pointer can accommodate or more dynamic memory. They can both be mitigated, but not eliminated, as risks by good design>>80346668What he’s talking about is highly hardware dependent and only doable in principle in simple systems like babby’s first arduino project. High reliability systems use TDM because interrupt driven systems are not fully verifiable in principle
>>80346805You can easily calculate the amount of memory worst case for all your interrupts stacking and worst case in the code. Find worst case what function has the most shit on the stack and with all your interrupts stacking on each other this is super easy to do. There are tools to do this.
>>80346851Babby’s first arduino project
>>80346851So in fact you can 100% verify you will never run out of memory.
>>80346904You are retarded. If you think you can’t verify and can calculate the max memory usage of your embedded system you are so retarded no one can help you.
>>80346931I suspect you’ve never worked with an embedded system of any complexity. (How do you fully verify a system with a legacy pcie controller? Where a galaxy of different hardware may be added in different slots. Have you even considered how meta stability or thermals can affect the timing analysis of a high performance system.) And never in the real world. (Where you rarely have complete control over the design of your system. Even if you’re the system architect of a newly developed system, your use case will probably involve some crappy standards that hamstring you)
>>80347064>what if your system takes a bunch of random shit and I’m running an OS that handles shityou aren’t really writing an embedded system then. It’s a pesudo embedded system. Your constraints aren’t probably that bad. Your probably have globs of memory and don’t have to worry about it unless you are doing crazy shit. Your OS probably uses dynamic memory too so it’s impossible to calculate the max usage. Plus if your run out memory it doesn’t matter because you can just reboot.>thermalsmay cause some variability data sheet will tell you worst case clock speed. If your time constraints are so slim that slight variations in clock speed from temp can fuck with you something is really wrong. Plus if you use an external clock these will be even slimmerI work at Lockheed and we calculate the max memory usage of our system and verify it. The systems we write aren’t simple.
>>80347243>I work at LockheedLol. Lockheed and the other dod contractors are still using 80s/90s tech. No wonder your instincts are so off base. t. Former Northrop Grumman R&D, left for big tech> If your time constraints are so slim that slight variations in clock speed from temp can fuck with you something is really wrongOr you’re working in a cutting edge system and trying to push the performance envelope
>>80340792When will I ever make an OS or a programming language?
>>80340743No, they are bad for caching. I use std::vector, std::map and std::set for everything. Implementing your own containers and sorting algorithms is a meme and something you will never need outside a CS degree. 99% of the time the std lib is the way to go.
>>80346763>java is not the only languageJava also doesn't call LinkedLists as ArrayLists. ArrayLists are dynamic arrays with amortized insertion costs. It's not a LinkedLists.
>>80340743There are some _very_ niche cases where linked lists are preferable. Contiguous memory is strongly preferable in all other cases.
>>80348788I know, this is what I'm talking aboutthe dude is mixing everything up and act like lists are always arrays or soe shit
Theyre actually bad to use unless you have a very specific use case. You're almost always better off with a dynamic array/std::vectorhttps://youtube.com/watch?v=YQs6IC-vgmo
>>80348983>the dude is mixing everything up and act like lists are always arrays or soe shitEverything is an array. :^)
>>80340743Text editors often use linked lists. The text buffer is stored as a linked list of structures that contain a pointer to a heap-allocated string, the number of allocated bytes, and the number of bytes used, and maybe the line number. When you insert a new line, you don't want to have to copy the entire text buffer, you just want to modify the "previous" and "next" pointers of the current and next line. This makes inserting lines O(1) instead of O(n)
>>80340891using System.Collections.Generic;public class LinkedList<T>{ private readonly Dictionary<ulong, T> _dictionary = new(); private ulong index = 0; public void Add(T value) { _dictionary[index++] = value; }}Am I doing it right?
using System.Collections.Generic;public class LinkedList<T>{ private readonly Dictionary<ulong, T> _dictionary = new(); private ulong index = 0; public void Add(T value) { _dictionary[index++] = value; }}
>>803490374chan replies are a linked list. Prove me wrong. Protip: you can’t
>>80349245it's a fixed-size id followed by a fixed-size length and then characters represented by numbers, so it quite literally is just an array of numbers
>>80349312>fixed-size idYou mean a pointer? > followed by a fixed-size length and then characters represented by numbersYou mean a struct/record?
>>80349362>You mean a pointer?Yes, an offset in memory which coincidentally also is just an array of numbers.>You mean a struct/record?You mean named offsets?
>>80349396>a struct with a pointer to a subsequent element is not a linked listDon’t mind me. I’m just adding another link to this list. FWIW, at the level of abstraction of something like 4chan, data is cloud stored and split between multiple processors / hard drives. There is not necessarily a contiguous region of memory at any level of abstraction.
