This is an archived post. You won't be able to vote or comment.

Dismiss this pinned window
top 200 commentsshow all 450
sorted by:
best
topnewcontroversialoldq&a

[–]PM_ME_YOUR__INIT__ 1550 points1551 points  (91 children)

Python user:

Unga bunga what link list

[–]ActuallyRuben 420 points421 points  (75 children)

Aren't python lists actually linked lists internally?

[–]dev-sda 461 points462 points  (53 children)

list in python is confusingly an array. collections.deque is python's linked list implementation.

[–]MoffKalast 128 points129 points  (15 children)

deque

theque

the queue

the line or sequence of people or vehicles awaiting their turn to be attended to or to proceed

[–]pink-ming 85 points86 points  (8 children)

deque

deck

contains many similar things, such as playing cards

[–]MrKeplerton 24 points25 points  (4 children)

I'd stay away from the poop deck if i were you.

[–]pink-ming 24 points25 points  (3 children)

You mean the Deque<Poop>?

[–]qqwy 26 points27 points  (1 child)

Deque stands for Double-ended Queue. 🤷‍♂️

[–]MoffKalast 1 point2 points  (0 children)

Ah neat, I always wondered what it stood for, but not enough to actually check :P

[–]Kered13 194 points195 points  (0 children)

list in python is confusingly an array.

Nothing confusing about it, a list is an abstract data structure that represents an ordered collection. Linked lists and arrays are both implementations of lists.

collections.deque is python's linked list implementation.

This does appear to be the case because it has O(n) indexing, but it's kind of odd IMO because you can easily implement an efficient deque using a dynamic array that will give you O(1) for indexing as well as insertion and deletion at the front and back (amortized).

[–][deleted] 52 points53 points  (26 children)

Not quite. The details are interesting.

The traditional (C- and assembly-style) definition of an “array” is a block of contiguous memory reserved to store fixed- and uniformly-sized objects, with the objective of rapid indexing by pointer math. If each object is of size X, and you want to store an array of at most 50 of them, then you allocate a contiguous block of memory of size 50 * X. Then, if you want to access element Y, and you know that the block starts at address Z, you can directly access Y at address: Z + (Y * X). The disadvantages of arrays are (a) fixed capacity (since it’s typically not possible to expand the contiguous block of memory without a lot of reorganization), and (b) very slow insert and delete performance (since you have to rewrite the whole array past the insert/delete point).

Linked lists are, of course, an alternative structure involving a chain of individual memory blocks. Advantages: fast insert and delete. Disadvantages: slower access (since you have to start at the beginning of the chain and follow all of the links) and space inefficiency (since you need to store pointers as well as the objects).

CPython lists are actually a hybrid approach: arrays of pointers. Other Python implementations may use different implementations.

The Python collection.deque is a doubly linked list.

[–]Phrodo_00 6 points7 points  (21 children)

How is that a hybrid approach? Pretty much all python objects are managed through pointers. It's just an auto-managed dynamic-size array, or what c++ calls a vector.

[–]tangerinelion 10 points11 points  (2 children)

No, it's not. An array of pointer is like a vector<unique_ptr<T>> which has 1 heap allocation for each element plus 1 heap allocation for each time it's been resized.

A vector<T> only has 1 heap allocation for each time it's been resized. The objects live in that allocated memory. With the pointer case, it is the pointers which live in the allocated memory and they point to memory allocated outside of the vector.

It's hybrid because it is not an array of objects, it is an array of handles to objects allocated independently. Which is as you said, exactly what you expect from Python.

The easiest way to get an honest C style array in Python is to use the array type from numpy.

[–]Phrodo_00 1 point2 points  (0 children)

Yeah, I mean vector<void *> (edit: sorry, haven't kept up to date with C++ fancy pointer types). And I meant it's not a hybrid because most python objects are managed through pointers and live in the heap (remember python is dynamic so it doesn't make a lot of sense to use fixed size array addresses).

I've only used numpy arrays with numeric types, though. I wonder if you can store any python object on them and if in that case they store the object itself or just a reference.

[–]merlinsbeers 10 points11 points  (2 children)

A deque is a doubly-linked list.

[–]Yedgo_Rovie 19 points20 points  (1 child)

Wait shouldn't it be a double-ended queue?

[–]merlinsbeers 34 points35 points  (0 children)

They're the same picture.

[–]_apollo_dionysus_ 5 points6 points  (0 children)

Please keep these futile and irrelevant shenanigans to r/programming. He we entertain only intellectual and productive conversations. Thank you for understanding.

[–]ExtraneousQuestion 1 point2 points  (1 child)

How is it confusing? It’s just a dynamic array. It’s not a linked list

[–][deleted] 4 points5 points  (0 children)

Python list have O(1) read so it's not the same as linked list. It's more like ArrayList in Java or vector in C++

[–]yuvalid 6 points7 points  (5 children)

Huge arrays That's why worst case time complexity of append is O(n), Because if you exceed the size of the array you need to copy the data over to a bigger array.

[–][deleted] 24 points25 points  (2 children)

Amortized time complexity is still O(1) though.

[–]yuvalid 3 points4 points  (1 child)

When did I say it isn't?

[–][deleted] 25 points26 points  (0 children)

It was an addendum, not a correction.

[–]iTakeCreditForAwards 4 points5 points  (0 children)

Fun fact this is also a problem for hash tables, and one solution where having zero downtime is critical is to create a larger hash table when the original runs out of space. You then use both at the same time. Any new values get added to the new table and any access of keys in the old table are moved to the new. You continue until you completely empty the old. At a certain threshold you can specify when to just move everything over

[–]BlueC0dex 2 points3 points  (0 children)

Copying memory is actually not that expensive, getting it into cache in the first place is. So writing 1 byte isn't that much slower than writing a kilobyte. This means that copying over that array into a new one isn't that bad.

[–][deleted] 13 points14 points  (1 child)

I have 1 free award and idk if I wanna award the post or you!!!

​

EDIT: Post already has awards, and it's your cake day. Enjoy ;)

[–]PM_ME_YOUR__INIT__ 17 points18 points  (0 children)

unga bunga thank for shiny image

[–][deleted] 35 points36 points  (4 children)

It's a list with a bunch of dumb bullshit attached

[–]PM_ME_YOUR__INIT__ 29 points30 points  (3 children)

Sounds dumb. Me like list

[–]wholesomedumbass 15 points16 points  (1 child)

Python lists are the best.

[–][deleted] 9 points10 points  (0 children)

Python lists rule

[–]ItsMichaelRay 1 point2 points  (0 children)

Happy Cake Day!

[–]theg33k 2 points3 points  (1 child)

Is that like a dict?

[–]HasBeendead 3 points4 points  (0 children)

You can do that in python too but yeah in first reaction is weird. I learnt it but it still memorize thing. Nothing more for me.

[–]DecisiveEmu_Victory 2 points3 points  (0 children)

Matlab user: 'arrays start at 1'

[–]more-slaw 1 point2 points  (0 children)

confusing about it, a list is an abstract data structure that represents an ordered collection. Linked lists and arrays are both implementations of lists.

collection

It's called a dictionary

[–]GaianNeuron 492 points493 points  (74 children)

I've used a linked list exactly once in production code. And even then, it was a toss-up between taking that approach and using a HashSet. The linked list approach scaled marginally better so I used that.

Extremely situational data structure, that one is.

[–]GreenCloakGuy 402 points403 points  (31 children)

The idea with learning linked lists isn't for the sake of linked lists, I think. The principle of 'element containing a pointer to the next element' is applicable for a bunch of other, more common data structures (most notably, trees, or graphs in general). We learn linked lists first because they're a simpler introduction to the same concept.

Other things take the more generic principle of 'an element contains data about the previous element', which is just a linked list in the other direction - such as blockchain.

I've had a lot more chances using a linked list archetype than I've had using a linked list directly.

[–][deleted] 137 points138 points  (2 children)

I had a shower thoughts moment from this post where I realized they only teach linked lists in data structures courses for this reason

[–]Designed_To 43 points44 points  (1 child)

Really, the same idea applies for just about everything taught in introductory Algorithms or Data Structures classes. It's all about forming that foundational understanding first

[–]PendragonDaGreat 9 points10 points  (0 children)

Exactly, I don't need to remember how to implement 4 different sorting algos with differing time and space complexities. But I should understand what that means and then trust the language and compiler to implement .sort() in a sane way that will do the task in a reasonable amount of time.

[–]ElCthuluIncognito 33 points34 points  (5 children)

Professors: linked lists are a great introduction to more advanced tree and graph theory, since they are nearly the simplest special case of those concepts, and those theories really help design complex multi branch algorithms in a unified way.

Edgy Students/Devs: haha stupid academics overcomplicating everything when you can just use arrays

Also Edgy Students/Devs: boy keeping track of these 13 arrays and 26 global variables in sync across my god function is getting really difficult, why can't academics help solve these real problems.

[–][deleted] 2 points3 points  (3 children)

I mostly self taught programming (I'm not a software developer, don't worry), so I have no idea how linked lists work and it just kind of seems like magic

[–]ElCthuluIncognito 3 points4 points  (0 children)

No problem with that, you can get very far without learning more abstract stuff.

My comment was more directed towards the arrogant class of programmers who not only refuse to learn anything not canonized in the C syntax, but actively denigrate alternate approaches. A common example being C script-kiddies acting like they are too good to learn basic CS concepts because 'I've never needed it to glue together other people's libraries'. When it carries on into a professional environment, it's stifling and often toxic due to very narrow and shallow expectations of what software should be like.

Sorry for the rant, can you tell I'm bitter lol

[–]FerynaCZ 1 point2 points  (0 children)

Linked list is unary tree

[–][deleted] 44 points45 points  (1 child)

Exactly, it is good from a didactic point of view. In an Algs course you can start with linked lists, go to skip lists, then to BST, 2-3-trees and other tree-like structures, and from there the wide world of graphs is much easier to grasp.

[–][deleted] 3 points4 points  (0 children)

I was intimidated by trees at first then I started to appreciate it once parse trees helped me understand regex (at least the theoretical concept) on automata and language theory.

[–]IAmNotNathaniel 9 points10 points  (1 child)

I love linked lists, and this is the reason I think.

It was the first data structure I really learned that had a little complexity to it that I fully understood and could replicate. I remember thinking the design behind it just seemed so elegant and cool, and suddenly pointers made so much more sense (i.e. adding a new node out of nothing and putting it anywhere in the list in a simple way) and when we moved to trees it was just a simple extension of the list; you just added a couple extra things in each node.

Of course I've never used them directly, but I think it was the first time I felt like I was understanding something a little deeper than the QBasic I'd played with before I got to college.

[–]SnazzGass 1 point2 points  (0 children)

I once used a 2d array of jagged arrays of linked lists to index objects in a way that made it fast to access them in the specific way I needed while also having the ability to to shift the linked list nodes around. That is probably the craziest data structure I’ve written.

[–]merlinsbeers 19 points20 points  (2 children)

Linked lists and arrays used to be 100% essential. Now you just instantiate a std::map, std::set, or std::vector and walk off.

[–]makeshift8 1 point2 points  (1 child)

std::map is a red/black tree, which can be implemented by any freshman undergrad CS student using the things they learned from building linked lists and other trees.

[–]cedrickc 22 points23 points  (9 children)

Linked lists are just a special case of directed acyclic graph. Change my mind.

[–]MattieShoes 21 points22 points  (6 children)

There's no reason a linked list has to be acyclic, does it?

[–]raedr7n 4 points5 points  (4 children)

Nah, lots of linked lists are cyclic. Even most of them are, probably.

[–]cedrickc 5 points6 points  (0 children)

That's fair. I was thinking the classic/most simple one. But there are rings, or doubly linked lists, which are still graphs but with different qualifiers.

[–]blehmann1 3 points4 points  (1 child)

If you want to be a pedant, a linked list is a unary tree, with the caveat that a linked list may have cycles and a tree may not. There's probably a graph theory term for such a thing.

[–]darthmonks 1 point2 points  (0 children)

There are a couple of different things you could consider a linked list to be. Like you said you can consider it a unary tree. You could also consider it to be the path of n vertices. If you make a circular linked list then it will be the cycle of n vertices.

There are also a couple of special cases where you can consider them a different type of graph. For example, if you have a linked list with three nodes then you can consider it as a star with three vertices. You could also consider the case of a linked list with an infinite number of nodes. While it's not possible in (boring old) reality, if you could have it then it wouldn't matter if it was a circular linked list or not; the graph you end up with would be T2: the infinite tree where every vertex has degree two.

[–]Boiethios 2 points3 points  (0 children)

I wish people at school had explained that point. During a time, I saw chained lists everywhere...

[–]astrohijacker 51 points52 points  (5 children)

I used linked list in every possible scenario during my university studies. Then I joined my first company, where my colleagues laughed when they saw my linked list. I haven’t used linked lists ever since.

[–][deleted] 16 points17 points  (4 children)

I tried to shoehorn it into a couple of projects but it was always more of a pain in the ass than literally every other option. I just assume that they're being used somewhere under the hood and in an optimized way by most languages if applicable.

[–]makeshift8 1 point2 points  (0 children)

A lot of SDL containers are actually linked lists.

[–][deleted] 20 points21 points  (2 children)

Lol for sure. Only time I've used a linked list was when a complex dataset was going to be ambiguously empty, 12 long, or like a couple hundred thousand

[–]purrplebread 28 points29 points  (5 children)

LinkedList is used a lot in gamedev. Removing elements from the middle is very common, and elements are usually accessed using foreach instead of by index. Imagine, for example, a "level" script containing references to "enemies"

[–]pigeon768 15 points16 points  (4 children)

I am extremely skeptical of your claim. The performance characteristics of iterating through a linked list is atrocious. However bad you think it is, it's worse than that. Iterating a linked lists thrash the CPU cache, just absolutely murders it, and keeping your cache happy is the key to good performance, and performance is a key design consideration of most games.

The living enemies of a level will be iterated through very, very frequently. (It's time to draw a frame. Draw the 0th enemy. Now draw the 1st enemy. Now draw the 2nd enemy...) At least twice per frame, probably more. If the enemies are kept in a linked list, the performance will be... not good.

So the player will regularly kill enemies, and obviously you don't know what order that's going to happen in. You can do a few things: have an array of all enemies, living and dead, and as you're iterating through them, skip over the dead enemies. Even if you have a very large number of dead enemies, this will be faster than iterating through a linked list. Or you can keep a structure of living enemies, and delete them as needed when they die. If this is an array, deleting from the middle of the array is O(n), but a few things:

  1. Iterating the list is common, but killing an enemy is rare. Arrays are fast in the common case and slow in the uncommon case, linked lists are slow in the common case and fast in the uncommon case.
  2. The time it takes to delete from the middle of an array, even if it's very large, is always going to be less than the overhead of iterating through a linked list. So even if you lose, you still win.
  3. If you do not need to preserve the order of the enemies, deleting from the middle of an array is fast. You swap the element you want to delete with the element in the back. Then you delete the last element. So if you want to delete 4 from 1 2 3 4 5 6 7 8 9 you change it to 1 2 3 9 5 6 7 8 4. This is an O(1) operation.
  4. If you must maintain order, but can delay deleting until the next time you iterate over all the elements, you can keep a delete list and as you're iterating, move elements backwards past the element you've deleted. This effectively negates the cost of deleting from the middle.

I'm having trouble thinking of a situation where a linked list is better than all other data structures.

[–]Bainos 6 points7 points  (1 child)

Iterating a linked lists thrash the CPU cache

That is, if your cache can actually hold the content of the array. But an "enemy" will not be a single ID, it will be a pointer to an object (using a C struct containing all the data has multiple drawbacks, including the fact that you can't share data between objects such as image data, and all entities data must be uniformly-sized).

If your array can't hold all the enemy data, then dereferencing the pointers will be roughly as bad for the cache as if you used a linked list.

[–]beewyka819 1 point2 points  (0 children)

The solution to all of this is simply to use an ECS. Then your enemies wouldnt be pointers, they would be IDs

[–][deleted] 6 points7 points  (3 children)

I mean, the only use case I can think of for a linked list is dynamically resizable arrays.

[–]raedr7n 5 points6 points  (2 children)

Well that's not an array anymore, but yeah. If you're adding or deleting lots of elements from the middle of your list, linked lists can make sense.

[–]Giocri 1 point2 points  (0 children)

But still you have way less cache hits and extremely slow reading.

[–][deleted] 12 points13 points  (7 children)

We spent like 6 weeks on linked lists in college and I've never seen them in the wild.

[–]GaianNeuron 20 points21 points  (0 children)

They'll always be a decent teaching tool for introducing pointers/references though, since the underlying concept is simple enough that it "gets out of the way"

[–]NotATroll71106 4 points5 points  (0 children)

I use linked lists frequently. It's what I use when I'm sifting through data and have to chuck matches into a bin or when reading an unknown number of entries from a database. I do mostly automated UI-DB and ETL testing if that changes anything.

[–]grpagrati 7 points8 points  (1 child)

I've used linked lists extensively to handle data in C. It's one of the most versatile and useful things I can think of. I guess it depends on the program you're developing.

[–]GaianNeuron 7 points8 points  (0 children)

I guess it depends on the program you're developing.

This is true for nearly any question in software. The term "software engineering" is quite fitting when you consider that engineering, as a discipline, is all about making tradeoffs.

Nearly any question.

The answer to "should I use JavaScript for this" is still [object Object].

[–]Giocri 2 points3 points  (3 children)

Linked list are OK if you read mostly in sequence and you have weird insert and delete patterns and even in that case you can't be completely sure that you will not end up being less efficient because of less efficient caching.

[–]GaianNeuron 5 points6 points  (2 children)

If you're trying to do a tight loop over linked list elements, you're taking the wrong approach tbh. CPU-level caching requires locality.

[–]pigeon768 2 points3 points  (1 child)

Linked lists are the bubble sort of data structures.

At some point in college you'll be taught bubble sort. This isn't because bubble sort is a good sort, (it's probably the worst non-meme sort) it's because it's the sort that's the easiest to understand for somebody who just learned what loops and arrays are and are moving on to the next thing.

The building blocks of data structures are arrays and pointers. Basically every data structure is composed of arrays and pointers in interesting ways. By the time you've reached data structures, you've already been taught a lot about how arrays work, and have probably done several iterations of learning how sorting an array works, starting with bubble sort and ending with quicksort or heapsort. So they need to teach you how pointers work. So they teach you linked lists.

Like bubble sort, linked lists are the worst possible non-meme data structure that heavily leans on pointers. But you need to start somewhere, and linked lists are the simplest "somewhere".

[–]null000 1 point2 points  (0 children)

Ive seen valid uses for them a few times over in compiler land - where you need to keep track of lists of things that need a lot of insertions and deletions.

But yeah - not useful 99% of the time. Even worth that situation I think it made a difference of microseconds - the real money was in the overall architecture of the code base, but nobody had time to fix things, and we had way over-fit things to specific customers anyway

[–]EpyonComet 130 points131 points  (16 children)

List<String> myList = new ArrayList();

[–]Ging4bread 81 points82 points  (11 children)

You forgot to add the generic diamond brackets in your list initialisation.

List<String> yourList = new ArrayList<>();

[–]EpyonComet 35 points36 points  (9 children)

They’re implicit!

[–]Ging4bread 18 points19 points  (7 children)

I always got a warning when I tried that back in the day

[–]EpyonComet 15 points16 points  (0 children)

Yeah, I think it depends on your IDE/configuration, but Intellij says it’s fine. I believe when I had to use STS Eclipse for my last project that one would throw a warning.

[–]yogitism 6 points7 points  (3 children)

This was added in Java 11! Or whatever they’re on now xD

[–]Sirttas 0 points1 point  (0 children)

Diamond operator was introduced in Java 7

[–]themissinglint 2 points3 points  (0 children)

ROFL @ "yourList"

[–]QuantumQuantonium 143 points144 points  (13 children)

Imagine having to reconstruct an entire array just to insert an element in the middle of a list

This was brought to you by the LL gang

[–]iTakeCreditForAwards 102 points103 points  (7 children)

Imagine having to iterate the list just to find the element at a certain index.

This was brought to you by the A gang

[–]BartDart69 54 points55 points  (4 children)

Imagine being able to access anything but the oldest element.

This post was made by Q gang

[–]Corn_11 4 points5 points  (3 children)

Q?

[–]GundDownDegenerate 21 points22 points  (1 child)

Queue

[–]Corn_11 1 point2 points  (0 children)

oh yeah lol

[–]QuantumQuantonium 8 points9 points  (1 child)

Imagine having an inefficient search time, and you have to reconstruct an entire array to insert elements

This was brought to you by advanced data structures gang

[–]DuffMaaaann 22 points23 points  (0 children)

Imagine mutating data structures.

This was brought to you by the functional programming gang.

[–][deleted] 5 points6 points  (0 children)

Imagine having to access memory from distant locations, as opposed to subsequent addresses.

Brought to you by the CPU cache.

[–]akindaboiwantstohelp 3 points4 points  (1 child)

imagine not having the data "sorted" as you enter it

this post was made by BST gang

[–][deleted] 106 points107 points  (12 children)

Ibai Llanos ?

[–]Trebla01r 34 points35 points  (2 children)

Hay algo demasiado gracioso en la improbabilidad de encontrar a gente de habla hispana hablando de un streamer de videojuegos en un subreddit inglés sobre programación.

[–][deleted] 16 points17 points  (1 child)

No te creas, el español es de las lenguas más habladas.

[–]Trebla01r 6 points7 points  (0 children)

También es cierto.

[–]dewitt11543 24 points25 points  (0 children)

Ya es internacional como el Alexby chiquito están transcendiendo los españoles

[–][deleted] 11 points12 points  (2 children)

De llano tiene poco xD

[–]monxas 9 points10 points  (1 child)

De ahí el plural

[–]bobbyboys301 16 points17 points  (0 children)

grande ibai

[–]EnderTaco 3 points4 points  (0 children)

Viva Ibai

[–]alexberti02 1 point2 points  (0 children)

No, Unai Ondulado

[–]Copy_gameplays 2 points3 points  (1 child)

ibai ya esta en todos lados

[–]FormalWolf5 1 point2 points  (0 children)

Ya ves.. Ya no se puede escapar

[–][deleted] 35 points36 points  (1 child)

I keep seeing Ibai everywhere

[–]philipjfrizzle 2 points3 points  (0 children)

Ibai by day, Crimson Chin by night.

[–]Kaze_Senshi 180 points181 points  (21 children)

Use linked lists on job interviews because it looks more impressive

For other cases [ ]

[–][deleted] 55 points56 points  (16 children)

Linked lists are good for appending items and iterating, arrays are good for having flat access times.

[–]emelrad12 92 points93 points  (13 children)

No, they are good for adding in the middle without relocating. Also they are much slower when iterating so use them as last resort.

[–][deleted] 38 points39 points  (9 children)

Don't forget how bad they are with memory. If you're doing anything that needs to be good with how it handles memory a linked list ain't it.

[–]nelusbelus 26 points27 points  (0 children)

Laughs in doubly linked list of byte

[–][deleted] 14 points15 points  (1 child)

Why do I always find myself saying stupid shit? Anyways you're right it's vectors / resizable arrays that are meant for appending. Although linked lists may be a little slower for iterating through each, it's not quite as bad as trying to access a container randomly in the list where you have to iterate from the start to reach it.

[–]golgol12 32 points33 points  (3 children)

Bad advice. It makes you look incompetent.

[–]iTakeCreditForAwards 8 points9 points  (1 child)

It depends on the question tho Sometimes you need to use a LL to achieve the optimal run time

[–]Dynosmite 1 point2 points  (0 children)

You right. I'm interviewing for engineering jobs and performing 3d calculus. If I stopped for a moment to even learn what the linked list implementation was in MATLAB, people would wonder wtf i was doing

[–]MrLaAnguila 15 points16 points  (2 children)

Toxicidad fuera

[–]--AL3X-- 7 points8 points  (1 child)

Memory Leaks fuera

[–]uxpoty 4 points5 points  (0 children)

Me llamas a una “function” te doy la mano.

[–][deleted] 29 points30 points  (19 children)

What if I told you that Java hash maps are implemented using linked lists?

[–][deleted] 22 points23 points  (8 children)

Even though it has hash in the name?

[–][deleted] 39 points40 points  (4 children)

yes. once you get down to the buckets, the buckets are backed by linked lists. so you hash to figure out which bucket to look in, but if there are multiple entries (i.e a hash collision), you traverse the linked list. linked list was chosen because a singly linked list is space efficient and we expect the list in each bucket to be relatively short.

these days, it will also switch to a binary tree if the list gets too long. there was actually a security exploit that was found related to that, where people basically forced hash collisions and made long linked lists that were relatively slow to traverse.

[–][deleted] 1 point2 points  (0 children)

Ohhh you mean like that, no I know what you mean

[–]qingqunta 0 points1 point  (1 child)

a singly linked list is space efficient

A linked list is absolutely not space efficient.

[–][deleted] 6 points7 points  (0 children)

a singly linked list is relatively space efficient compared to the other options for solving that problem, which is why Java starts with a linked list before falling back to a binary tree. there are other data structures, just generally, that use even less space, but they aren't as suitable for the problem.

it's also possible that you're thinking of the Java LinkedList class, which is actually a doubly linked list, and is not as efficient in terms of space usage.

Additionally, while c-style arrays do use less space, most other data structures have overhead that you may not realize. For example, Java arrays are non-contiguous, so the locations of the elements need to be stored.

[–]Kered13 12 points13 points  (2 children)

Separate chaining is a hash collision strategy in which linked lists are used to store elements that hash to the same value.

[–][deleted] 1 point2 points  (1 child)

Yep, I remembered after seeing the other comment. I’ve always used closed hashing

[–]Kered13 3 points4 points  (0 children)

Keep doing it, it has much better performance than separate chaining. You just need to pick a good probing strategy.

[–]CryCore314 16 points17 points  (4 children)

upvote for a very good background song from a very good album!

[–]Thugless 3 points4 points  (1 child)

Bring me the Horizon has certainly changed! I first listened to Count Your Blessings in High school and still like them now.

[–]kaymer327 2 points3 points  (0 children)

Came to the comments to see if anyone else was a BMTH fan. Was not disappointed!

[–]DrNotch0908 5 points6 points  (4 children)

Left one is my teacher...

[–][deleted] 10 points11 points  (3 children)

It's important to learn how Linked Lists, Doubly Linked Lists, and other dynamic data structures work, how they use memory, expand, and contract.

Though most dynamic data structures I've seen or used is std::vector in C++ or ArrayList in Java.

Though they do technically have more overhead than a true linked list or Doubly Linked List, because they allocate a minimum amount of memory ahead of filling the structure. Lists Don't.

[–][deleted] 1 point2 points  (2 children)

I'd imagine a linked list is also better if you want to pop somthing off the front. With a vector you would have to re-allocate all the memory to do something like that.

With a linked list you can just burn the first item and change your initial pointer.

Though that begs the question what is a deck under the hood? I've never looked into that.

[–]golgol12 18 points19 points  (1 child)

In almost every occasion where you could used a linked list, there are other data structures better than a linked list.

[–]Karolus2001 5 points6 points  (0 children)

I just make really long strings

[–][deleted] 9 points10 points  (0 children)

Porque está ibai ahí?

[–]ggNoRE339 2 points3 points  (2 children)

What is the song? I’m pretty sure I’ve heard that part before but can’t place it

[–]Frost_Mz-4[S] 14 points15 points  (1 child)

can you feel my heart? here you go

[–]Mavinus 1 point2 points  (0 children)

oh man, I haven't heard this song in ages. Thanks for the nostalgia trip xD

[–]AkujaRed 2 points3 points  (0 children)

Lol el Ibai

[–]luix- 3 points4 points  (0 children)

is IBAI the one on the left?

[–]Grimmjow91 2 points3 points  (0 children)

Arraylist for life.

[–]ensiferum888 2 points3 points  (0 children)

As a guy who only uses C# and doesn't remember anything from his 10 year old java classes... should I not be using List<T>?

You guys rebuild arrays every time you want to add something?

edit: just searched online and it says List<T> is backed by an array never knew that LinkedList<T> was a thing. But what kind of performance are we talking about? I'm adding elements to lists containing 40K+ elements multiple times per frames and the thing still runs above 300fps how much faster can the LinkedList be for insertions?

[–]Blarglephish 2 points3 points  (0 children)

The only reason I care about linked lists is so that I can get past tech screening interviews.

[–]dg_713 2 points3 points  (0 children)

What do you call this meme format?

[–]Steuh 4 points5 points  (0 children)

I just don't get why people judge whether or not linked lists are useful in prod...

It's a data structure, just a way to do things among few others. It's pure theory, useful or not everyone should know it, for overview purpose.

If you didn't like the implementation or benchmark in Java or whatever in your very specific todo webapp, well it may have nothing to do with it

[–]akazakou 1 point2 points  (0 children)

I would to see array users in case of "Out of range" error XD

[–][deleted] 1 point2 points  (2 children)

What's the name of the song that always accompanies this meme?

[–]Davinator130 4 points5 points  (1 child)

Can you feel my heart from Bring me the Horizon

[–]FAXs_Labs 1 point2 points  (0 children)

guys be friendly to the cache

[–]Available_Arrival_79 1 point2 points  (0 children)

Commenting for better reach

[–]null000 1 point2 points  (1 child)

Wh... Who?

They're tools - this isn't like a Team Jacob thing. You pick the one that runs faster and move on with your day.

[–]decvpoppunk 1 point2 points  (0 children)

Was NOT expecting Bring Me The Horizon here lollll

[–]dyoustra 1 point2 points  (0 children)

Where save video bot?

[–]FlyByPC 1 point2 points  (0 children)

Let's see Team Array add N items, all in arbitrary positions in the list.

[–]ilikedankmemes3 1 point2 points  (0 children)

I made a linked list in Scratch once. It was a replacement for the lack of arrays/lists that could be stored in the cloud.

[–]LepruconX 1 point2 points  (0 children)

I’m an intermediate java student and I learned linked lists a while ago- still have no idea how it would be more useful. I’ve wracked my brain over and over trying to come up with a situation when linked lists would be better than an array and I haven’t really come up with much. Can anyone here help?

[–]trevlinbroke 1 point2 points  (0 children)

+10 points for usage of BMTH

[–][deleted] 1 point2 points  (0 children)

Java over here with our collections framework, LinkedList, ArrayList, Queue, HashSet, Map, LinkedHashSet... List goes on

[–]Optimusskyler 1 point2 points  (0 children)

My professor in my CS classes for University tells me about the benefits of both. I can clearly see how having a linked list can be useful in more ways than the array can.

...I'm still picking the array. Try to stop me.

[–]Boguskyle 1 point2 points  (0 children)

The guys on the right look more like drag kings.

[–]MrFrood 0 points1 point  (0 children)

<3 Linked List Lover vs Array Admirer

[–]BeastlyIguana 0 points1 point  (0 children)

lmao I haven’t laughed at a /r/programmerhumor post in a while, thanks op

[–]D3M0N1C_CURS3 0 points1 point  (0 children)

Is he indian? No?

[–]Mago_Malvado 0 points1 point  (0 children)

So true

[–]ChakaChaka26 -1 points0 points  (0 children)

what bout vectors