DEPRECATED Linked List for Godot -- see link below

README.md

WARNING ⚠️ Deprecated. Use https://gist.github.com/belzecue/6253c8c694d602e715fff0b3f4303344/ instead.

Old usage sample:

const LinkedList = preload("LinkedList.gd")

func _ready():
  var ll = LinkedList.new()
	ll.push_back(-1)
	ll.push_back(5)
	ll.push_front(1)
	ll.push_front(2)
	print(ll.size()) # 4
	print(ll.pop_best(funcref(self, "comp"))) # 5
	print(ll.pop_back()) # -1
	print(ll.pop_front()) # 2
	print(ll.size()) # 1

func comp(a,b):
	return a > b

</details>

LinkedList.gd

##
## WARNING: Deprecated. Use https://gist.github.com/belzecue/6253c8c694d602e715fff0b3f4303344/ instead.
##

extends Reference

class LinkedListItem:
	extends Reference
	
	var next = null
	var previous = null
	var data = {}
	
	func _init(v):
		data = v
	
	func link(other):
		other.previous = self
		next = other
	
	func unlink():
		var _next = next
		var _previous = previous
		if _previous:
			_previous.next = next
		if _next:
			_next.previous = previous

var _tail = null
var _head = _tail
var _len = 0

func size():
	return _len

func push_back(val):
	if _len == 0:
		_head = LinkedListItem.new(val)
		_tail = _head
	else:
		var new_head = LinkedListItem.new(val)
		_head.link(new_head)
		_head = new_head
	_len += 1

func push_front(val):
	if _len == 0:
		_head = LinkedListItem.new(val)
		_tail = _head
	else:
		var new_tail = LinkedListItem.new(val)
		new_tail.link(_tail)
		_tail = new_tail
	_len += 1

func pop_back():
	if _len == 0:
		return null
	else:
		var result = _head.data
		_head = _head.previous
		_len -= 1
		return result

func pop_front():
	if _len == 0:
		return null
	else:
		var result = _tail.data
		_tail = _tail.next
		_len -= 1
		return result

func pop_best(better_func):
	if _len == 0:
		return null
	else:
		var current_best = _tail
		var next = _tail.next
		while next:
			if not better_func.call_func(current_best.data, next.data):
				current_best = next
			next = next.next
		if _head == current_best:
			return pop_back()
		if _tail == current_best:
			return pop_front()
		else:
			current_best.unlink()
			return current_best.data
			
##
## WARNING: Deprecated. Use https://gist.github.com/belzecue/6253c8c694d602e715fff0b3f4303344/ instead.
##

Small error in your example, in the commented results. You've got:

print(ll.pop_back()) # -1
print(ll.pop_front()) # 1
print(ll.size()) # 1

but the results are actually:

print(ll.pop_back()) # -1
print(ll.pop_front()) # 2
print(ll.size()) # 1

@belzecue O, you are actually correct. Fixed!

Do note that I wrote that piece of code a loong time ago, and I'm not sure I can vouch for its being bug-free, stable, or performant 😅 For one, LinkedListItem is very likely leaking memory through reference cycles right now.

isn't the push_back and push_front logic when linking the new item inverted?

var new_tail = LinkedListItem.new(val)
new_tail.link(_tail)
_tail = new_tail

and

var new_head = LinkedListItem.new(val)
_head.link(new_head)
_head = new_head

Shouldn't it be _tail.link(new_tail) and new_head.link(_head)?

@Ranpu123 I think you are right, the head/tail naming is reversed, but it does not effect the behaviour of the list. The code is actually doing the right thing as is. You can test that the current code is working correctly re head and tail with this:

func _ready():
	var my_list: LinkedList = LinkedList.new()
	my_list.push_front("head")
	my_list.push_back("middle") # <-- comment out one of these to test
	# my_list.push_front("middle") # <-- comment out one of these to test
	my_list.push_back("tail")
	print("list length: ", my_list._len)
	print("first item: ", my_list.pop_front())
	print("last item: ", my_list.pop_back())

The output is as expected:

list length: 3
first item: head
last item: tail

Swapping the commented line, to deliberately add the "middle" item to the front of the list instead also gives the expected result:

func _ready():
	var my_list: LinkedList = LinkedList.new()
	my_list.push_front("head")
	# my_list.push_back("middle") # <-- comment out one of these to test
	my_list.push_front("middle") # <-- comment out one of these to test
	my_list.push_back("tail")
	print("list length: ", my_list._len)
	print("first item: ", my_list.pop_front())
	print("last item: ", my_list.pop_back())

list length: 3
first item: middle
last item: tail

For the sake of making the code read correctly, to remove this understandable confusion with the naming, you can simply swap the naming of _head and _tail in the code. Do a CTL+H replace three times as follows:

_head -> _~tail
_tail -> _head
_~tail -> tail

and now the code will read correctly.

@belzecue Hmm.. would you like to take over maintaining this snippet of code? I can't really give you edit rights or transfer it, but if you have your own version, either as a Gist or as a repo, I'd be willing to slap a big "Deprecated" warning on top and link people to yours (:

No worries, happy to maintain a fork (which includes the swapped code mentioned in my prior comment).

https://gist.github.com/belzecue/6253c8c694d602e715fff0b3f4303344/

Alrighty, thanks! 😊 Updated the readme and script to link to your gist (: -- you might want to change the first few lines of your LinkedList.gd to reflect that too.