an ArrayList-based linked list for SourcePawn. Intended to be pretty fast compared to a regular linked list. Can be changed so the ArrayLists are arrays.

linkedlist.inc

/**
 * linkedlist.inc
 *
 * Copyright [2021] Nergal the Ashurian aka Kevin Yonan
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction,
 * including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE ANDNONINFRINGEMENT.
 *
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#if defined _linkedlist_included
	#endinput
#endif
#define _linkedlist_included

#include <adt>

enum struct LinkedList {
	ArrayList data;
	ArrayList next;
	ArrayList prev;
	int       head;
	int       tail;
	int       len;
	int       slot;
	
	void Init(int startsize=1, int blocksize=1) {
		this.head = this.tail = -1;
		this.len  = 0;
		this.data = new ArrayList(blocksize, startsize);
		this.next = new ArrayList(_, startsize);
		this.prev = new ArrayList(_, startsize);
		
		int data_len = this.data.Length;
		this.slot = data_len - 1;
		/// initialize the nodes as a free-list first.
		for( int i; i < data_len; i++ ) {
			this.prev.Set(i, i - 1);
			this.next.Set(i, i + 1);
		}
		this.next.Set(data_len-1, -1);
	}
	
	void Destroy() {
		delete this.data;
		delete this.next;
		delete this.prev;
		this.head = this.tail = -1;
		this.len  = this.slot = 0;
	}
	
	int AllocIndex() {
		/// no more free indexes!
		if( this.slot < 0 ) {
			return -1;
		}
		/// pop index from free list.
		int index = this.slot;
		this.slot = this.prev.Get(index);
		if( this.slot >= 0 ) {
			this.next.Set(this.slot, -1);
		}
		return index;
	}
	
	void FreeIndex(int i) {
		if( this.slot < 0 ) {
			this.slot = i;
			this.next.Set(i, -1);
			this.prev.Set(i, -1);
		} else {
			this.prev.Set(i, this.slot);
			this.next.Set(i, -1);
			this.next.Set(this.slot, i);
			this.slot = i;
		}
	}
	
	int PushCell(any data) {
		int i = this.AllocIndex();
		if( i < 0 ) {
			return i;
		}
		
		this.data.Set(i, data);
		if( this.head == -1 ) {
			this.head = this.tail = i;
		} else {
			this.next.Set(i, this.head);
			this.prev.Set(i, -1);
			this.prev.Set(this.head, i);
			this.head = i;
		}
		this.len++;
		return i;
	}
	
	void RemoveNode(int node) {
		if( node < 0 || !this.data.Get(node) ) {
			return;
		}
		
		if( this.prev.Get(node) > -1 ) {
			int p = this.prev.Get(node);
			this.next.Set(p, this.next.Get(node));
		} else {
			this.head = this.next.Get(node);
			if( this.head > -1 ) {
				this.prev.Set(this.head, -1);
			}
		}
		
		if( this.next.Get(node) > -1 ) {
			int n = this.next.Get(node);
			this.prev.Set(n, this.prev.Get(node));
		} else {
			this.tail = this.prev.Get(node);
			if( this.tail > -1 ) {
				this.next.Set(this.tail, -1);
			}
		}
		
		/// delete & add the index back to the free-list.
		this.data.Set(node, 0);
		this.FreeIndex(node);
		this.len--;
	}
	
	any Head() {
		return( this.head >= 0 ) ? this.data.Get(this.head) : 0;
	}
	
	any Tail() {
		return( this.tail >= 0 ) ? this.data.Get(this.tail) : 0;
	}
	
	int NodeCount() {
		return this.len;
	}
	
	int FreeCount() {
		return this.data.Length - this.len;
	}
	
	void InsertCellAfter(int curr, any data) {
		if( curr<0 ) {
			return;
		}
		int insert = this.AllocIndex();
		if( insert<0 ) {
			return;
		}
		this.data.Set(insert, data);
		this.prev.Set(insert, curr);
		if( this.next.Get(curr)==-1 ) {
			this.tail = insert;
		} else {
			this.next.Set(insert, this.next.Get(curr));
			int n = this.next.Get(curr);
			this.prev.Set(n, insert);
		}
		this.next.Set(curr, insert);
	}
	
	void InsertCellBefore(int curr, any data) {
		if( curr < 0 ) {
			return;
		}
		int insert = this.AllocIndex();
		if( insert < 0 ) {
			return;
		}
		this.data.Set(insert, data);
		this.next.Set(insert, curr);
		if( this.prev.Get(curr) == -1 ) {
			this.head = insert;
		} else {
			this.prev.Set(insert, this.prev.Get(curr));
			int p = this.prev.Get(curr);
			this.next.Set(p, insert);
		}
		this.prev.Set(curr, insert);
	}
	
	int FindNode(any data) {
		for( int i=this.head; i >= 0; i = this.next.Get(i) ) {
			if( this.data.Get(i)==data ) {
				return i;
			}
		}
		return -1;
	}
	
	bool RemoveValue(any data) {
		int i = this.FindNode(data);
		if( i < 0 ) {
			return false;
		}
		this.RemoveNode(i);
		return true;
	}
	
	any PopHead() {
		any data = this.Head();
		this.RemoveNode(this.head);
		return data;
	}
	
	any PopTail() {
		any data = this.Tail();
		this.RemoveNode(this.tail);
		return data;
	}
}