Doubly Linked List for Godot

README.md

Use it like:

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

LinkedList.gd

# Linked List
# from https://gist.github.com/bojidar-bg/a570c614a4dd1cd84949

# Example use
"""

var my_linked_list = LinkedList.new()

func _ready():
	var ll = my_linked_list
	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
	print(ll.pop_front()) # 1
	print(ll.size()) # 0
	

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

"""

class_name LinkedList extends Reference

class LinkedListItem:
	extends Reference
	
	var head: LinkedListItem = null
	var tail: LinkedListItem = null
	var data = null
	
	func _init(v):
		data = v
	
	func link_to(other: LinkedListItem):
		other.tail = self
		head = other
	
	func unlink():
		var _next: LinkedListItem = head
		var _previous: LinkedListItem = tail
		if _previous:
			_previous.head = head
		if _next:
			_next.tail = tail


var _head: LinkedListItem = null
var _tail: LinkedListItem = _head
var _len: int = 0


func size() -> int:
	return _len


func push_back(val) -> void:
	if _len == 0:
		_tail = LinkedListItem.new(val)
		_head = _tail
	else:
		var new_tail: LinkedListItem = LinkedListItem.new(val)
		_tail.link_to(new_tail)
		_tail = new_tail
	_len += 1


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


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


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


func pop_best(better_func):
	if _len == 0:
		return null
	else:
		var current_best: LinkedListItem = _head
		var next: LinkedListItem = _head.head
		while next:
			if not better_func.call_func(current_best.data, next.data):
				current_best = next
			next = next.head
		if _tail == current_best:
			return pop_back()
		if _head == current_best:
			return pop_front()
		else:
			current_best.unlink()
			return current_best.data

Hello 👾 your current doubly linked list is rather a stack with extra pointers, within link() you are missing a middle statement saying: other.next = next. Furthermore, it appears that needless memory is wasted holding on to an empty dictionary while waiting for data to be added to an item.

@kostasde, thanks for the feedback.

within link() you are missing a middle statement saying: other.next = next

The property naming is not great in the code, which I think is leading to confusion (like here). I would prefer seeing "head" and "tail" used consistently throughout for clarity and will rewrite it when I get a chance. In those terms, "other.next = next" would be "other.head = head" which is incorrect because we are chaining this item to the other item, i.e. this "head" to other's "tail".

I would prefer seeing "head" and "tail" used consistently throughout for clarity and will rewrite it when I get a chance.

Done.

You're welcome!

i.e. this "head" to other's "tail".

And then just making other the new head, I see, but that's what I mean by it only supporting stacking. I think it worth noting that link doesn't support link()-ing at an arbitrary point in the list. Truly not what you intended to do given the single argument to link, but anywho...