Linked lists on suicide watch

Linked lists on suicide watch

Other urls found in this thread:

google.com/#q=C basic linked list
macs.hw.ac.uk/~rjp/Coursewww/Cwww/linklist.html
twitter.com/SFWRedditImages

What's the point of this thread?

What's the point of "nvidia on suicide watch" threads?

>Sup Forums 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, user, 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

>I don't know about caches
>I don't know about amortized analysis
yours sucked

>strings are linked lists

what shitty language are you using?

Befunge

Haskell

Erlang

All of them.

C#

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

>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.

That's a (((Lisp))) myth.

If arrays were linked lists, you would have to read the previous elements to find the next element.

Try doing a[a[a[a[a[a[i]]]]]] with linked lists.

I have seriously never needed to use a linked list. I don't understand the need to teach them.

You what, mate? Strings are arrays of characters.

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?

This. Also linked lists make skip lists easier to understand and people actually use those sometimes

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

Or if your elements are fucking huge, like the task struct in the linux kernel

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.

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

Linked lists are O(n) insertion faggot. How do you magically have a pointer to the place you want to insert into?

> How do you magically have the index of the location you want to insert to
Only count the insertion operation, not the lookup+insertion.

How do you insert without doing a lookup?

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.

You already spent O(n) time trying to find the element. There is no advantage over an array list.

You can Concat cons lists very fast in functional langauges

>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.

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.

>LLs have O(1) insertion.

WRONG unless you're inserting at the front or the back

>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)

>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

>THAT OPERATION IS O(n)
yes, and it's O(n^2) for an array.

>WRONG unless you're inserting at the front or the back

Still O(1) inserting at an index.

>Say I'm scanning through the list
Already O(n)

You already are at O(n) just to find the place where you what to insert.

>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.

>Still O(1) inserting at an index.

REEEEEEEEEEEE HOW FUCKING STUPID ARE YOU HOLY SHIT

>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.

It's correct you fucking doofus. If you're inserting at head, tail, or X it's always O(1)

No it's not you fucking idiot. You can insert multiple elements at once into an array list.

>you have a pointer to an element of a list
How the fuck did you get the pointer to the element?

>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.

>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.

>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.

>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 Sup Forums 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.

>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

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

If you don't care about order than you can use a hash table.

>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

Holy shit you are retarded.

>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

Refute it if it's wrong shit for brains

You're in a corner here and can't get out

Rearranging pointers doesn't change the O notation

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.

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?

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.

>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.

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.

>>Rearranging pointers doesn't change the O notation

This is true. Your entire argument falls apart now.

>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.

>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.

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.

>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)

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.

>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.

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)

>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.

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.

>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.

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.

Document markup. Used widely in javascript - adding to DOM after a particular element.

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.

>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.

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.

google.com/#q=C basic linked list

First result:
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.

>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.

What the fuck are locks made out of you fucking mong?

An atomic boolean should I wish.

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.

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?

What this man said, also for very basic memory allocators. Pretty sure NT uses a linked list for Page Frame Allocation

How do you think the lock is implemented (hint, it's NOT a spinlock.)

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.

>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?

But he's talking about a mutex, not a spinlock.

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.

A mutex in no way requires a linked list you fucking faggot. He's not talking about mutexes.

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.

>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.

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.

>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.

I already specified a use case here: 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.

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.

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.

>Regardless of whether it upsets you or not, it exists and is a valid use case.

No it isn't.

>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.

That's fucking retarded. You can just keep 2 lists.

>That's fucking retarded.

Welcome to India.

>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.

I explicitly specified that I store the pointer to the list element after which I insert in my very first post. Here: .

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.

K