Linked lists on suicide watch
What's the point of this thread?
>>55047434
What's the point of "nvidia on suicide watch" threads?
>>55047571
>/g/ used to be so nice but it's full of shit nowadays
>guess I'll add some to the pile
You're doing God's work, Anon, truly.
>:^(
OK now show us element removal.
>i've never taken a data structures and algorithms course
lol
>strings are linked lists of 64-bit characters
JUST
>>55047770
>I don't know about caches
>I don't know about amortized analysis
yours sucked
>>55047774
>strings are linked lists
what shitty language are you using?
>>55048088
Befunge
>>55048088
Haskell
>>55048088
Erlang
>>55048088
All of them.
>>55047434
To show the effects of a naively implemented linked list vs a contiguous memory array on cache.
Make note of the naively part, add in a smarter memory allocator for the linked list and it would do much better, than what he lists
>>55049572
>To show the effects [in one specific benchmark, the details of which are not shown anywhere in the image]
Arrays are just implicitly linked lists.
>>55050949
That's a (((Lisp))) myth.
If arrays were linked lists, you would have to read the previous elements to find the next element.
Try doinga[a[a[a[a[a[i]]]]]]with linked lists.
>>55047417
I have seriously never needed to use a linked list. I don't understand the need to teach them.
>>55047774
You what, mate? Strings are arrays of characters.
>>55051552
I agree you don't need to use them anymore when most languages have ready support for sorted maps i.e. trees. But teaching trees would be hard without talking about pointers/references first, and linked lists are a really simple way to bridge the subject. How do you go about teaching more advanced structures? Jump straight in?
>>55051792
This. Also linked lists make skip lists easier to understand and people actually use those sometimes
>>55050949
arrays have O(1) lookup, linked lists have O(n) lookup
Arrays/Vectors have O(n) insertion, but Vectors have amortized insertion so the insertion time is actually O(1) at the cost of increasing space (which is still O(n))
LLs have O(1) insertion.
linked lists are good if you rarely traverse it but you just gotta add a shitload of insertions
>>55052424
Or if your elements are fucking huge, like the task struct in the linux kernel
>>55052424
A minor nitpick, you have O(n) insertion in a linked list in the worst case unless you have a pointer to where you want to insert, and you trash your cache while at it.
>>55051552
They're good for parser parts, like if you don't know if you'll need 2 or 2000 of something. Keeps memory from being wasted/needless reallocs
>>55052424
Linked lists are O(n) insertion faggot. How do you magically have a pointer to the place you want to insert into?
>>55054190
> How do you magically have the index of the location you want to insert to
Only count the insertion operation, not the lookup+insertion.
>>55054219
How do you insert without doing a lookup?
>>55054225
The point is, that if you are working on an element in the list, you can insert to it O(1), as opposed to O(n) with an array.
It's use case dependant.
>>55054241
You already spent O(n) time trying to find the element. There is no advantage over an array list.
>>55051552
You can Concat cons lists very fast in functional langauges
>>55054259
>if you are already working on an element
Say I'm scanning through the list, updating multiple elements as I go, which may require insertions before and after.
I don't need to do lookups for insertions because I'll already have the pointers/objects.
>>55054259
LL: You can always insert a node between two others with O(1) time, no questions about it. Choosing to insert between two elements is up to you though.
Array: Insert between two elements means having to move the elements to the right of it over. You may move 1 element over, or may move all N elements over to make room for the new element.
>>55052424
>LLs have O(1) insertion.
WRONG unless you're inserting at the front or the back
>>55054219
>Only count the insertion operation, not the lookup+insertion.
SHUT THE FUCK UP
YOU DONT KNOW WHAT YOU'RE TALKING ABOUT
IT'S O(n) YOU FUCKING IMBECILE
Best case is O(1) but average and worst is O(n)
>>55054276
>Say I'm scanning through the list, updating multiple elements as I go, which may require insertions before and after.
>I don't need to do lookups for insertions because I'll already have the pointers/objects.
OH MY FUCKING GOD
THAT OPERATION IS O(n)
YOU RETARDED FUCK AHHH
REEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
>>55054287
>THAT OPERATION IS O(n)
yes, and it's O(n^2) for an array.
>>55054287
>WRONG unless you're inserting at the front or the back
Still O(1) inserting at an index.
>>55054276
>Say I'm scanning through the list
Already O(n)
>>55054282
You already are at O(n) just to find the place where you what to insert.
>>55054287
>IT'S O(n) YOU FUCKING IMBECILE
It's O(1) if you already know where you are inserting. This is a fact. You can not dispute this.
Cases where you know where you are inserting are plenty - you have a pointer to an element of a list and want to insert another right after it. That's O(1).
No need to be upset. Sometimes you're just wrong.
>>55054297
>Still O(1) inserting at an index.
REEEEEEEEEEEE HOW FUCKING STUPID ARE YOU HOLY SHIT
>>55054294
>yes, and it's O(n^2) for an array.
No it's not. Random insert into a c style array is O(1), because you can memcpy the first portion of the array into a grown space, insert your element, and then copy the remaining portion.
>>55054316
It's correct you fucking doofus. If you're inserting at head, tail, or X it's always O(1)
>>55054294
No it's not you fucking idiot. You can insert multiple elements at once into an array list.
>>55054309
>you have a pointer to an element of a list
How the fuck did you get the pointer to the element?
>>55054309
>It's O(1) if you already know where you are inserting. This is a fact. You can not dispute this.
Yes I can, because you needed O(n) to get to "know where you are inserting".
I'm leaving out the fact that the way you're trying to explain linked list insertion proves to me that you have NO FUCKING CLUE about what you're doing, because there's no such thing as "knowing where to insert", because there is no RANDOM FUCKING ACCESS to a linked list.
There's no INDEX, you fucking asswipe.
There's only begin(), end(), and begin()+x.
There's no x.
>>55054332
>How the fuck did you get the pointer to the element?
I created that element myself long ago and stored the pointer in one of my other data structures.
>>55054336
>Yes I can, because you needed O(n) to get to "know where you are inserting".
No you didn't. Obviously you are not always searching through the list for a specific value to insert after.
>>55054331
>If you're inserting at head, tail,
Thanks for repeating what I said.
>or X it's always O(1)
WRONG.
I can't believe /g/ is too fucking imbecilic to understand even the simplest of complexity theory.
>HURR DURR THE POINTER UPDATE ITSELF IS CONSTANT TIME HURRRRR
>but finding the pointer was O(n)
>BUT ITS O(1) HUUUUUUUURRRRRRR
Kill yourself, you don't understand SHIT about computers.
>>55054357
>Obviously you are not always searching through the list for a specific value to insert after.
Yes you are, you fucking piece of shit. UNLESS you insert at the very front or very back.
That makes your average case O(n), as I've said countless times before.
Therefore you're fucking WRONG.
EVERY FUCKING TIME you want to insert anywhere other than front or back, YOU'RE LINEAR.
>ITT: People that have done first year algorithms and think they know their shit
>>55054370
I want to insert at position 12 in a list of 20 elements
There's no searching here, you fucking dipshit. It's list start address + 12 * element size
>>55054352
If you don't care about order than you can use a hash table.
>>55054352
>I created that element myself long ago and stored the pointer in one of my other data structures.
1. No longer a linked list
2. Maintaining pointers in a separate data structure pointing at linked list elements, how the FUCK do you now know which element in your separate data structure points where and represents what?
IT'S STILL LINEAR BECAUSE YOU HAVE TO SEARCH YOUR FUCKING SEPARATE DATA STRUCTURE NOW
HOLY SHIIIIIT
KYS
>>55054392
Holy shit you are retarded.
>>55054392
>I want to insert at position 12 in a list of 20 elements
>There's no searching here, you fucking dipshit.
AHAHAHAHAH
> It's list start address + 12 * element size
AHAHAHAHAHAHAHAHAHAHAHAHAHAH OH WOW
LET ME LAUGH EVEN HARDER
YOU WERE SERIOUS THE WHOLE TIME
HERE'S WHAT WILL HAPPEN:
SIGSEGV
SIGSEGV
SIGSEGV
EVERY
FUCKING
TIME
BECAUSE YOU HAVE DANGLING POINTERS IN YOUR LINKED LIST NOW
AHAHAHAHAHAHAH
OH WOW
>>55054400
Refute it if it's wrong shit for brains
You're in a corner here and can't get out
>>55054410
Rearranging pointers doesn't change the O notation
>>55054394
I do care about the order. Order is preserved in this case. Hash table is something else entirely- I have a list, not key-value mapping.
>>55054395
It is a 100% linked list. and I just store the pointer to linked list element. Is it so difficult to understand? Do you want me to write code for you?
>>55054429
How do you know that order is preserved? You're just inserting some shit after a random element without checking the rest of the list.
>>55054418
>Rearranging pointers doesn't change the O notation
HAHAHAHAHAHA
STOP
STOP
I CANT BREATHE
For one, a linked list is not contiguous in memory so you're overwriting heap randomly, congrats on your SIGSEGV.
For another, even if you were lucky enough to have it contiguous, what you've now done is created a dangling pointer inside of your linked list. Kill. Your. Self.
>>55054440
I am inserting very particular data at a specified position - after another very particular element. Order preserved and the element is placed exactly where I asked it to be placed.
>>55054452
>>Rearranging pointers doesn't change the O notation
This is true. Your entire argument falls apart now.
>>55054461
>have list of 1, 2, 3, 4
>keep pointer to 2
>want to insert 5 into list
>oh, good thing I have a pointer to 2 kept, I'll just insert after it because 5 goes after 2!
Nice going fucktard.
>Insert
>Link previous
>Link next
This doesn't change, regardless of where you're putting the item in the list.
Insertion is O(1), that is final and that is the word of accomplished computer scientists around the world. If you think otherwise, you are objectively wrong, and should consider a reeducation in computing.
>>55054429
>It is a 100% linked list. and I just store the pointer to linked list element. Is it so difficult to understand? Do you want me to write code for you?
You're so fucking stupid it's unbelievable. I can't even fathom how you think your "pointer data structure" is going to save you in any way here. You don't seem to understand how a linked list fucking works in the first place.
>>55054463
No it isn't. Apart from the fact that what you proposed is literally retarded and doesn't work, even if it did work, you'd need to jump to the previous element and update its pointer which you fucking can't without O(n) to find it.
Guys, why not post some code samples of what you're doing? I'm not for either side on this because there's been so much yelling I can't even figure out what you guys are arguing about now.
Actually, no, keep yelling. This is fun.
>>55054487
>even if it did work, you'd need to jump to the previous element and update its pointer which you fucking can't without O(n) to find it.
This is irrelevant. The insertion is O(1) but the searching is O(n)
>>55054477
It's the order I want. I have the option to insert with O(1) at a particular position - after an element I have the pointer to. Hence, I'm able to insert to linked list with O(1) if I already know where to insert.
>>55054496
>This is irrelevant.
No it isn't.
>The insertion is O(1)
No it isn't, insertion requires a search, insertion does not exist without a search.
>but the searching is O(n)
Lo and behold he got the hint.
>>55054503
Searching and inserting are two different operations. You don't combine them.
Just so we can close the case on this nonsense:
The search is O(n)
However the insertion after the search is O(1)
>>55054487
>You're so fucking stupid it's unbelievable. I can't even fathom how you think your "pointer data structure" is going to save you in any way here. You don't seem to understand how a linked list fucking works in the first place.
Pretty difficult to write a refutation when you have nothing but insults in your post. I'm still waiting for a counter-argument.
>>55054499
Then your order is fucking retarded. Please give me a real world use case of why you would ever want to do something like this.
>>55054511
>Searching and inserting are two different operations. You don't combine them.
No they aren't. Insertion into a linked list has a hard dependency on a prior search.
No matter how many times you try to escape with semantics, you're still fucking wrong, and I will keep reposting it.
Insertion does not exist without search. Code a linked list insert without a search and paste it.
>>55054512
I've said before, you no longer have a linked list. You have a fucking non-contiguous array. You're dumb as shit and don't even realize it.
>>55054513
Document markup. Used widely in javascript - adding to DOM after a particular element.
>>55054531
I have the following structure:struct LinkedListElem{
char *value;
struct LinkedListElem *next;
};
The list is a pointer to the first LinkedListElem. It is a linked list.
>>55054548
>Document markup. Used widely in javascript - adding to DOM after a particular element.
Pajeet detected. Go shit on a street.
>I have the following structure:
You have a container of non contiguous memory to which you store pointers. You have a non contiguous array, not a linked list. A linked list does not store pointers to elements, anywhere, ever, apart from within each element.
I swear to god if you seriously believe you have a linked list I will nuke India.
>>55051552
Then you're clearly in your first or second year of college and have taken no elementary operating systems or networked programming course.
I'll even give you a hint: How do you design a multi-threaded application where each thread of execution requires mutually exclusive access to a resource?
If you've found the answer: Congratulations, there is a linked list in your solution.
>>55054574
https://www.google.com/#q=C+basic+linked+list
First result:
http://www.macs.hw.ac.uk/~rjp/Coursewww/Cwww/linklist.html
If you really want to claim otherwise and continue throwing insults, show me a source that says linked list is built differently.
>>55054583
>I'll even give you a hint: How do you design a multi-threaded application where each thread of execution requires mutually exclusive access to a resource?
What the fuck do you need a linked list for there? It's simple locking, you moron.
>>55054600
What the fuck are locks made out of you fucking mong?
>>55054604
An atomic boolean should I wish.
>>55054596
Last time I'm responding to your faggot Indian street shitter ass.
A linked list does not have a side data structure storing pointers to elements.
You're wrong, and everything you think you know is wrong. Not only are you taking up more space than a linked list, you're also unsafely storing pointers that could at any moment become dangling. Kill your fucking self.
>>55054611
And am I right to assume your dumbass multithreaded program constantly polls the lock to see if it's open?
What if you wanted a program that wasn't dumb as fuck and used message passing to share the resource?
>>55054583
What this man said, also for very basic memory allocators. Pretty sure NT uses a linked list for Page Frame Allocation
>>55054600
How do you think the lock is implemented (hint, it's NOT a spinlock.)
>>55054623
I asked for a source and not your opinion.
Your claim is that my structure is not a linked list.
I provided a source that says it is.
Your opinion does not help here. You already expressed it. You can only salvage the argument by providing a source that refutes my source.
>>55054629
>And am I right to assume your dumbass multithreaded program constantly polls the lock to see if it's open?
If I was using a simple as fuck locking mechanism, of course. That's how the C++ standard defines locks, with added eye candy like timeouts and recursive locks and so on.
>What if you wanted a program that wasn't dumb as fuck and used message passing to share the resource?
What would you gain in terms of performance here compared to polling?
Your other threads would have to be listening and poll every cycle anyway, so what the fuck?
>>55054611
But he's talking about a mutex, not a spinlock.
>>55054661
Your OS controls the threads. It implements a sleep function. It doesn't need to poll and instead schedules more intelligently, skipping these threads until they're woken up by the thread occupying the resource.
>>55054662
A mutex in no way requires a linked list you fucking faggot. He's not talking about mutexes.
>>55054675
This is imbecilic. I can wake up the other threads by hand when one thread unlocks the mutex. The other threads can poll asynchronously if I want, or every cycle. I don't need the OS scheduler to do any more work than it is already doing. I want to see some performance reviews showing that your solution is better because it isn't.
Here is a simple linked list implementation in C that demonstrates O(1) insertion.#include "stdio.h"
#include "stdlib.h"
struct LinkedListElem{
const char *value;
struct LinkedListElem *next;
};
struct LinkedListElem *LinkedListPrepend(struct LinkedListElem **list,const char *value){
struct LinkedListElem *first=*list;
*list=malloc(sizeof(struct LinkedListElem));
(*list)->value=value;
(*list)->next=first;
return *list;
}
struct LinkedListElem *LinkedListInsertAfter(struct LinkedListElem *elem,const char *value){
struct LinkedListElem *e=malloc(sizeof(struct LinkedListElem));
e->value=value;
e->next=elem->next;
elem->next=e;
return e;
}
struct LinkedListElem *LinkedListPrint(struct LinkedListElem **list){
struct LinkedListElem *e=*list;
while(e!=NULL){
printf("%s\n",e->value);
e=e->next;
}
}
main(){
struct LinkedListElem *list=NULL;
LinkedListPrepend(&list,"d");
LinkedListPrepend(&list,"c");
struct LinkedListElem *b=LinkedListPrepend(&list,"b");
LinkedListPrepend(&list,"a");
LinkedListPrint(&list);
printf("===\n");
/* O(1) insertion */
LinkedListInsertAfter(b,"this goes after b");
LinkedListPrint(&list);
}
Outputs:a
b
c
d
===
a
b
this goes after b
c
d
The person who angrily wrote in upper case letter, no need to respond. I will accept your silent apology.
>>55054708
>I can wake up the other threads by hand
And what, pray tell, are you using to keep track of these threads?
Don't tell me you're going to wake everything up.
Or you're going to do something stupid and complex like keep track of the exact number of threads you need at any given time, instead of allowing the algorithm to handle it for you.
You're just being obstinate in not wanting to use linked lists even if it requires you to make your design more complex and harder to maintain.
>>55054738
How do you know that the proper spot of "this goes after b" is after b? In any real world use case where you have to maintain a proper ordering of your elements, you won't know where "this goes after b" belongs.
>>55054764
>And what, pray tell, are you using to keep track of these threads?
Are you fucking stupid?
An array, a vector. What the fuck is your obsession with using a linked list? What do you gain by using a linked list over an array to keep track of your threads? Nothing.
>>55054766
I already specified a use case here: >>55054548
Regardless of whether it upsets you or not, it exists and is a valid use case.
Even if there wasn't one, all I need to do is demonstrate that O(1) insertion is possible if you already know where you want to insert, and i did just that with the code I posted.
>2016
>not using cache-aligned linked array lists
Enjoy your inflexible arrays or slow linked lists.
>>55054766
Suppose the linked list is divided into two categories. Both of those categories have searchable items, so you don't want specialized nodes for A and for B. You just want a linked list of base pointers that works for A and B. Maybe the container for A and for B is pretty common.
So you're not totally concerned with a strict linear order. Maybe you're just interested in having, say, the first segment be just the A's and the second being just the B's.
So if you hold a node to the B...you get a list that still holds both kinds (one universal search!), for cases where you don't really care what the thing you've found is, so long as you've found a thing.
Consider a parser, for example. Maybe you're looking for a class or a var. But for some reason you want the classes after the vars. So you hold a pointer to the last var, and inject all of the classes after it. Doing so means each element can just have a next.
>>55054794
Okay, how do you figure out which thread is next?
Do you wake them all up and force them to fight for the lock?
Or do you wake up ONLY ONE and then just give the resource to it?
You cannot use a fucking array for this you mong.
Threads are race wars to the extreme. Your stupid threads will be fighting for a position in your array and go missing if you want to do it the smart way.
Or you can do it your retarded way and wake everything up every time you open up the resource.
>>55054796
>Regardless of whether it upsets you or not, it exists and is a valid use case.
No it isn't.
>>55054738
>Here is a simple linked list implementation in C that demonstrates O(1) insertion.
No it isn't.
You've not coded a linked list. You cheated by keeping a pointer to b, which is not in any way representative of a legitimate linked list. I can fuck your stupid as shit example up simply by requiring that you insert the element outside of main() and only after you had inserted b.
You're a fucking cheat, Pajeet. Go shit on a street somewhere. Nobody in the real world would allow you to write data structure this fucking stupid, and they wouldn't work for RANDOM INSERTS.
>>55054823
That's fucking retarded. You can just keep 2 lists.
>>55054841
>That's fucking retarded.
Welcome to India.
>>55054830
>You cannot use a fucking array for this you mong.
Of course I can.
I know which thread got the resource last, I increment the counter and activate thread+1.
>>55054831
I explicitly specified that I store the pointer to the list element after which I insert in my very first post. Here: >>55054309.
The thing I wrote is a linked list. If you want to argue about that, please do by all means specify a source that refutes my source - your opinion does not interest me.
Contain your anger and admit, at least to yourself, that you were wrong.
>>55054852
And you're going to write code to circle around this array?
Why not just have a thread point to the next one in the queue?
Why are you making everything so hard on yourself?
I hope you realize that I'm talking about "pointers pointing to pointers", being identical to linked lists.
Stop making everything so pointlessly difficult.
>>55054831
>You cheated by keeping a pointer to b
Autism
>>55054861
>I explicitly specified that I store the pointer to the list element after which I insert in my very first post
And that disqualifies your shitty data structure from being a linked list.
>The thing I wrote is a linked list.
It isn't, and it's not an opinion.
Show me a reference linked list implementation that maintains a separate data structure of pointers to elements within the linked list. I fucking dare you.
Here is one that proves my point:
http://www.learn-c.org/en/Linked_lists
And another:
http://cs.brown.edu/~jwicks/libstdc++/html_user/stl__list_8h-source.html
Now shut the fuck up you brown skinned curry stinking piece of dog shit.
Oh, and you still seem to have missed the point about maintaining an array of dangling pointers :^)
>>55054873
>insert/delete in the middle
>search time + O(1)
>= O(n)
Why did you post a pic to prove me right?
But okay Pajeet. Here is your fucking task.
Using this garbage code: >>55054738
And WITHOUT modifying main(), and AFTER a b c and d were inserted, and WITHOUT keeping pointers to each a b c and d, insert an element between c and d in constant time.
GO AHEAD.
>>55054906
PROTIP:
IF YOU CANT, YOU DONT HAVE A LINKED LIST.
Because a linked list requires that you insert an element anywhere within it, WITHOUT KNOWING WHERE YOUR ELEMENTS ARE LOCATED IN MEMORY.
https://gcc.gnu.org/onlinedocs/gcc-4.6.3/libstdc++/api/a00588.html#a4511f158e36cee6c3a75a59109416907
>Due to the nature of a list this operation can be done in constant time, and does not invalidate iterators and references.
OH WHATS THAT
PAJEET IS FUCKING RETARDED? WHODA THUNK IT
>>55054893
None of those imply that my implementation is not a linked list.
In fact, the first one is literally a copy of mine - replace const char * with int and you get same data structure.
>>55054708
>A mutex in no way requires a linked list you fucking faggot. He's not talking about mutexes.
This thread is about linked lists you, cock gobbler. Lurk the osdev forums some more, you might learn something about system efficiency instead of being an absolute idiot and actually POLLING things. Jesus fucking Christ, the whole reason the IO APIC/PIC exists is so you DON'T have to poll your fucking hardware devices. I don't know what planet you're on, but if you're stupid enough to do this, I hope you never work on any system code, because you're going to run into so many locking issues that it will be worse than actually using a linked list.
http://forum.osdev.org/viewtopic.php?t=14261
>>55054914
>None of those imply that my implementation is not a linked list.
Oh but they do, because none of them keep pointers to elements after insertion into linked lists.
>In fact, the first one is literally a copy of mine - replace const char * with int and you get same data structure.
Except that one is able to insert into the middle of a linked list without keeping an array of pointers on the side.
Answer my fucking task you shit smelling street shitter.
>>55054937
>Oh but they do, because none of them keep pointers to elements after insertion into linked lists.
Where does it say you're not allowed to keep pointers to list elements?
>Answer my fucking task you shit smelling street shitter.
My argument is pretty solid without doing your tasks. Maybe if you ask nicely I'll consider it.
>>55054190
Update the last element every insertion, really not that hard
>>55054955
>Where does it say you're not allowed to keep pointers to list elements?
If you do, you no longer have a linked list. Very simple. A linked list does not occupy more space than the size of its elements. It is allowed to occupy n*sizeof(element). Your linked list occupies n*sizeof(element)+n*sizeof(size_t).
You're a fucking RETARD, now get the hell back to India where you belong.
>My argument is pretty solid without doing your tasks
In other words, you can't because you're fucking wrong and I blew you the fuck out.
>it-its a linked list b-b-but i cant insert into it unless i keep pointers!
Your linked list is not only wrong, it's incomplete and uses up more space than it is allowed to.
>>55054331
Think of it like this, how do you get to X? You still need to traverse from the head or tail to X to be able to insert there
>>55054287
>lel fuck explaining and giving arguments, lets just rage, that'll show em
>>55054963
So you're inserting to the end every time? Array lists can do that in constant time too.
>>55054987
What if your search is based on name, and your linked list keeps track of a midway point so that your searches don't always go from the start of the list?
>>55055019
>and your linked list keeps track of a midway point so that your searches don't always go from the start of the list?
Still O(n) complexity.
>>55055000
But anon arrays are static.
But to keep in line with this thread: you Cock gobbling street shitter
>>55055033
I never said anything about arrays. I was talking about array lists.
>>55055019
than would be O(n/2), which is still O(n)
>>55055038
Nigger.
But yes misread my mistake.
You brown visa having cow fucker
>>55054906
>Why did you post a pic to prove me right?
Insert in the end can be O(1), which was the original claim.
>>55054913
>>55054906
What's with the capslock and racism? How autistic are you?
>>55055033
>But anon arrays are static.
What? No they're not.
realloc() + assign [x] to something is O(1).
>>55055060
>Insert in the end can be O(1), which was the original claim.
No it wasn't. The claim was insert anywhere would be O(1). I said from the start insert at the back is O(1).
Protip: insert at the front can be O(1) too.
>>55055061
Isn't realloc O(n)? The more elements you have, the more you have to copy.
>>55055061
You would have to reallocate the entire array. Array elements by def are contiguous memory
>>55055086
Allocating the memory can be done in constant time, and copying the elements over can be done in amortized constant time.
>>55055095
But you're not modifying the array you're creating a new one. Why are you arguing arrays are static as their length is defined at creation
>>55055109
I'm not.
>>55054955
>>55054963
>>55054997
I can explain what he means. First, here is the definition of a linked list from Wikipedia.
>In computer science, a linked list is a linear collection of data elements, called nodes, pointing to the next node by means of a pointer.
Notice how there is no fancy tracking pointer in the definition. What you're referring to as linked list, is in fact, linked list/fancy tracking pointer, or as I've recently taken to calling it, linked list plus fancy tracking pointer. With an actual standalone linked list that follows the definition of a linked list, you don't automatically assume it includes the fancy tracking pointer because that would mean you added something to the definition.
>>55055080
No, realloc is O(1).
>>55055200
>Notice how there is no fancy tracking pointer in the definition. What you're referring to as linked list, is in fact, linked list/fancy tracking pointer, or as I've recently taken to calling it, linked list plus fancy tracking pointer.
Well played.
And yes, that is of course the explanation he wanted but I on purpose denied him because I wanted to see how delusional Pajeet can be.
Here is another example of O(1) list insertion, this time using C++ standard lists. std::list is a doubly linked list, but the example can work with a single linked list also.#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
int main(){
std::list<int> list;
for(int i=0; i<10; i++)
list.push_back(i*10);
std::list<int>::iterator it = std::find(list.begin(),list.end(),50);
it++;
list.insert(it,51);
list.insert(it,52);
list.insert(it,53);
list.insert(it,54);
list.insert(it,55);
list.insert(it,56);
for(std::list<int>::iterator it = list.begin(); it!=list.end(); ++it)
std::cout << *it << '\n';
return 0;
}
Here, we have one O(n) lookup and six O(1) insertions.
>>55055200
Nowhere in this definition is implied that storing a pointer to a data element would make your data structure not a linked list element. Conveniently, in the example above, a pointer to a data element is stored using std::list<int>::iterator structure. and the action of storing that pointer does not disqualify the structure from being called a list.
This just keeps getting better.
>>55055239
>Here, we have one O(n) lookup and six O(1) insertions.
W R O N G.
std::find is LINEAR TIME.
You have LINEAR TIME insertions. main() is LINEAR TIME.
>>55055250
It's a lookup. A liner time lookup. I have one of it. Just like I wrote in the post you're quoting. And I have six O(1) insertions after it.
>>55055257
[ ] has understood upper bound
[x] has not understood upper bound
Do they teach complexity theory in India? If not, they should start.
>Nowhere in this definition is implied that storing a pointer to a data element would make your data structure not a linked list element.
Nowhere in that definition does it say a linked list shouldn't be able to launch nuclear weapons.
Are you this dumb? Please be trolling. YOU DEVIATED FROM ITS DEFINITION and claim that a linked list can be anything because the definition does not EXCLUDE everything.
KILL YOURSELF.
>>55055239
You can do the same thing with an array list.
>>55055239
>Conveniently, in the example above, a pointer to a data element is stored using std::list<int>::iterator structure
And this part is not part of the container, therefore it is NOT part of the linked list data structure. It's part of what you're doing WITH the linked list. There's a very distinct fucking difference, you dumb piece of shit.
>>55055268
Looking at your posts, it looks like you seem to think that main() is insertion. main() is not insertion. list.insert() is insertion. And list.insert() is O(1).
>>55055277
I am not advocating for use of lists. 'm just providing examples demonstrating that list insertion can be done in linear time.
>>55055283
I wrote before that the pointer I'm storing is not the part of linked list. I store the pointer, and using it I'm able to do O(1) list insertions - just like I wrote in my first post: >>55054309.
>>55055307
In order to do list.insert you had to do list.find, which is O(n). There is no conceivable way to get around that requirement without coming up with convoluted scenarios.
>>55055307
>I wrote before that the pointer I'm storing is not the part of linked list. I store the pointer, and using it I'm able to do O(1) list insertions - just like I wrote in my first post
Then you don't have a point, because your linked list still cannot insert to a random position in constant time. Only your piece of shit code around the linked list can (with its unsafe use of pointers). That does not make your linked list O(1) insertion, you stupid faggot. Understand this.
>>55055307
>Looking at your posts, it looks like you seem to think that main() is insertion.
main() is insertion, because main() is calling insert. main() has a complexity of O(n). You are not calling main() without having O(n) complexity.
>list.insert() is O(1).
Which makes not one bit of difference because you cannot use list.insert() without passing an iterator, and to acquire iterator you have a O(n) operation. You've simply wrapped both steps by one function, which makes that function O(n).
>this fucking retard genuinely believes if he calls O(n) first and then O(1), his entire code is bound by O(1)
>>55055347
>>55055339
>>55055307
I will say this again just to be very clear
U P P E R
P
P
E
R
B O U N D
O
U
N
D
>>55055307
>Looking at your posts, it looks like you seem to think that main() is insertion. main() is not insertion. list.insert() is insertion. And list.insert() is O(1).
>>55055339
In my code I do one find and six inserts. find is O(n) and each of inserts is O(1).
>>55055347
>your linked list still cannot insert to a random position in constant time
Here is the method that inserts in constant time: http://www.cplusplus.com/reference/list/list/insert/
>>55055347
>You are not calling main() without having O(n) complexity.
Of course. After all, it also creates a list. The fact that it creates a list should be evidence good enough that main is not insertion.
>Which makes not one bit of difference because you cannot use list.insert() without passing an iterator, and to acquire iterator you have a O(n) operation.
If you look at definition of std::list, there are plenty of other methods that return an iterator. Particularly, insertion.
>>55055347
>his entire code is bound by O(1)
Never claimed that one. Only claimed insertion itself is O(1). I provided an example where there is one O(n) lookup and after it six O(1) insertions.
>>55055385
You can do a billion fucking inserts for all I care. You are not going to get past the O(n) requirement for finding the spot to insert into the first time.
>>55055385
>Here is the method that inserts in constant time: http://www.cplusplus.com/reference/list/list/insert/
It takes an iterator. You cannot use it without being bound by O(n), you fucking dumb asshole.
>Of course. After all, it also creates a list. The fact that it creates a list should be evidence good enough that main is not insertion.
You MUST be trolling.
I'm going to ask you one last time.
Do you believe that main() is O(1) complexity? By extension, if you say no, do you admit that you're not inserting into a linked list at constant time complexity?
>>55055385
>Never claimed that one. Only claimed insertion itself is O(1). I provided an example where there is one O(n) lookup and after it six O(1) insertions.
Look ma I'm backpedaling!
>>55055385
INDIA IN CHARGE OF COMPLEXITY THEORY EVERYONE
INDIA
>>55055402
Do I have to? Every single insert is O(1).
Let's imagine that insertion is O(n).
Say, you have a list with n elements.
A function that finds an element in the list by its value and then inserts n new elements after it, would be O(n*n).
But with list it's O(n) operation instead. It's O(n) operation because list insertion is O(1).
>>55055449
>A function that finds an element in the list by its value and then inserts n new elements after it, would be O(n*n).
That would be a stupid function. You can build the list of elements to be inserted and then insert ALL of the elements at once in ONE insert.
>>55055406
>Do you believe that main() is O(1) complexity
It's not. I never claimed main() is O(1).
>By extension, if you say no, do you admit that you're not inserting into a linked list at constant time complexity?
list.insert is O(1), so, yes.
>Look ma I'm backpedaling!
Here's my first post: >>55054309
>>55055449
>Do I have to? Every single insert is O(1).
Holy fucking shit, what will it take for you to understand how complexity works?
>>55055477
>list.insert is O(1), so, yes.
HOLY SHIT GUYS LOOK
MY BUBBLE SORT IS O(1) COMPLEXITY BECAUSE A SINGLE ASSIGNMENT IS O(1)
FUCK MATHEMATICAL SCIENCE
FUCK IT! INDIA HAS THE ANSWERS
>>55055475
>That would be a stupid function.
So, you can't find a problem with my reasoning then?
Just call it stupid and hope it sticks?
>>55055486
Insertion and lookup are two different functions.
>>55055477
>list.insert is O(1), so, yes.
>still has not understood complexity theory
>>55055503
>Insertion and lookup are two different functions.
No they aren't. You can't insert into std::list without first iterating it. Prove me wrong.
>trying to compare using Big Oh notation
used Tilde notation you fags
>>55055503
Sure, if you want to use suboptimal algorithms, then the structure of a linked list can offset the cost of inserting. It still has a total runtime of O(n) though, not O(1).
>>55054022
>what is array doubling
>>55055545
>Sure, if you want to use suboptimal algorithms, then the structure of a linked list can offset the cost of inserting. It still has a total runtime of O(n) though, not O(1).
B-B-BUT THE INSERTION IS O(1) BAWWWW
FUCK UPPER BOUND ITS O(1)
IT DOESNT FIT THE NARRATIVE
Linked list insertion is O(n^2)
>>55055521
The proof is in >>55055449.
>>55055545
Insertion is O(1). Lookup is O(n). Lookup is not an integral part of insertion - you can get the pointer to insert into from other sources - particularly, from another insertion. The proof that insertion is O(1) is in >>55055449.
>>55055586
>The proof is in >>55055449.
No it isn't. I asked you a straight up fucking question you piece of shit. Answer it.
I want you to show me how you can list.insert without having first iterated said list.
If you can't, you're a lying piece of subhuman shit.
>>55055586
>Lookup is not an integral part of insertion
Prove this. Show me code that calls list.insert() without prior iteration and does not insert an element at the front or back. Insert into the middle without iteration.
>>55055586
>you can get the pointer to insert into from other sources - particularly, from another insertion
How will you get the iterator to insert into the middle of a list from another insertion? Show me.
>>55055586
I'm tired of arguing semantics. Whatever you classify "insertion" as doesn't change the fact that whatever algorithm you are using that uses that operation will be at least O(n). Ultimately, any algorithm that uses a linked list can be modified to achieve the same or better runtime complexity using an array list, as proven in real world performance tests.
>>55055584
that is for random insertion
>Lookup is not an integral part of insertion
Prove this. Show me code that calls list.insert() without prior iteration and does not insert an element at the front or back. Insert into the middle without iteration.>Lookup is not an integral part of insertion
Prove this. Show me code that calls list.insert() without prior iteration and does not insert an element at the front or back. Insert into the middle without iteration.>Lookup is not an integral part of insertion
Prove this. Show me code that calls list.insert() without prior iteration and does not insert an element at the front or back. Insert into the middle without iteration.>Lookup is not an integral part of insertion
Prove this. Show me code that calls list.insert() without prior iteration and does not insert an element at the front or back. Insert into the middle without iteration.>Lookup is not an integral part of insertion
Prove this. Show me code that calls list.insert() without prior iteration and does not insert an element at the front or back. Insert into the middle without iteration.>Lookup is not an integral part of insertion
Prove this. Show me code that calls list.insert() without prior iteration and does not insert an element at the front or back. Insert into the middle without iteration.
>>55055642
the point of a linked list is to not insert in the middle, why would anyone even do that
>>55055661
The point is that Pajeet is a lying piece of dumb shit who understand neither linked lists, nor coding, nor complexity theory.
He claims he can insert into the middle of an std::list with O(1).
>>55055661
There is no point to linked lists. Vectors are superior.
>>55055604
I don't have to demonstrate an example that does this without iteration. In my original post, >>55054309, I talk about a stored pointer. The pointer can very well be obtained by iteration. After it's obtained, it's already there, and you can use it as many times as you want to do insertion - each of those insertions will be O(1).
>>55055619
> I'm tired of arguing semantics.
Great!
Let's look into what well known sources say about which one of us is right!
https://en.wikipedia.org/wiki/Best,_worst_and_average_case
http://bigocheatsheet.com/
https://www.google.com/#q=list+insertion+complexity
>>55055673
Unless you want to push an element at the front.
Vector is O(n) for that, but a deque/list is O(1)
>>55055678
>I don't have to demonstrate an example that does this without iteration
So you fucking can't, you lying piece of subhuman trash. You fucking CANT.
>>55055678
Have fun with your shitty performance.
>>55055685
>there's no such thing as a double ended vector
>>55055685
> So you fucking can't, you lying piece of subhuman trash. You fucking CANT.
If you read my original post I never claimed I would do that. I only said that insertion itself is O(1).
>>55055690
What does that have to do with anything? I'm not advocating for use of lists at all.
>>55055685
insert at the end and translate the index so that it appears to be at the start, bang, amortized O(1) inserts with a vector
>>55055073
>Protip: insert at the front can be O(1) too.
No shit sherlock.
Why are you re-stating things I already said?
>>55055619
So you want to tell me that I will get the same performance with a arraylist as with linked list when I have elements that are ~cache size, or even ~page size?
Especially when I abuse them as stack?
But I have to admit, that's really synthetical.
Also you break assumptions if you want to have continues memory and random insert/removal, since every other pointer to the object will be dangling/pointing to wrong object if you move it in your array
>>55054822
>dat image
>>55054418
You can't guarantee all the items have the same size. And even if they would, list elements are not stored in contiguous form by default (and if they were to be, then an array would be better)
>>55054822
I'm glad HIRO ridded us from such toxic people.
>>55055743
You shouldn't be storing large or mutable structures in lists anyway, but pointers or references to them.
>>55055709
>If you read my original post I never claimed I would do that. I only said that insertion itself is O(1).
I don't think I've ever seen someone on 4chan get blown out as hard as this and then continue to shift goalposts for 2 fucking hours.
>>55055699
>there's no such thing as a double ended vector
Are you fucking stupid? A double ended vector is still O(n), you still have to shift out all elements from n+1, otherwise it ceases being a vector. Vector implies contiguous memory. You're not changing that.
>>55055726
>insert at the end and translate the index so that it appears to be at the start, bang, amortized O(1) inserts with a vector
I would say this is okay to do but it really isn't, because a vector wasn't designed for this, but a deque was, so use a fucking deque.
>>55055827
That really depends on the usecase.
And saving that indirection may well be worth it.
But that's with linux kernel style lists, with C++ std::list I am on your side.
>>55055857
>>55055857
Please look up how a double ended vector works.
>>55055827
you wut
the point of lists is for immutable data, you can slice lists and add them to new lists for constant time
>>55055874
You had better fucking do that, because a double ended vector still requires you to reallocate even if you're only reallocating parts. It's still O(n).
>>55055891
Not for inserting at the front.
To illustrate why search/insertion seperation matters, let's consider iterating over a list and inserting an element after a few of them.
With one we use a std::list: the iterating along is O(n) and the insertion is O(1) for a combined complexity of (n).
The other is a std::vector: the iterating through is O(n) and the insertion is also O(n) for a combined complexity of O(n*n).
The distinction that insertions are O(1) for linked lists as compared to vectors is important here.
>>55047417
Wait, I thought linked lists could be used to implement vectors.
Someone tell me what the fuck I'm thinking about.
I thought you could implement a "vector", that is, a data structure similar to an array that can grow and shrink in size as you add elements, either through simple arrays or linked lists.
SOMEONE PLEASE EXPLAIN
>>55055923
Batch insertions on a vector can be done in O(n) time.
>>55055922
And bogosort is O(n)
>>55055842
My original point posted in my first post still stands.
>>55055946
Someone please define a "vector" for me.
>>55055978
It's not. But you can implement a deque with an array that allows for constant time inserts and deletions at both the front and the back. It's not my fault if your first semester CS course didn't teach you how and you can't figure it out. Just look at the implementation in the standard C++ library.
>>55055923
>combined complexity of O(n*n).
No, if you do a single O(n) iteration and a O(n) insert, it sums as O(n + n). It's O(n*n) only if you're modifying the container on each step of the iteration.
>>55056006
>>55055946
A vector can grow and shrink in size, but the C++ standard lib requires its vector type to store the elements contiguously, which's not possible with linked lists.
>>55055959
True, I still think that the point still stands that it's worth considering the two operations separately.
If you're a fool enough to not realise that your O(1) insertion requires you to already have an iterator/pointer to the element and you go searching each time then hope is lost for you anyway.
>>55055987
Nope, it's utterly destroyed. You outed yourself as a fucking fool who will go to some employer and claim your code is O(1) when in reality it's O(n).
What am I talking about, you work in a fucking call center.
>>55056060
>If you're a fool enough to not realise that your O(1) insertion requires you to already have an iterator/pointer to the element and you go searching each time then hope is lost for you anyway.
And yet again you don't understand complexity.
Even if you were to call:
find()
insert()
find()
insert()
over and over again, you're STILL only dealing in O(n) complexity.
I really, really hope you die in a horrible accident just because I don't want to believe people like you exist and possibly try to teach less fortunate folks your stupid wrong bullshit.
>>55056020
Where did I say you're doing a single O(n) insert?
>>55056062
Here is my original post: >>55054309
Everything I posted there still stands.
>>55056060
>True,
You just fucked your own O(1) insertion claims in the ass. Congrats.
> I still think that the point still stands that it's worth considering the two operations separately.
This NEVER was a point, it NEVER will be a point, and it NEVER could be a point. NOBODY does this and it's mathematically INVALID to do so.
>>55056083
You can keep referencing that post a million times, you stupid nigger still got blown out and everyone can see it.
>>55056079
>blowing yourself out EVEN MORE
It doesn't matter how many O(n) inserts you do in one step, you're still O(n).
Want to carry on getting fucked in the ass by my brain?
>>55055923
>The distinction that insertions are O(1) for linked lists as compared to vectors is important here.
It isn't, because both operations are bound by O(n) in your example.
Confirmed for not knowing shit. Why are you so fucking retarded, man? What is wrong with your fucking mind?
>>55056088
LoL.
I'll just leave this here and head off:
http://en.cppreference.com/w/cpp/container/list/insert
>> Complexity
>> 1-2) Constant.
>>55056135
>LoL
>literally writing that
>literally confirming that you're mentally challenged
For someone who loves arguing semantics so much, you sure are happy to ignore the most important one:
> Iterator pointing to the inserted value
To acquire this requires O(n) operation.
But it doesn't fit your narrative, does it? You're so fucking stupid, you just have to keep lying, and lying, and lying, and lying.
>>55056100
I will keep referencing it until you refute it, which you did not manage so far.
>>55055223
It's O(n), inbred.
So who do I believe
>>55056222
No it isn't. Why the fuck would it be O(n)? It simply copies the old data into a new segment of larger size, you fucking asswipe.
>>55056304
The angry all caps guy
>>55056304
Literally every source in the world lists linked list insertion as O(n).
There's only one dumbfuck Indian call center agent on this board who claims it's O(1) and still does because he possesses ignorance of the highest order.
A wonderful trait for a coder no doubt :^)
>>55056401
https://en.wikipedia.org/wiki/Best,_worst_and_average_case
http://bigocheatsheet.com/
https://www.google.com/#q=list+insertion+complexity
In addition to those source stating it's O(1), you failed to refute my arguments.
>>55056384
HOW MANY ELEMENTS DO YOU THINK IT COPIES?
>>55056423
That's IF you know where you're insterting
If you don't you'll have to search and then instert which is O(n) + O(1) = O(n)
>>55056423
Those sources explicitly state that it is only O(1) if you already are in the middle of an indexing operation, which makes your whole operation O(n) by default.
Meanwhile, you claimed that you can insert without indexing, thereby not needing O(n) complexity to insert, which has been proven wrong a million times over in this thread.
This is something you're still resisting, but I know deep down you know it to be true. Over time you will accept it.
>>55056450
>HOW MANY ELEMENTS DO YOU THINK IT COPIES?
Oh my fucking god, realloc() does not copy elements one by one, it copies &a to &a+n you fucking idiotic moron. It's a lowest level memory operation in C, not a fucking high level container function.
>>55056478
>Meanwhile, you claimed that you can insert without indexing, thereby not needing O(n) complexity to insert, which has been proven wrong a million times over in this thread.
I'll refer you to my original post:
>Cases where you know where you are inserting are plenty - you have a pointer to an element of a list and want to insert another right after it. That's O(1).
That's your if right there. Does that mean you have issues with reading comprehension?
>>55056478
> Literally has n in his reply
You must be a stupid idiot
>>55056533
Jesus man this is painful. It copies memory into new memory. It does not iterate anything. It just copies from start address until end address into new address. The n has no impact because it doesn't matter how long the block is. Fucking hell.
>>55056561
How do you imagine CPU does the copy operation? Does it take same time to copy 10 bytes as it does to copy 100000 bytes?
>>55056527
Your case was proven to be bullshit, you claimed that a lookup followed by an insert was O(1) and got destroyed for it.
Then you claimed that you could insert into the middle of a list without iterating, and I challenged you to prove it and you backed out like a fucking pussy.
This is the last reply you're going to get out of me and the sad part is you're not trolling, you actually are mentally fucking handicapped.
Take a course on complexity theory.
>>55056584
You're joking right? This has NOTHING to do with complexity of realloc.
>>55056593
Implementation of malloc has everything to do with its complexity.
>>55056584
Oh, and yes, yes it does. We're talking about a contiguous block of memory here. The addresses are known.
THERE IS NO FUCKING ITERATION.
>>55056603
Realloc, not malloc. Realloc can grow memory in place, it needn't even call malloc most times.
And malloc is constant time too.
>>55056585
You asked me to demonstrate something I did not claim in the first place, I refused. My claim still stands.
>>55056661
>Lookup is not an integral part of insertion - you can get the pointer to insert into from other source
Straight up liar.
You claim you can insert without lookup into anywhere. Prove it.
Pussy.
>>55056661
>Lookup is not an integral part of insertion
L i e s. You did claim it.
>>55056661
>Lookup is not an integral part of insertion - you can get the pointer to insert into from other source
Repostan until Pajeet hangs himself
>>55056661
>Lookup is not an integral part of insertion - you can get the pointer to insert into from other source
kys
>>55056689
>>55056704
>>55056725
Still claim it. All literature lists insertion as separate from lookup. You can insert at start or at a position returned by another insert. Lookup is not an integral part of insertion.
>>55056749
Then prove it and show code that inserts into std::list middle position without iterating first.
I'll wait :^)
>>55056763
>using the smiley with a carat nose
>>55056763
Here you go:list.insert(it,51);
Just like I wrote at start, I have a pointer to the place where I want to insert stuff - it's stored in the it structure.
This runs in constant time.
>>55056844
Error: it is undefined.
You failed to demonstrate it you fucking embarrassment.
Any additional wrapper code is not existent nor allowed, and it is NOT part of the linked list itself, therefore you're not altering the linear time insert in any way.
And besides, your side structure wastes memory. Potentially millions of stale fucking pointers to dead linked list elements PLUS the cost of maintaining it. Great performance bro.
And what about deleting? What if you delete it? What, will you do an O(n) lookup through your SIDE STRUCTURE now in order to keep your supposed O(1) complexity?
Your design is so fucking broken it's not even funny.
>>55056844
Also, you fucked up again. it is your structure? Why are you passing it to a function expecting an iterator?
>>55048088
Haskell does this
>>55056907
It is defined outside. I am only demonstrating the insert. Read my code to find out what it is.
>And besides, your side structure wastes memory. Potentially millions of stale fucking pointers to dead linked list elements PLUS the cost of maintaining it. Great performance bro.
How many times must I say this? I am not advocating the use of lists. Only stating the obvious - that insertion is O(1).
>>55056934
It's the std::list, dummy. And it is std::list<int>::iterator.
>>55056401
Linked lists as FIFOs enqueue elements in O(1), that is, as long as you implement a FIFO sensibly, with a pointer to the last element of the queue. Arbitrary insertion (i.e. wherever you want) is still O(n), but a linked list which can do arbitrary insertions is not a FIFO anymore.
tl;dr linked lists are efficient as long as they're used as queues
>>55057108
Read above for the faggot claiming random insert is O(1).
I'm through arguing with that stupidity.
>>55057241
Tuck your tail and run. You have no counterargument. List insertion is O(1) in cases when you already know where to insert, and it's really stupid of you to claim contrary to such an obvious statement.
>>55057276
>he thinks having the last word will make him right
sage
>>55057403
I am right - last word or not.
But as long as you don't post a counterargument, I also win the argument in addition to being right.
>literally hovering the thread biting your nails until I reply again
I fucked your head.
>>55057459
> hovering the thread
Someone out there still uses 4chan without 4chanx. Hilarious.
>>55057481
>thinking it provides anything worthwhile that isn't built into 4chan by now anyway
top kek you're a greater fool than I thought
Doesn't understand complexity, is butthurt over being proved wrong, and uses laggy botnets
You fail at everything
>>55057515
You did not prove me wrong. By all means, please do continue the argument by responding to my posts.
>>55057535
Nope, this is over. I won, you couldn't back up your claims, you lost. Move on.
Or don't and keep crying here. I'm going into town, maybe celebrate my victory with an ice cream :^)
>>55057599
Here's a post without your response: >>55057036
Bye.
>>55054316
>No it's not. Random insert into a c style array is O(1), because you can memcpy the first portion of the array into a grown space, insert your element, and then copy the remaining portion.
If you know an O(1) memcpy, you can patent it and get filthy rich.
You're just embarrassing yourself.
>>55057632
You need to read this: http://blog.httrack.com/blog/2014/04/05/a-story-of-realloc-and-laziness/
Holy fuck CS freshmen are retarded
>>55056467
I hope you are not allowed to bread
>>55056605
So when we copy it blocks of (lets say SIMD 256B) and move 4KiB of data, we do not iterate over 16 blocks of 256B data?
How does that magic work?
>>55052424
>arrays have O(1) lookup
In Java this is only true if you know what index the object you're looking for is at. If you're looking for the index of an object ArrayLists are the only O(1) solution
>>55057599
Guys, guys, imagine some actual fucking real code and not some bullshit demonstration.
Something like, let's say a slideshow. And the user can go through it viewing it.
And at some point he decides: hey, I want another picture in here and clicks FUCKING INSERT, which will be O(1) sinde we know where to insert
The iteration is not part an integral part of insert. But *some* iteration takes place before.
