First I have t warn you - I am indeed a retard...

First I have t warn you - I am indeed a retard, what's the difference between a linked list and an array and what are some real life cases where the latter couldn't be used instead of the first?

Attached: 1537552288596.png (1161x881, 1.04M)

Google it son.

I can't give you an example because I too am a retard but perhaps a higher-leveled one.
A linked list is a List with two nodes: the data, and a reference to the next data. You begin with the "head" which has no reference to other nodes. The next node references the "head." In fact, every node only sees the node in front of it - they're all the "head."
An array is a collection that stores data linearly. You can store arrays within arrays, pretty neat.

The best use of a linked list is not using it.

An array is contiguous in memory whole each node in a linked list can be anywhere in memory. To get the next element of an array you just increment the memory address by the size of the element, to get the next element of a linked list you must follow a pointer in the node of the current element.
Arrays are better for almost all cases but linked lists may be an improvement if you need to insert/delete elements in the middle of the list (because you don't need to move all the later elements around).

If you are creating a temporary collection then arrays are better
If you have a persistent collection where objects are usually iterated over but rarely inserted or deleted, a linked list is better

>what are some real life cases where the latter couldn't be used instead of the first?
None.

To insert an element in the middle of an array you have to resize the array, shift all the existing elements and only then you can insert your value. In linked list you change the values of two pointers and you're done. That's the use case.

If you dont care about order then you can insert and delete in the middle of an array by swapping it out with the end value

Completely the other way round.

Spatial partition where space is broken up into buckets and objects move around in space and are placed in the appropriate bucket
Linked list is faster and uses less memory for this application

All of these are great.
/g is once again the most intelligent board.

All depends on the use case obviously. If you only insert at the end you're still better off with an array. Another case is with the iterators, linked list iterators don't get invalidated after insertions/deletions.

How? Lists have more overhead involved in creating them but once they exist and their entries exist, insertion and deletion speed is faster and iteration speed is the same (assuming they're references to objects)

Performance behaviour of these is explained on Wikipedia, SO, CLRS (tge book) and the other suspects.

Obviously any application where the difference matters will be affected.

Iteration in linked lists is very slow because of low cache locality.

If you need your elements sorted use map. If you don't use hashmap. Other collections save some ultraspecialized ones like segment trees are obsolete.

I thought fast implementations of linked lists used arrays of nodes internally to preserve locality?

quick, somebody post the cartoon

The other post said:
>If you have a persistent collection where objects are *usually iterated over* *but rarely inserted or deleted*, a linked list is better
Iterating over an array is faster, inserting / deleting from a linked list is faster

As
said, the other way around makes more sense.

Linked list are only faster than arrays at insertion/deletion yet you suggest the usage that completely negates this advantage. Also "temporary" collections are frequently modified.

Depends
If you are storing actual data instead of pointers to data, then array is the obvious best choice
Most cases you are storing pointer to data, in which case if you store the link with the data you're pointing to, cache locality is the same
Generic lists tend to create their own link object though, in which case it is slower

We specifically talk about linked lists, what you have in mind is called an array-backed list.

That's right, they call those unrolled linked lists.

arrays are faster at insertion if you're building a collection from scratch. linked lists are only faster if the nodes/list already exist

That's a different data structure, although I'm not sure what that has to do with my example

>arrays are faster at insertion if you're building a collection from scratch
That's not insertion though.

Well I'm assuming that inserting onto the end of an array is still inserting, which is what you would be doing to build a typical temporary data structure

Back insertion is a corner case of insertion that just happens to be very easy to implement in arrays.

No, that is a problen with commonly used comp.sci / programming terminology. Insertion is different from appending.

it's the most common case

I'm working on blockchain and I can tell you a linked list is exactly what a blockchain is and the nodes that run the blockchain run on a set, which is just a linked list but with only unique values.

Prepending or appending is the fastest way to add elements into various implementations of data collections, so they're obviously used with these.

You can add to the beginning of a linked list by just making a new element and linking it to the beginning of the list, and then treating the new element as the beginning. And you can create a new element and link it to the middle of a list, giving you two lists with different heads but the exact same tail.
Linked lists can be circular if the last element in the list links to the first. Or it can link somewhere in the middle.
Linked lists can also be bidirectional. A typical use case is browser history, going back in history walks backwards in the list and going forward walks forward, as opposed to taking the current index and decreasing or increasing the index by 1. When you go back and take a different path, only one element needs to be linked, and no matter how much history you accumulate there's no need to reallocate an array.

Put into an analogy, a linked list is like a treasure map, and an array is like an elevator panel. If the jorney is more important than the destination, use a list.

A linked list is better when making a cache.