Why are linked lists so perfect bros?

This is why nothing runs well anymore. Even phones with as much ram as my laptop and twice the cores are slower than necessary because of fucks like you

Arraylist?

They're not, they don't make use memory locality.
They're simple to implement and that's about it.

They are shit. Arrays still superior

Why would anyone use a linked list over an array realistically? Is it some kind of memory limitation thing? The only time I've used them is when I use some lisp language

You'll shit your balls when you learn about jump lists.

Arrays have O(1) access and linked lists have O(n) access, but arrays have O(n) insertion/deletion and linked lists have O(1) insertion/deletion

iterable and collection are interfaces, so they just ensure you can use all classes that implement those interfaces the same way.
for example, you can use the foreach shorthand on iterables:
ArrayList list = ...;
for (String s : list)
{
// do something
}

there are also significant differences between arrays, lists, sets and maps.
an array has a fixed size, the others don't.
a set can only store unique values, while a list can contain as many duplicates as you like.
a map maps keys to values, so keys have to be unique.

well i fucked up the closing tag, but you get the idea

Finding the point to insert is still O(n) on a linked list so they frequently don't come out ahead in real usage

So linked lists are just good for adding stuff to the front of it pretty much

Uh, no. Ban related.

You can easily have a tail pointer.

Or back.

once you go map you don't go bap

Linked lists are usually better if you need to frequently insert/delete elements in the middle of the list.

Maps have horrible performance if the input is already sorted.

Wouldnt that make it O(n) though because you have to keep recursing on it

It's so confusing.
I always thought that main difference lies in memory management.
You can navigate array-like structure by adding two numbers, which is blazingly fast. But if you need to add the new element or delete the old one you need to reallocate the memory, which is slow.
If we use linked list we can add a new element by allocating memory for this element and switching prev and next pointer values, which is fast.
A similar process can be used to delete the element, but with a twist: you need to find this element first. And searching through linked list is extremely slow: in the worst case you need to go through the whole list.

A reminder that insertion in a linked list is ALWAYS O(1).

Cred Forums can't seem to grasp this simple concept.

a better question is why is forth so perfect

It has nothing to do with that. The main difference is the cache performance.

>searching through linked list is slow
No just make your linked list nodes be the size of a cacheline, and there's no problem.

we call them blockchains now

get up to date with the web scale terminology

No. Just no.

Lisp weenies I can understand. At least the language lets you make abstractions, even though the ecosystem is dead. But forth? You can't make any abstractions since it's baiscally asm. But It's like assembly language for an imaginary stack machine, so it's not even efficient.

Man, I can't see even 1 good reason to use forth to program anything.

LOL fukkin nerds
Who gives a shitt what nerdstructure u use
Just use an array for everything lol

1 : []

>cache performance
Excuse me, but literally what?
We have the free chain. You can either allocate the big chunk of memory that will contain all of your elements or you can allocate memory bit by bit.
In the second case, you cannot predict where your elements will be contained without some sort of external system, no?

you can make an contiguous arena and allocate your nodes out of that.

you can also pack multiple nodes into each allocation so that the allocation fills the cacheline.

see caches work by fetching lines from memory at a time and storing them on the cpu cache. a cache line is like 64 bytes. so the smallest memory access you can do is 64 bytes not one byte. whenver you think you're reading 1 byte the cpu could be reading 64 bytes from memory if the line that byte is in is not in the cache.

so arrays are contiguous, so when you read the 64bytes you read in adjacent elements of the array. For ex 32-bit ints, you can fit 16 of them in 1 cache line. So you'd only need to actually hit memory 1 time to read 16 elements of the array.

But linked list elements aren't stored in order. So every element you traverse, you're basically getting a cache miss, and you have to read 64 bytes from memory.

But if you do like I said, you can align the linked list nodes to fill the cache line. So then when you read 1 cacheline you can read multiple linked list nodes at once, giving you the cache advantage that arrays have.

And yes you can predict where the elements are stored.

1 way:

instead of doing

struct node {struct node *next; int val; }

you can do
struct node {struct node *next; int val[4]; }

and store multiple node's payloads in a single "node" struct.

or like I said use an arena, basically writing your own version of malloc to make sure the linked list nodes are contiguous in memory.

My comment was based on the assumption that JavaScript Arrays are similarly implemented as C++ vectors (arrays in C++ are fixed-sized).

In a typical linked list, in order to insert an element in "position" you traverse the list to the "position", create a new element, and modify two pointers.

In a vector, you have to reallocate every single element after "position" to their new locations, and then insert the new element.

So both in theory take O(n) time, but the vector operation involves writing/deleting "n" elements (in the worst case reallocating the entire vector), whereas the linked list operation is just traversing "n" elements which is usually faster.

Why would you do this instead of just using a vector?

I'm sure you can do insertion in an array in amortized O(1) if you let everything else go to shit.

Dude cache locality lmao

>you can make an contiguous arena and allocate your nodes out of that.
>or like I said use an arena, basically writing your own version of malloc to make sure the linked list nodes are contiguous in memory.
I'll be the first person to admit that my knowledge about this subject a bit shaky, but it looks an awful lot like some kind of clever array implementation, like STL Vector.
It will work if you can accurately predict maximum amount of memory you will ever need. If suddenly you need to store more than you initially predicted, it will be "we need to add one more element to the array" all over again, no?

There is no real world use case where linked lists are superior to array lists.

>jumping all over memory so the cpu can't predict anything
wew, I bet you use java too

Contiguous dynamic arrays are GOAT

>There is no real world use case where linked lists are superior to array lists.

I am willing to bet, that besides knowing about programming, you also know nothing about the UNIX filesystem.

A b-tree is a multiple linked list.

I bet your a volafaggot

en.wikipedia.org/wiki/Unix_File_System

>your
you're