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

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

@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 (:

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.