[a / b / c / d / e / f / g / gif / h / hr / k / m / o / p / r / s / t / u / v / vg / vm / vmg / vr / vrpg / vst / w / wg] [i / ic] [r9k / s4s / vip / qa] [cm / hm / lgbt / y] [3 / aco / adv / an / bant / biz / cgl / ck / co / diy / fa / fit / gd / hc / his / int / jp / lit / mlp / mu / n / news / out / po / pol / pw / qst / sci / soc / sp / tg / toy / trv / tv / vp / vt / wsg / wsr / x / xs] [Settings] [Search] [Mobile] [Home]
Board
Settings Mobile Home
/g/ - Technology

[Advertise on 4chan]


Thread archived.
You cannot reply anymore.


[Advertise on 4chan]


Learning about linked lists/doubly linked lists in a course. It seems to be a bullshit learning exercise. Do any of you actually use linked lists? Are they even used for anything practical?
>>
>>80340743
Your operating system uses them. The runtime of your favorite programming language uses them. You are approaching the peak of mount stupid.
>>
>>80340792
Holy fuck. I was just told it was an alternative to an array.
>>
>>80340845
It's an alternative to an array list. An array is a much more primitive concept than lists.
>>
>>80340743
I use them all the time because C lacks of a STL
>>
>>80340743
They are a trick around memory management for variable storage. If you haven't learned about compute complexity yet, don't worry about the fact that there is a million ways to do the same thing.
>>
>>80340743
Yep. I had a case where we needed to increment a list in an arbitrarily large collection of lists, based on certain conditions. There were a few different collections that we could use, but they all required some complicated holding a tracking indices. So a collection of linked lists, where we could just call an
 .increment 
method seemed much easier to me.

Don't think I explained that very well.
>>
>>80340845
You were told that it's an alternative to an array (which isn't entirely correct) and still thought it was stupid academia practice bs? Really?
>>
File: dancing-ferris.gif (258 KB, 734x490)
258 KB
258 KB GIF
>>80340743
Just use a hash map lolololololo
>>
not really although they're used for a few things, but if it takes you more than 30 seconds to grasp you're too low IQ to be a programmer anyway
>>
>>80340891
Depends on what you are doing. If you don’t need quick searches then hashmap doesn’t make any sense and it’s just bloat. For example if you made a queue you’d probably just use a linked list it’d be dumb as fuck as fuck to use a hashmap.
>>
>>80340743
Think about how a data structure will look like when you don't order them into next and prev instead use left_child and right_child. Linked list is the entry point in learning tree like data.
>>
>>80341184
If I made a queue I'd use a heap so I could prioritize
>>
>>80340743
bruh it's shit
the std library implementation sucks if it doesn't 100% cover your use case and it rekts the data locality principle of optimization so you think you're being 420iq programmer possessed by god but you might as well be a pythonfag
so you just get fucked in the ass performance wise compared to just removing and shifting an array.
>>
They're one of the most common data structures around you dense fuck.
>>
>>80340792
Member when Bjarne Stroustrup said we should avoid LL?
>>
>>80340743
I’ve used them many times in my career. Babby’s first data structure. You don’t need them if you’re only interested in being a low income code monkey

They are like arrays in the sense that they’re a way of maintaining lists. They’re better in the sense that they have cheaper insertions. Also a good use case for recursion
>>
>>80340883
Me too, was it for an OS class in denmark?
>>
File: 1613877908108.png (348 KB, 1203x882)
348 KB
348 KB PNG
>>80340845
Absolutely not.
Arrays operate on the stack with a fixed length, while linked lists and vectors operate as allocated memory on the heap with flexible size.

Personally I don't really use linked lists in C, because seeking to the point of the list just to get a certain node's data is inefficient. So I use my own vector implementation (since libc doesn't have one standard) so I can use it like a resizable array with direct insertion and deletion.
>>
>>80341731
No https://www.geeksforgeeks.org/variable-length-arrays-in-c-and-c/
>>
>>80341759
>No
Variable sized lengths != flexible and resizable lengths

int a = 5;
int arr[a];

you can't resize arr after it's declared. Sure, if a was something passed to a function, the array would be different length each time it's declared, but it's still fixed length.
>>
>>80341801
When you use a vector class it is just an abstraction using arrays under the hood.
>>
>>80340743
Everything in that course, assuming it's a data structures course, is used heavily everywhere.
>>
>>80341828
No, it's not that simple. Arrays are ALWAYS on the stack, they are local variables that get deleted once whatever block they were declared in goes out of scope.

In an array, each member is directly in front of the other in memory. The array variable itself is just a pointer to the beginning member at 0, which is why pointers are the same as arrays.
arr[2] is the same as arr+2

Linked lists are chains of allocated chunks of memory, they are do not need to be directly in front of each other, because each node's struct has the pointer to the next node. While vectors do indeed have an array of pointers to whatever data they hold, that is still an array of allocated memory at different position of memory on the heap. The array is just used to easily look up each pointer
>>
>>80341731
not defining the length of the array as a variable pleb
>>
>>80341929
Lmao its still fixed length, what are you arguing about. Do you think if you change the variable that the array size will change too, don't be a dumb dumb
>>
>>80341911
>Arrays are ALWAYS on the stack
No you’re a brainlet
int* a = malloc(sizeof(int)*N);
Is heap allocated. Only the pointer goes on the stack. The array goes on the heap
>>
>>80341970
You are being language lawyered faggot. Pointers aren't arrays, not even if they point to a contiguous section of memory.
>>
>>80341911
Do you know what the stack is?
>>
>>80341731
>Personally I don't really use linked lists in C, because seeking to the point of the list just to get a certain node's data is inefficient. So I use my own vector implementation so I can use it like a resizable array with direct insertion and deletion.
Moving data around on every insert/delete, invalidating pointers to elements, and calling realloc() is not exactly free. If you don't need the random access a linked list may be more efficient, not less.

>>80341759
VLAs are basically abandonware at this point, and tend to conflict with runtime stack-checking and static analysis. I would avoid them unless you're working on embedded or kernel stuff where you can't rely on or don't have a malloc equivalent.

>>80341911
>No, it's not that simple. Arrays are ALWAYS on the stack
An array is just a sequence of items of (usually) the same type. Being resizable or not, residing on the stack or heap, is irrelevant. Some languages have "static" and "dynamic" arrays and terms like "vector" are reserved for mathematical types. The C family does not define programming.
>>
For queues I normally use this. Guess you could use an array though. They're easier to work with that arrays or vectors for some problems.
>>
>>80341984
Arrays are *always* pointers in c. Brackets are just a convenient way of dereferencing

a[5]=6;
And
(*(a+sizeof(int)*5))=6;
Are functionally identical. Try it yourself.
>>
I was under the impression that lists in most programming languages were just linked lists?
>>
>>80340743
>Do any of you actually use linked lists?
All the time, they're probably the most common "datastructure" if stretching that term hard.
>>
>>80342036
More typically lists are arrays with some abstraction to make them seem more dynamic than they are. Linked lists typically have hidden costs that they don’t teach in your intro class that have to do with the cacheing structure of your machine and the minimum dynamically allocatable block.
>>
>>80342030
No, you fucking retard. Arrays are a completely separate C-language construct as specified in the standard. They are also implicitly convertible to pointers so that you can do
foo a[5];
foo* b = a;

without the compiler telling you to go suck a bag of dicks. It doesn't matter what the underlying operations are in this context. An array is an array and a pointer is a pointer.
>>
>>80340891
what's life like post-op anon?
>>
>>80342066
use the language for more than a week you fucking retard, the only difference between
int a[5];

and
in a=malloc(sizeof(int)*5);

is that the malloc version is on the heap, they're both arrays.
>>
You need them for binary trees. Never used either of them except for the time I took the algorithms and data structure class in uni
>>
>>80342036
They're usually linked lists. Some of the languages that struggle with memory and performance provide alternatives based on arrays like Java's ArrayList.
>>
>>80341970
I meant explicitly declared arrays, because >>80341759 was implying the fact you could declare them with variable lengths meant they were somehow equally flexible as lists.
>>
>>80342066
They’re the same type bub. If what you were saying was true and one was on the stack and the other was on the heap, then assigning b to a in your example would require an expensive copy. In fact it does not. Because they both type foo*, so you’re only copying your machine’s native pointer size. And moreover, they’re both referencing the same block of memory after you copy the pointer. (Ie the copy is shallow)
>>
>>80342086
I've been using C for longer than you have been alive you little shit. You have never read a single page of the standard and you are embarrassing yourself.
>>
>>80342117
you're both embarrassing yourselves, sperging out about semantics
>>
>>80342112
Nice way to miss the point of the post, nigger. God I fucking hate zoomer shitters.
>>
>>80342066
Arrays are always pointers but pointers are not always arrays
>>
>>80342141
>made two contradictory impossible statements about the language
>missing the point
Kek lrn2code
>>
>>80342066
They're the same and this concept has an entire chapter (chapter 5) dedicated to itself in K&R
>>
>>80342144
> Arrays are always pointers but pointers are not always arrays
In C they kinda are because their memory model is built on arrays. So any time you’ve got a pointer you can always buffer overrun it using the bracket operator. (It is why C has such poor security)
>>
>>80342165
Almost the same. Unlike pointers arrays can't be reassigned to point to something else.
>>
>>80342184
Well yeah that's what I meant. Arrays have guaranteed allocated memory for them in the next address, but any random pointer doesn't and can be accesing illegal memory by being incremented and deref'd with [], therefore it should not be treated like an array and use []
>>
>>80342213
*unless it's an array on the stack or vector on the heap
>>
>>80342213
Any array can be accessing illegal memory too. Character strings are notorious for this
>>
>>80342227
No what I mean is you can't expect any pointer to have allocated memory in front of it
>>
>>80342218
Vector is a c++ class. When you heap allocate an array. It is still just an array. Fwiw you should very rarely put an array on the stack as you’ll easily smash your stack doing that
>>
>>80340743
Theyre quite nice for their simplicity and ease to grow dynamically - but a brainlet like you need not worry about that
>>
>>80342243
Yeah but the stack is way faster than the heap so it has it's advantages for small shit, if it's something huge then chances are it's something used frequently in the program in which case any sane programmer would have it as persistent data on the heap
>>
>>80340743
they are very useful in functional programming. defining combinators using recursion on lists is very natural.
>>
>>80342243
It's probably far worse to have them on the heap today assuming you're not allocating every single buffer separately as an attacker will have more access to state.
>>
>>80340866
An array list uses a linked list. An array in its most basic form is just contiguous memory.
>>
>>80342354
>An array list uses a linked list.
???
>>
>>80340743
its very helpful. you should try to learn what you can do with it before trying to mastering/understanding/practicing.
>>
>>80342354
Do you mean a linear *dynamic* array?
>>
>>80342301
It is actually pretty rare to have functions that are compute heavy but not memory intensive. (At least compute heavy to the point that you need to optimize a c program)
>>
>>80342117
>I've been using C for longer than you have been alive you little shit
>still doesn't think pointers are arrays
either you're larping (100% chance) or you have a learning disorder
>>
>>80342471
Pointers aren't arrays. They're references to memory. You can represent an array using a pointer to it's first element, but that's not the same thing.
>>
ITT: Babby programmers trying to find their way out of Dunning-Kruger valley. Holy shit this place is crammed full of retards with zero actual experience.
>>
Can't you just malloc to have an array on the heap? And resizing is just realloc, and if it fails then malloc + memcopy.
>>
>>80340743
>are they even used
Depends on the language you use and what exactly you're doing. Most high level (modern) languages have dynamic size arrays so lists don't have to be used as "an alternative to arrays" and you'll never see them used in such a way.
>>
>>80342518

>Pointers aren't arrays. They're references to memory.

Arrays are just references to memory, anon
>>
>>80342604
No, an array is a particular usage of memory.
A collection of wood and nails isn't a house. People aren't piles of meat.
>>
>>80342621
>an array is a particular usage of memory
A pointer is a particular usage of memory
>>
>>80341671
>They’re better in the sense that they have cheaper insertions.
Insertion and removal. That's the point that most of this Thread mises.
>>80340743
>Are they even used for anything practical?
A good example is distributing units of work to a threadpool, where concepts like work stealing can get really expensive (to the point that it's not even worth it and you're better off just letting some threads idle) with large arrays.
>>
>>80342754
>Insertion and removal
>remowal
?
You still need to traverse the list to remove an element
>>
>>80342764
>You still need to traverse the list to remove an element
For insertion/removal in the middle of the list, yes. When dispatching to i.e. a pool of worker threads, 99% of the time you'll insert on one end and remove from the other end. With lists, that means updating 2-3 values - depending on the type of list (single- or double-linked). With arrays, one of those two operations requires shifting every single element by one position.
>>
>>80342940
>99% of the time you'll insert on one end and remove from the other end
Thats assuming what people will do with it. Thats not how it works
>>
>>80342940
If you’re only inserting and removing at the ends you can use a ring buffer for O(1) performance
>>
>>80340743
>It seems to be a bullshit learning exercise
You shouldn't have this attitude mate it isn't going to help you at all.
>>
>>80342161
what level of sperg do you have to be in order for both of you to continue this conversation
>>
>>80342956
Even if your use case involves insertion/removal in the middle, it's still updating a few pointers vs. shifting the position of all elements after the spot. Traversion is usually pretty cheap in comparison, as it's read-only.
>>80342958
If you don't need the option to insert/remove in the middle and can live with a constant size (i.e. blocking insertion until a spot is available), then yes - a ring buffer will perform even better.
>>
>>80343097
>cheap in comparison, as it's read-only
Your intuition about performance is wrong. Reading is slower than writing, because reading blocks. Writing can be deferred. And random access is slower than sequential access.

Both operations are O(n) - in the linked list, you need to iterate the list, and in the array you need to shift elements. But the array will be faster by a constant factor because it's sequential instead of random access.
>>
>>80343097
>If you don't need the option to insert/remove in the middle
A ring buffer will still be faster even with insertion in the middle.
Copying n sequential values is vastly quicker than following n randomly scattered pointers.
>>
>>80343148
>Reading is slower than writing, because reading blocks. Writing can be deferred.
Writing involves some type of memory barrier, unless you're in a single-threaded environment. Which you shouldn't be if you care about performance, as it's $current_year and even low-end hardware is 4t or more.
>>
File: 1611537078287.jpg (34 KB, 682x263)
34 KB
34 KB JPG
>>80340845
>I was just told it was an alternative to an array
they are capable of the same things, but investigate their time complexities. if they aren't teaching you that, jfc the zoomer controlled future is bleak
>>
File: pure_pythonV3.png (16 KB, 743x356)
16 KB
16 KB PNG
>>80340743
use python/perl and forgot all this shit
a internet browser for 17 lines
https://gitlab.com/SSS8555/python_g6_client
>>
>>80342030
look up array decay
>>
>>80343683
this kills the brainlet
>>
imagine using pajeet lists instead of vectors
>>
File: 1591400502642.jpg (127 KB, 640x680)
127 KB
127 KB JPG
>this thread
>>
I've programmed professionally for 5 years and have never used a linked list once. It's a cute learning exercise though.
>>
>>80341695
No, it was a problem that came up recently at my job.
>>
>>80341911
In C, arrays declared outside of main are in the heap. Arrays declared inside main are on the stack. And if you use malloc its in the heap.
>>
>>80340743
newby question
why would you use a linked list over an array?
>>
>>80345077

Strings in many languages.
>>
>>80345077
This is true in C but not in other languages with dynamic array sizes
>Cheap and easy to extend
>Not a fixed size
>Can be modified to be more feature rich (see single vs double vs circular linked lists)
>>
>>80342086
sizeoff(arr) will give you the actual memory usage of the array, but sizeof(ptr) will just give you the size of the pointer. They are very similar but not the same.
>>
>>80345077
Big structs can be handled faster via linked lists, since you don't have to move the memory to sort the list.
>>
>>80345117
you forgot
>dogshit iteration performance
>>80345736
>array of pointers
>???
>profit
>>
>>80340891
Any hash map that stores multiple values to one key is using a linked/doubly linked list.
>>
Sometimes I feel bad about how much I’m progressing on my degree then I read threads like this and remember that /g/ is full of self taught retards who don’t understand basic concepts and feel better about myself
>>
>>80345992
A lot of them will use an array. For example if your hashes have a range of 256, you can allocate an N*256 array, to give you N space in each bucket.
>>
>>80340743
No they're useless in all cases.
>>
>>80340743
There's always a better option than a linked list.
>>
>>80341406
> he doesn't make his own faster implementation
look at this retard
>>
>>80340743
>Do any of you actually use linked lists?
No but it's a good way to learn about pointers/references.
>>
>>80345077
You often see them in metadata, for example scatter-gather DMA headers. In that case you’re building a dynamic data structure that needs to be connected flexibly and you’re not concerned with the performance of your list traversal.
>>
>>80345992
Not always. Pooling can be done with arrays. Just the only problem is if one of the pools fill up you have to rehash. Linked list pooling doesn’t have this problem but slightly slower because you get cache misses. If you are pretty confident you won’t fill up pools then array is fine
>>
>>80346194
*Another example is the PCIe extended capability space. It has a linked list for storing device capability and configuration structures
>>
>this thread
when will /g/ stop being retarded?
>>
>>80340743
Linked lists CAN be faster than whatever your language standard library offers you, but only in small hobby projects. They're also useful when used as a ring buffer on very low level.

In most cases you won't have any benifit cause the List your language offers you include hard-to-implement features like preallocating, indexing and garbage collection and all kinds of heuristic algorithms that make access faster
>>
>>80346142
That's not true, what if my goal was to create a discontinuous block of related pieces of memory linked together with pointers that has worse performance as it grows??
>>
Why are you guys dissing linked lists so bad?

It's not useless.

>The inode (index node) is a data structure in a Unix-style file system that describes a file-system object such as a file or a directory. Each inode stores the attributes and disk block locations of the object's data. File-system object attributes may include metadata (times of last change, access, modification), as well as owner and permission data.
>>
>>80342377
lurk/study more
>>
>>80346309
They are retarded. They think it’s faster because you don’t get cache misses but instead you run into issues of reallocations bringing your whole computer to a halt.
>>
>>80346309

Still, if you're working with a garbage collected language or a language that offers a standard library, you should prefer using that instead of programming your own
>>
>>80346330
Obviously this is true but this doesn’t make linked list bad or worthless. Just means you should use built in data structures when they are available
>>
Data structures are pointless, who needs variables anyways, constants are a constant waste of time, sequential circuits were a mistake, combinational circuits are useless, who needs to know how to process math problems, addition is pointless, who needs numbers anyways!
>>
>>80346330
If you are working on embedded system, lists are your friends.
>>
>>80346395
If you are using linked list in an embedded system you are dumb as fuck. What circle of hell are you in if you are writing embedded code that has dynamic memory. Horrible practice.
>>
>>80346395
If you're working on embedded systems, chances are Wind River or whatever you're building on already offers you a great list implementation
>>
>>80346440
>>80346395
Please don’t use dynamic memory in embedded systems.
>>
>>80346472
You don't even need dynamic memory, the adequate library will map the RAM you need and just give you an abstraction that feels like dynamic memory
>>
>>80346534
If you are doing this you don’t need a linked list then. You would just be using an array with some abstraction layer. You are writing an embedded systems it should be 100% deterministic.
>>
Looks like I got outted as an embedded retard
>>
>>80346558
> You are writing an embedded systems it should be 100% deterministic.
Interrupts are unavoidable
>>
>>80346584
Interrupts are deterministic. You can calculate the max memory allocation from pushing shit on the stack and the max time delay caused by interrupts stacking on top of each other pretty easily so you won’t miss any deadlines on your system. So you could find out what’s the worst case scenario for memory allocation and “latency”. If you have dynamic memory this is not possible or is way more difficult.
>>
>>80346656
Where can I learn about this so I don't embarrass myself next time
>>
>>80346656
>Interrupts are deterministic
Lol no. That is definitionally the opposite of true. They’re manageable but not deterministic. And fwiw dynamic memory allocation is far more predictable
>>
>>80346703
Calculating the worst case for dynamic memory is impossible. IF IT IS then you wouldn’t be dynamically allocating shit and just allocate the worst case amount of memory you will need to allocate statically. It makes 0 sense to dynamically allocate memory in an embedded system.
>>
>>80340743
>Learning about linked lists/doubly linked lists in a course. It seems to be a bullshit learning exercise. Do any of you actually use linked lists? Are they even used for anything practical?
Do not try to consider "linked list" as some kind of specific structure, it's an abstraction to a container that can do few things - element can be added/removed/modified anywhere without moving too much stuff around, and can be traversed in either direction but indexing without additional supporting structure is impossible.
Examples are multiple and plentiful. Just try to start from the problem you want to solve not from algorithm name. For example try to find efficient way of keeping a list of tasks to do.
>>
>>80342377
this retard is talking about implementation details of java arraylist and linkedlist
he probably thinks it's the general rule for arrays and lists
>>80346314
java is not the only language in existence, you should lurk/study more
>>
>>80346703
And yes interrupts are deterministic if you don’t miss use them. they take a deterministic amount of time do shit and deterministic amount of memory. So it’s true they aren’t 100% deterministic probably by the textbook definition but they are deterministic in the sense of what actually matters ie finding out you won’t run out of memory and finding out you won’t miss deadlines.
>>
>>80346731
It is similar to interrupts in the sense that both contain an overflow case. You can have more interrupts than your stack pointer can accommodate or more dynamic memory. They can both be mitigated, but not eliminated, as risks by good design

>>80346668
What he’s talking about is highly hardware dependent and only doable in principle in simple systems like babby’s first arduino project. High reliability systems use TDM because interrupt driven systems are not fully verifiable in principle
>>
>>80346805
You can easily calculate the amount of memory worst case for all your interrupts stacking and worst case in the code. Find worst case what function has the most shit on the stack and with all your interrupts stacking on each other this is super easy to do. There are tools to do this.
>>
>>80346851
Babby’s first arduino project
>>
>>80346851
So in fact you can 100% verify you will never run out of memory.
>>
>>80346904
You are retarded. If you think you can’t verify and can calculate the max memory usage of your embedded system you are so retarded no one can help you.
>>
>>80346931
I suspect you’ve never worked with an embedded system of any complexity. (How do you fully verify a system with a legacy pcie controller? Where a galaxy of different hardware may be added in different slots. Have you even considered how meta stability or thermals can affect the timing analysis of a high performance system.) And never in the real world. (Where you rarely have complete control over the design of your system. Even if you’re the system architect of a newly developed system, your use case will probably involve some crappy standards that hamstring you)
>>
>>80347064
>what if your system takes a bunch of random shit and I’m running an OS that handles shit
you aren’t really writing an embedded system then. It’s a pesudo embedded system. Your constraints aren’t probably that bad. Your probably have globs of memory and don’t have to worry about it unless you are doing crazy shit. Your OS probably uses dynamic memory too so it’s impossible to calculate the max usage. Plus if your run out memory it doesn’t matter because you can just reboot.
>thermals
may cause some variability data sheet will tell you worst case clock speed. If your time constraints are so slim that slight variations in clock speed from temp can fuck with you something is really wrong. Plus if you use an external clock these will be even slimmer
I work at Lockheed and we calculate the max memory usage of our system and verify it. The systems we write aren’t simple.
>>
>>80347243
>I work at Lockheed
Lol. Lockheed and the other dod contractors are still using 80s/90s tech. No wonder your instincts are so off base.
t. Former Northrop Grumman R&D, left for big tech

> If your time constraints are so slim that slight variations in clock speed from temp can fuck with you something is really wrong
Or you’re working in a cutting edge system and trying to push the performance envelope
>>
>>80340792
When will I ever make an OS or a programming language?
>>
>>80340743
No, they are bad for caching. I use std::vector, std::map and std::set for everything. Implementing your own containers and sorting algorithms is a meme and something you will never need outside a CS degree. 99% of the time the std lib is the way to go.
>>
>>80346763
>java is not the only language
Java also doesn't call LinkedLists as ArrayLists. ArrayLists are dynamic arrays with amortized insertion costs. It's not a LinkedLists.
>>
>>80340743
There are some _very_ niche cases where linked lists are preferable. Contiguous memory is strongly preferable in all other cases.
>>
>>80348788
I know, this is what I'm talking about
the dude is mixing everything up and act like lists are always arrays or soe shit
>>
Theyre actually bad to use unless you have a very specific use case. You're almost always better off with a dynamic array/std::vector

https://youtube.com/watch?v=YQs6IC-vgmo
>>
File: arrayofnumberswojak.jpg (237 KB, 1000x2349)
237 KB
237 KB JPG
>>80348983
>the dude is mixing everything up and act like lists are always arrays or soe shit
Everything is an array. :^)
>>
>>80340743
Text editors often use linked lists. The text buffer is stored as a linked list of structures that contain a pointer to a heap-allocated string, the number of allocated bytes, and the number of bytes used, and maybe the line number. When you insert a new line, you don't want to have to copy the entire text buffer, you just want to modify the "previous" and "next" pointers of the current and next line. This makes inserting lines O(1) instead of O(n)
>>
File: 1614076070480.png (170 KB, 600x600)
170 KB
170 KB PNG
>>80340891
using System.Collections.Generic;

public class LinkedList<T>
{
private readonly Dictionary<ulong, T> _dictionary = new();

private ulong index = 0;

public void Add(T value)
{
_dictionary[index++] = value;
}
}


Am I doing it right?
>>
>>80349037
4chan replies are a linked list. Prove me wrong. Protip: you can’t
>>
>>80349245
it's a fixed-size id followed by a fixed-size length and then characters represented by numbers, so it quite literally is just an array of numbers
>>
>>80349312
>fixed-size id
You mean a pointer?

> followed by a fixed-size length and then characters represented by numbers
You mean a struct/record?
>>
>>80349362
>You mean a pointer?
Yes, an offset in memory which coincidentally also is just an array of numbers.

>You mean a struct/record?
You mean named offsets?
>>
>>80349396
>a struct with a pointer to a subsequent element is not a linked list
Don’t mind me. I’m just adding another link to this list.

FWIW, at the level of abstraction of something like 4chan, data is cloud stored and split between multiple processors / hard drives. There is not necessarily a contiguous region of memory at any level of abstraction.



Delete Post: [File Only] Style:
[Disable Mobile View / Use Desktop Site]

[Enable Mobile View / Use Mobile Site]

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.