So is the linked list obsolete now that we have ArrayList?

So is the linked list obsolete now that we have ArrayList?

Other urls found in this thread:

lxr.free-electrons.com/ident?i=list_head
lxr.free-electrons.com/source/include/linux/sched.h#L1389
stackoverflow.com/questions/12359228/reliable-information-about-x86-string-instruction-performance
youtube.com/watch?v=1oHEYk6xuvQ
twitter.com/SFWRedditImages

/thread

Not enjoying given List functions in one, and the speed and less hardware usage of the other while searching.

Not sure if serious or troll

He has a point though

>Is the fork obsolete not that we have pitchforks?

>I never learned amortized analysis or about caches

That is surely bs(*). A list has constant insertion - it's two pointer assignments. A vector requires elements to be shifted.

* unless it's an insert using a linear search

Of course it uses linear search

Dynamic arrays have amortized O(1) inserts when you insert at the end, much like linked lists

I'm a genius
f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
Bash sleep.sh 1 5 3 7 6
Order n

It explicitly says that it's using linear search. I don't understand how vector can be so fast though.

Linked lists were a joke to begin with and have 0 real world usage. It's a terrible data structure that shits all over your cache, you couldn't come up with anything worse even of you tried.

Caching

they're not, it's just that LLs are as slow as it gets

Vectors/arrays are usually implemented as a section of contiguous memory. You just increment the index to reach the next element. Linked lists contain a pointer to the next element in the list, which may not necessarily be the next contiguous memory section.

Why does the Linux kernel use linked lists then smartypants?

i post old meyms and say their my own xD

>sleep.sh 10000000001 10000000000
nice runtime of 300 years

Tell that to the folks at Autodesk.

It doesn't. Show me even one source file of kernel code with linked lists.

it uses intrusive lls dickface

nice example of pajeet-powered crapware

If all elements you have are numbers.

The plot is not search, it's search+insert. Is shifting a million of elements really that that fast?

No idea, it does seem kinda funny, but maybe I'm just dumb.

include/linux/list.h

>tfw have a project due 31 may
>have to use linked lists
>have no fucking idea where to start
I think I don't like programming...

wtf are you retarded?

not it's slow as fuck, but compared to anything with linked lists it's as good as instantaneous

To think of it, there's a movsw instruction. A million elements shift really should be less than a second on modern hardware.

In which language?

are you?
lxr.free-electrons.com/ident?i=list_head

C
We're supposed to do a travel agency of some sort. Like buy ticket, cancel trip, put in wait list, etc...

The list of processes

lxr.free-electrons.com/source/include/linux/sched.h#L1389

Don't underestimate the effects of caching and how our memory systems are optimized for block transfers.

Isn't implementing a linked list a pain in the ass in C? Good luck. Just use Stack Exchange like everyone else in your class probably will.

Apparently, Sandy bridge can move tens of gigabytes per second using the right instructions.
stackoverflow.com/questions/12359228/reliable-information-about-x86-string-instruction-performance

No, it's very easy, which is why linked lists are so commonly used in C.

Easy to implement, performance isn't always top priority.

It very much is in linux though.

>performance isn't everything
it kinda is in a kernel, especially in the scheduler

Wrong

No

Written by the same person.

typedef struct{
int ticket_number;
char* flight_name;
ticket* next_ticket;
}ticket;

void run_list( ticket* head ){
if( ticket->next_ticket )
run_list( &(ticket->next_ticket) );
else
printf( "%s", (*head)->ticket_name);


i think that's a basic linked list structure and how to go through it, my pointers arithmetic is a bit rusty but you get the main idea.
you can differentiate from other programmers by getting shit done instead of complaining, if you don't know it research it.

ITT: aspies who watched "Sasesh Venugopal Patel Explains Data Structures" on youtube and now have valid opinions

To answer No, they are not obsolete

sorry, as i was saying i'm a bit rusty in C but just a little while programming will get me going. (lazy to make an insertion method)

#include
#include

struct ticket{
int ticket_number;
char* flight_name;
struct ticket* next_ticket;
};

void run_list( struct ticket* head ){
if( head->next_ticket )
run_list( head->next_ticket );
printf( "%s\n", head->flight_name );
}

int main( void ) {
struct ticket* test = malloc( sizeof( struct ticket ) );
test->flight_name = "hello world";
test->ticket_number = 10;
test->next_ticket = malloc( sizeof(struct ticket) );
test->next_ticket->flight_name = "hello world 2";
test->next_ticket->ticket_number = 20;
test->next_ticket->next_ticket = NULL;
run_list( test );
}

I never learned amortized analysis but I know what a cache is. Sort of.

Teach me, senpai? :3

>you can differentiate from other programmers by getting shit done instead of complaining
I like the cut of your jib

Unfortunately, getting shit done by yourself seems counterproductive towards making it in the real world...

You don't know what linked lists are for OP

what i meant is, oh i don't know how to implement lists.
>programmer A: WAAAAAAAAAAAH I FUCKING CANT IS TOO HARD
>programmer B:i'll look it up in this reference manual and then implement it.

that's kind of what i meant

No.
1. Linked Lists guarantee order
2. Traversing a Linked List is much faster than an array list

Each data structure has a purpose and an intended use.

>2. Traversing a Linked List is much faster than an array list

what? Array lists / vectors are contiguous in memory and will traverse much quicker. Think about the cache

no return

>implying they're for anything

They aren't "for" anything. They are inferior to array backed lists in every single measure.

#REKT

Compact data are easier to read from ram due to brust mode and the higher cost to resize an ArrayList (which require to copy the whole data) become irrelevant in a long run.

>1. Linked Lists guarantee order
no

>2. Traversing a Linked List is much faster than an array list
no

insert an element into the front of a linked list. Now do that on an array list.

Exceed the capacity of an array list. Now do the same with a linked list... oh wait

Wtf is this "linked list is bad" meme? They have particular use cases. Linked lists are only as shit as your programming skill and ability to use them correctly.

If you do more inserts/moves/deletes than reads, linkedlist is better.

hush now. let the morons strawman in peace so they can quicker return to their undergrad studies.

You insert stuff at the end of the arraylist, not at the start

Amortized complexity (this includes exceeding the allocated size) is O(1) and the constant factors are significantly lower because linked lists are shit at cache behavior

Don't worry, you will learn this in CS102

>insert an element into the front of a linked list. Now do that on an array list.
Insert an element into the back of a linked list. Now do that on an array list.

>Exceed the capacity of an array list. Now do the same with a linked list... oh wait
Allocating memory is sublinear, O(1) in most scenarios.

>Allocating memory is sublinear, O(1) in most scenarios.
with a fucking huge constant factor.

you are missing the point, he's saying linked list have are useful. sometimes it's better use array list, other time no. you shouldn't use array list regardless, you should look at what you need.

There is literally no performance benchmark where a linked list is superior than a properly coded array backed list. The only advantage a linked list has is the simplicity in coding.

A good potential use case for a linked list would be if you needed a data structure to function like a stack but in extremely rare circumstances you might need arbitrary access.

the constant factors are significantly lower because linked lists are shit at cache behavior

Only true if you aren't storing referential data.

Also, do not make the mistake of considering amortized and per operation complexity as equivalent. They absolutely are not, and it's something to consider if consistency is important.

A linked list can be a graph, an array list cannot.

linked list is good for infinity datasets

youtube.com/watch?v=1oHEYk6xuvQ

Most people here should watch this video. It does a pretty good explanation. of why even though "vectors" should be slow on inserts vs a LL they arent because of how L1/L2 Cache works on any modern CPU

>2016
>writing software in C++