So is the linked list obsolete now that we have ArrayList?
>>54528157
/thread
>>54528157
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
>>54528157
He has a point though
>>54528157
>Is the fork obsolete not that we have pitchforks?
>>54528337
>I never learned amortized analysis or about caches
>>54528430
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
>>54528645
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 geniusf() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
Bash sleep.sh 1 5 3 7 6
Order n
>>54528645
It explicitly says that it's using linear search. I don't understand how vector can be so fast though.
>>54528157
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.
>>54528745
Caching
>>54528745
they're not, it's just that LLs are as slow as it gets
>>54528745
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.
>>54528766
Why does the Linux kernel use linked lists then smartypants?
>>54528719
i post old meyms and say their my own xD
>>54528719
>sleep.sh 10000000001 10000000000
nice runtime of 300 years
>>54528766
Tell that to the folks at Autodesk.
>>54528838
It doesn't. Show me even one source file of kernel code with linked lists.
>>54528838
it uses intrusive lls dickface
>>54528877
nice example of pajeet-powered crapware
>>54528157
If all elements you have are numbers.
>>54528814
The plot is not search, it's search+insert. Is shifting a million of elements really that that fast?
>>54529077
No idea, it does seem kinda funny, but maybe I'm just dumb.
>>54528890
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...
>>54529126
wtf are you retarded?
>>54529077
not it's slow as fuck, but compared to anything with linked lists it's as good as instantaneous
>>54529077
To think of it, there's a movsw instruction. A million elements shift really should be less than a second on modern hardware.
>>54529150
In which language?
>>54529175
are you?
http://lxr.free-electrons.com/ident?i=list_head
>>54529217
C
We're supposed to do a travel agency of some sort. Like buy ticket, cancel trip, put in wait list, etc...
>>54528890
The list of processes
http://lxr.free-electrons.com/source/include/linux/sched.h#L1389
>>54529077
Don't underestimate the effects of caching and how our memory systems are optimized for block transfers.
>>54529274
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.
>>54529077
Apparently, Sandy bridge can move tens of gigabytes per second using the right instructions.
http://stackoverflow.com/questions/12359228/reliable-information-about-x86-string-instruction-performance
>>54529365
No, it's very easy, which is why linked lists are so commonly used in C.
>>54528838
Easy to implement, performance isn't always top priority.
>>54529417
It very much is in linux though.
>>54529417
>performance isn't everything
it kinda is in a kernel, especially in the scheduler
>>54529512
Wrong
>>54528719
>>54528855
Written by the same person.
>>54529409typedef 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 >>54528157
No, they are not obsolete
>>54529274
>>54529365
>>54529409
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 <stdio.h>
#include <stdlib.h>
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 );
}
>>54528453
I never learned amortized analysis but I know what a cache is. Sort of.
Teach me, senpai? :3
>>54530530
>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
>>54530964
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.
>>54531724
>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
>>54530474
no return
>>54531532
>implying they're for anything
>>54531532
They aren't "for" anything. They are inferior to array backed lists in every single measure.
>>54529309
>>54528890
#REKT
>>54530920
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.
>>54531724
>1. Linked Lists guarantee order
no
>2. Traversing a Linked List is much faster than an array list
no
>>54532066
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.
>>54533374
hush now. let the morons strawman in peace so they can quicker return to their undergrad studies.
>>54533374
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
>>54533374
>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.
>>54535313
>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.
>>54536221
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.
>>54535261
the constant factors are significantly lower because linked lists are shit at cache behavior
Only true if you aren't storing referential data.
>>54535261
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
https://www.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
>>54538010
>2016
>writing software in C++
