Rename `List` -> `LinkedList`, with a `List` alias pointing to `LinkedList`.

[Ivorforce]

The reason is that List is ambiguous. In most languages, it refers to sequences of undefined backing — either as an abstract class, like Java, or as a concrete type with encapsulated backing, like Python or C# (although all major implementations use array backings). The only languages where List is inherently linked are functional languages, which don't support the concept of contiguous arrays (although interestingly, some implementations still optimize by using array backings where possible).

In instances where a linked list is needed, it would be advisable to use LinkedList explicitly. In instances where the backing is unimportant, or not known which performs best, continuing to use List would be OK. Maintainers should be able to decide which is the most efficient backing type for these instances. Classes like Vector, LocalVector and others are already fairly close in interface to List / LinkedList, so it is realistic that this could be done at some point if wanted.

[Ivorforce]

Unfortunately, git does not have a concept of a rename. I have not touched any code in linked_list.h, except for renaming it, but the code change appears big because list.h was added in its stead. Here is the actual diff:

gh pr checkout 100323
git diff HEAD~:core/templates/list.h HEAD:core/templates/linked_list.h

similarity index 97%
rename from core/templates/list.h
rename to core/templates/linked_list.h
index 02afeec74d..13d5e4908b 100644
--- a/core/templates/list.h
+++ b/core/templates/linked_list.h
@@ -1,5 +1,5 @@
 /**************************************************************************/
-/*  list.h                                                                */
+/*  linked_list.h                                                         */
 /**************************************************************************/
 /*                         This file is part of:                          */
 /*                             GODOT ENGINE                               */
@@ -28,8 +28,8 @@
 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                 */
 /**************************************************************************/
 
-#ifndef LIST_H
-#define LIST_H
+#ifndef LINKED_LIST_H
+#define LINKED_LIST_H
 
 #include "core/error/error_macros.h"
 #include "core/os/memory.h"
@@ -44,13 +44,13 @@
  */
 
 template <typename T, typename A = DefaultAllocator>
-class List {
+class LinkedList {
 	struct _Data;
 
 public:
 	class Element {
 	private:
-		friend class List<T, A>;
+		friend class LinkedList<T, A>;
 
 		T value;
 		Element *next_ptr = nullptr;
@@ -132,7 +132,7 @@ public:
 			data->erase(this);
 		}
 
-		void transfer_to_back(List<T, A> *p_dst_list);
+		void transfer_to_back(LinkedList<T, A> *p_dst_list);
 
 		_FORCE_INLINE_ Element() {}
 	};
@@ -514,7 +514,7 @@ public:
 	/**
 	 * copy the list
 	 */
-	void operator=(const List &p_list) {
+	void operator=(const LinkedList &p_list) {
 		clear();
 		const Element *it = p_list.front();
 		while (it) {
@@ -753,7 +753,7 @@ public:
 	/**
 	 * copy constructor for the list
 	 */
-	List(const List &p_list) {
+	LinkedList(const LinkedList &p_list) {
 		const Element *it = p_list.front();
 		while (it) {
 			push_back(it->get());
@@ -761,9 +761,9 @@ public:
 		}
 	}
 
-	List() {}
+	LinkedList() {}
 
-	~List() {
+	~LinkedList() {
 		clear();
 		if (_data) {
 			ERR_FAIL_COND(_data->size_cache);
@@ -773,7 +773,7 @@ public:
 };
 
 template <typename T, typename A>
-void List<T, A>::Element::transfer_to_back(List<T, A> *p_dst_list) {
+void LinkedList<T, A>::Element::transfer_to_back(LinkedList<T, A> *p_dst_list) {
 	// Detach from current.
 
 	if (data->first == this) {
@@ -809,4 +809,4 @@ void List<T, A>::Element::transfer_to_back(List<T, A> *p_dst_list) {
 	p_dst_list->_data->size_cache++;
 }
 
-#endif // LIST_H
+#endif // LINKED_LIST_H

[RandomShaper]

I had considered this myself. If the type has a more specific name, 'linked list', it's less likely that it will be used unless the maintainer is aware of the implications. Regarding how to introduce the change, I'm a bit worried this may break compatibility with modules or GDExtensions. Maybe we could do the following:

• Rename to LinkedList, but keep list.h.
• Still alias LinkedList as List.
• Mark List somehow as deprecated, noting that in the future (Godot 5, maybe?) the include will be linked_list.h and List won't be available anymore.

[Ivorforce]

Regarding how to introduce the change, I'm a bit worried this may break compatibility with modules or GDExtensions.

I think it won't cause issues the way i have it, but I'd be totally cool with your suggestion too.

[hpvb]

This does feel a little bit "code churney" I think this would really only be appropriate if we actually had a List that is maybe more like a Python list or something explicitly, but we have LocalVector instead. Given that this is C++, and there a List is in fact generally speaking a linked list and a Java/Python/whatever List is an Array or Vector, I actually don't think that in the context of the Godot codebase any confusion really exists.

I don't think that this is a useful thing to do, personally.

[Ivorforce]

I think this would really only be appropriate if we actually had a List that is maybe more like a Python list or something explicitly, but we have LocalVector instead. Given that this is C++, and there a List is in fact generally speaking a linked list

I don't think that's true - as explained above, I think List is a term generally agnostic to the underlying storage strategy. I don't think I've ever seen a List refer to linked lists before, neither in code nor in texts, especially since they're a dying breed. (Edit: You're right on c++ though, apparently std::list is usually a linked list. That doesn't change my overall opinion on this matter, but it does change the implications somewhat).

I actually don't think that in the context of the Godot codebase any confusion really exists.

I disagree. I think the fact that a word-search for List yields nearly 5000 entries, while one for LocalVector yields only 900, is enough evidence to warrant a rename. I think people employ the List type because they think it is the go-to default for ordered sequences. Given the background that in nearly all cases, linear buffers (i.e. LocalVector) are superior to linked lists (i.e. List) because linked lists don't play well with modern CPU caches, leading to decreased performance, this is a misjudgement. Renaming List to LinkedList would help alleviate this problem in the future.

[hpvb]

@Ivorforce I see what you are saying, but I really don't think it is a problem. This is a NAK for me. But I'm not the only decidor :)

[akien-mga]

I disagree. I think the fact that a word-search for List yields nearly 5000 entries, while one for LocalVector yields only 900, is enough evidence to warrant a rename. I think people employ the List type because they think it is the go-to default for ordered sequences.

This is for legacy reasons.

LocalVector was introduced quite recently in the codebase, and we're still in the progress of migrating usage away from List (which used to be the go-to for this) with LocalVector.

So the numbers you mention don't necessarily illustrate that people still use List when they shouldn't, but simply that there's a lot of legacy code that's being ported little by little, where it makes sense.

More so than renaming templates, I think having a clear documentation page that explains what each template is for and when to use it and when not to, with examples, would help a ton with ensure the quality of the codebase going forward.

[Ivorforce]

Alright, i confess this PR is just too forward, especially with the concerns and other arguments that have been brought up. If there's still interest in the change, a proposal should be created first instead (i should definitely have done that in the first place, lol, apologies).