If I understand correctly, TLinkedList performs way better when you don’t need the index and if it’s size changes. Especially if you have a large array and do this many times per frame (AI or something). But TLinkedList cannot even be marked as UPROPERTY and thus anything that uses this TLinkedList also cannot be marked either:
// This is a container-hack to circumvent UE4's limitation for TMap's: "Nested containers are not supported".
USTRUCT()
struct FMyStruct
{
GENERATED_USTRUCT_BODY()
// No UPROPERTY because it's not supported by UE4.
TLinkedList<MyAwesomeType> Values;
};
// In a header in a galaxy far far away:
TMap<FText, FMyStruct> Foo; // <<< this also cannot be marked as UPROPERTY because of the TLinkedList.
According to: A list vs TArray - Programming & Scripting - Unreal Engine Forums TArray “isn’t too bad” (a performance chart would be better to really compare stuff) but is that really a reason to not use LinkedLists? Just because of lack of support from Epic for it? Why isn’t it fully supported by now? Are we really supposed to use the ‘inferior’ TArray for this when we don’t need an index setter/getter and when we know it will have many elements added&removed every tick? Shouldn’t we always be using TLinkedList instead the moment we don’t need the index? Because really, most of the time I don’t need the index anyway.
I must be thinking completely wrong because otherwise this would have been added a long time ago so why are TArrays better?
A linked list simply is a pointer to the next element in the list. You don’t need to use a TLinkedList to do that. Instead, with MyAwesomeType, you can just store another pointer to the next MyAwesomeType
struct MyAwesomeType
{
int MyAwesomeData;
UPROPERTY()
MyAwesomeType* Next;
}
And then to access the linked list, you just get the head of the linked list and do traversal or whatever you want to do with it.
As for why linked list is faster than arrays, arrays is better for random access on any index of the array. Linked list is better if you just want to append to the list, or just delete the 1st/last elem from the list most times (instead of deleting/inserting in the middle). This is because you always cache the head or tail of the list.
Yes I understand that. Yes I know I could make my own linked list type but I really expected not to have to do that for UE4 in 2017, which would be a pain anyway because you probably will have to work with templates and create custom iterators and sorting and etc. No thanks.
LinkedList is better when you don’t need the index in any way and whenever you add/remove items to/from it all the time. But for me personally, this is like 8 out of 10 times!
Most of the time I don’t need the random access on any index. Most of the time I just need to store a bunch of enemies, players, projectiles, jobs, etc, together. For example I keep a list of all player units for the GUI. But I will never ever need to to use the index for this. So it should be a LinkedList right?
So after thinking about it, 8 out of 10 of my arrays should be linked lists. They have items added/removed all the time but they never get accessed by index. I guess this would apply to most UE4 developers. So why is the TArray ‘preferred’ by Epic? Or is it simply because:
TArray can do what a TLinkedList can and more (indexer).
TArray doesn’t perform as well as a TLinkedList but nobody cares?
TLinkedList is the '‘more correct’ implementation most of the time, but nobody cares?
TArray is more non-programmer-friendly because some/most blueprint users can’t program and linked lists would be too complicated?
TArray and TLinkedList can both be looped, sorted, etc. so they can often both be used interchangeably, but TLinkedList often performs better.
The ‘more correct’ implementation in most cases would be to use a TLinkedList instead of a TArray and it also performs better in those cases. So I don’t understand why support was given for TArray but not for TLinkedList even though that is the one we (I think) should be using most of the time?
The only reason I’m using TArrays in most cases is purely because of UE4 compatibility (or it’s lack thereof). But I rather not.
Linked list is for adding/removing elements at the front or back or the list, which would take O(1). Adding/Removing from the middle of the list still would take the size of the list O(n). Epic’s TArray also has pop and push methods which almost work like Stacks, which basically also allow you to remove/add from ends of the Array easily as well. I bet the implementation for pop and push probably is also O(1).
You will know when to use a linked list and when to use an array by intuition. You use a linked list when for each enemy, you only need to access or do something about the “next” enemy or “previous” enemy. For example, for my case I needed a linked list for a group of enemies that are moving in a line formation. When the enemy ahead of this enemy is moving in a certain direction, the current enemy also moves in a certain direction. For any enemy, I never cared about all the enemies in the linked list. I only cared about the enemy ahead or behind of it. This is a great opportunity to use linked lists. (You can also use TArray to do this, but Linked lists obviously fits better)
As a rule of thumb, you should almost always use TArrays, unless you have specific reasons to use LinkedLists, like the one I just mentioned.