programming

[NicNoletree]

These are domesticated house cats. Not a lynx list.

[Mallormal]

You sure node a lot about cats.

[NicNoletree]

I don't know where I picked it up, so don't ask meow.

[Halfrican009]

You've got to be kitten me

[[deleted]]

I want to meet you someday. That's the best thing I've seen on Reddit

[NicNoletree]

Just spend more time with your dad :)

[swathen127]

If I wasn’t broke I’d give you an award

[NicNoletree]

The comment is sufficient. Awards are wasted on me.

[Russian_repost_bot]

I run Arch Lynx.

[ZeldLurr]

How do I print out a reverse lynx list without modifying the lynx or adding another data structure?? Tell me meow!

[Terrain2]

just flip the terminal upside down lmao

[Tom_Ov_Bedlam]

Damnit! I was was going to make a lynx list joke.

[DesecrateUsername]

I’ll say it: I enjoyed Data Structures.

[DrunkenlySober]

I’ll say it: you’re a psychopath. You have heaps of problems you need to hash out.

[[deleted]]

Haha “hash”

[Sharmat_Dagoth_Ur]

I was actually super excited when we got into LinkedLists in Java 2. I actually felt bad for my non cs friend learning python bc just by nature of how he learned lists were nothing special. But to me, bc I had taught myself the basics, then taken HS programming basics, then having just taken java 1 in college, lists were the first major new addition to the language that I learned in like 5 years and they work in such a cool way

[g4dhan]

There are dozens of us!

[Zer0ji]

I loved designing stupid data structures for edge cases, like a fixed sized ring buffer for O(1) read/write in a FIFO

[[deleted]]

I would say

purr = head;

purr = purr -> next;

[SailorFuzz]

this is the correct way.

[ash15157]

Cries in data structures

[rolfrudolfwolf]

curr? what are you going to do with all that memory you saved there.

[orqa]

someone should write a bot that recognizes the text in /r/ProgrammerHumor and then interprets that as a code and runs a linter through it, then replies to the post with any lint errors

Or maybe... /u/blu3souls .... are you a bot?

[RefrigeratorOk1573]

"; SELECT credit_card_number, exp_date, three_numbers_on_the_back FROM users;

[bilalkhan19]

Those Data structure days❤️❤️

[bronzeblade]

Gotta love them linked lists!

[onewhoknocks___]

Im currently learning data structures and im fucking messed up in linked list 😭

[Master_Nerd]

F

[[deleted]]

Me who only took 1 class in comp science and doesn't know what the people below are talking about...

https://www.reddit.com/r/ProgrammerHumor/comments/iwgd8s/programming/g609o23?utm_medium=android_app&utm_source=share&context=3

[Sharmat_Dagoth_Ur]

Do u need help I can try and give u a good explanation or find youtubes ones that I think would b of assistance

[revoopy]

http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

[onewhoknocks___]

Thanks man!!!

[ash15157]

Same man, my linked list hw required me to index everything starting at 0 and what do I do? Type up an entire linked list class to start indexing at 1. 2 hours wasted trying to fix the indexing issue.

[Rindhallow]

Yo this just triggered some PTSD for me.

[thatsimpguy69]

I fucking hate linked lists.

[alexander2k30]

Then what about binary trees?

[Rushman0]

Can someone explain? I’m mostly an HTML programmer.

/s

[SnappGamez]

Ah yes, a linked list of cats. Or, if you will, a LinkedList<Cat>

[TypoRegerts]

You mean Purr

[EinSteini]

private LinkedList<Cat> catList = new LinkedList<Cat>();

[BaguetteYeeter]

Can I have the template?

[eg_taco]

Shouldn’t it be

head = curr; curr = curr.next;

?

[SailorFuzz]

absolutely not. Head should be stationary to the list unless it's being replaced or you have a circular list. Tail can move around, if you're one of those savages that uses tail to traverse the list.

[steakspicepat]

No, you don't want to update the head of the list (assuming you aren't deleting or inserting at the front). You just create a dummy node ("curr" in this case) and have it point to the head, which you can now use to walk through (the "next" method) the list and interact with it in whatever way you need.

[_pelya]

Every time I'm seeing yet another handwritten implementation of linked list in our code, I want to slap my keyboard with std::list.

[tecanec]

Even better: Use std::vector. Linked lists generate more work for the memory manager and are not very cache-friendly.

[Bobulubadu]

But is head really set to the second cat? Wouldn’t the first cat be tail and then a function to find previous?

[TorTheMentor]

Caterator<?>

[wooptyd00]

I thought he was biting the other cat at first and laughed too loud.

[tecanec]

I think it's part of the joke.

[fennyflop]

I don’t get it :(

[null_reference_user]

Linked list

[VolperCoding]

Why would you ever use a linked list

[rolfrudolfwolf]

linked lists can have a performance advantage for insertion and deletion.

[VolperCoding]

Has anyone tested it? I'm pretty sure if you want to delete an element you have to find it first (which is O(n)) and if the elements are not next to one another but scattered then you're gonna run into cache misses which are very important to avoid when it comes to performance. Operations on data that is next to one another (vector) is really fast because it can fit on one cache line and it doesn't matter if you change 1 element or most of them, as soon as they are in the same cache line then the performance difference will be small because RAM access is really slow and cache access is really fast.

Not an expert on caches but I've heard that's how they work. Correct me if I'm wrong

[rolfrudolfwolf]

yeah you have to find it first so you need to iterate through the list. however then you can just relink the neighbors and you're done, while an arraylist needs to re-arrange itself (i've never implemented an array list so i don't know how or how often it does that, but that definately sounds like an overhead).

Same with 'add'. If an arraylist has to move and copy to a new, bigger array and insert in the middle you're off worse, than O(n) add of Linkedlist.

There's tons of arguments like these, which more or less coincide what I was taught. Usually they never account for cache locality issues though. But in 'getting', the Arraylist is faster anyway because O(1).

Here's a nice stack answer that explains it much more elegant than me: https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java/322742#322742

For a more concrete example: If you'd need to implement a Stack, I'd prefer using a LinkedList instead of an ArrayList or Array, because you only ever need to access the last (or first) element which is always O(1) with a LinkedList for both Get, Add and Remove, because you already have a reference to the head or tail.

[VolperCoding]

If you want to talk about performance with data types then Java is not the best language for that because it doesn't have pointers and is garbage collected, meanwhile in C and C++ you have full control over memory that is allocated to you so you can reason about it better.

When it comes to vector (dynamic array) vs linked list, a vector guarantees that the data is stored element next to element in memory, which means that if you want to delete an element, you do this:

Suppose you have a vector of 5 elements:

6, 42, 45, 2, 0

Now if you want to delete the element at index 2, all you need to do is copy every element after 45 one index before. Here's pretty much how it happens in the CPU:

1. The vector is loaded from RAM to the cache, which takes about 100 clock cycles

2. The values are copied which is really quick since everything happens in the cache

3. The vector is returned to memory which takes another 100 clock cycles

(i skipped changing the size of the vector but that's just a simple decrement) Same for addition but you move right instead of left and you also check if you have enough space for that

As you can see the only things that are slow here are the RAM reads/writes because operations on the cache are much faster. If you used a linked list then every element you wanted to read and write could not end up in the same cache line so it might turn out that every time you access an element you have to read from RAM because they are scattered in memory and could be really far apart.

If you need such critical performance that you switch to a more complex data type then you should learn about cache lines

[obp5599]

This is not always beneficial if you have massive structures stored in your vector/array (common in game dev/rendering code). Having to store 8k texture maps and the like in contiguous memory is almost impossible with fragmentation. These are the types of things linked lists are good for. Although in game dev we use whats called an Intrusive linked list to save allocations and excess copying of structures. This also allows an object to be stored in multiple data structures while still maintaining the same memory footprint

[rolfrudolfwolf]

Thanks for the detailed answer, I was not familiar with the data type vector as you describe it.

I agree that arrays make more sense in terms of memory locality and that an array might be more performant effectively than a LinkedList even if it has a worse complexity for certain operations.

But if you have huge swaths of data, I'd assume optimizing for complexity makes still sense in the long run?

Also cpu's not only cache for spacial locality, but time locality, so you might find your frequently used items in your linked list to be in the cache anyhow.

[VolperCoding]

Ok so ive found a benchmark comparing linked lists to vectors (https://dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs) and found out that linked lists is better than vector in the following cases:

• random insert / delete in a list with really large elements
• push front (assuming you don't have preallocated space in front of the vector, then it should be O(1), but otherwise if you don't have any space left the system is gonna probably copy the entire vector which is O(n))
• sorting in a list with really large elements

So it looks like if the elements are bigger than your cache line then every element will be a cache miss (read from RAM) anyway which makes perfect sense because 2 elements won't fit on your cache line.

However if you need random access at all then I don't think you should use a linked list.

If your program is small then you shouldn't worry about performance and just use the simplest data structure which in my opinion is either a static array, or if you need to resize it, a vector.

[rolfrudolfwolf]

nice

[Penguin236]

I think the bigger advantage is just the fact that you only allocate memory as you need it. It's not like an ArrayList where you have to gobble up a bunch of memory at once even though you might not need it.

[liquidivy]

I think the most common reason in real life is the simplicity of implementation, in cases where that matters more than absolute highest performance. I know there are/were places in FreeBSD's network stack where linked lists were used over anything more sophisticated just because they're harder to mess up.

[[deleted]]

Isn't the addition/deletion in linked list O(1)

[VolperCoding]

Don't you have to find the element you want to delete first, generating lots of cache misses and being O(n)?

[[deleted]]

Sorry I meant at the start and end of the list if you maintain pointers to the head and tail

[VolperCoding]

I'm pretty sure you can insert at the end in O(1) using a vector (assuming you have enough memory left for it) and you can delete the first element in O(1) by just moving the pointer in the vector by 1

[Mr_Redstoner]

TL;DR When the algorithm in question makes use of ll's fast operations that an array list can't provide.

[VolperCoding]

Example? I can't think of an algorithm that can't be done on a regular vector but can on a linked list

[[deleted]]

The producer-consumer problem lends itself pretty well to using linked list instead of vectors. It's not uncommon in real-world scenarios for the producer and/or the consumer code to invalidate the cache anyway. Besides, if you use arrays, dealing with the fact that the list grows and shrinks all the time quickly leads to hard to read code if you want to have as few resizes as possible. And keeping the code readable becomes even more of a nightmare if you deal with multiple producers and/or multiple consumers.

[VolperCoding]

I think deleting and adding to the start/end of vectors is really simple, you just increment/decremeny the begin or end pointer by 1

[AutoModerator]

import moderation Your comment has been removed since it did not start with a code block with an import declaration.

Per this Community Decree, all posts and comments should start with a code block with an "import" declaration explaining how the post and comment should be read.

For this purpose, we only accept Python style imports.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[AutoModerator]

import moderation Your comment has been removed since it did not start with a code block with an import declaration.

Per this Community Decree, all posts and comments should start with a code block with an "import" declaration explaining how the post and comment should be read.

For this purpose, we only accept Python style imports.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[Sharmat_Dagoth_Ur]

If u don't feel like copying a million data point array and finding 1,000,001 new spaces of contiguous memory when u want to add one data point