Реализация односвязного списка

Односвязный список – такая структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент (при этом последний элемент списка ссылается на null).

Рассказ об этой структуре данных мы опустим, если у вас появится желание тщательно разобраться в ней, то добро пожаловать в поисковые системы, ну или можете посмотреть, например, тут: реализация односвязного списка на Си.

И сегодня мы реализуем односвязный список на D…

Вот что реализовано в классе нашего односвязного списка (перечислено в порядке следования соответствующих методов класса):

• создание списка (в двух вариантах);
• проверка списка на пустоту;
• получение длины списка;
• получение головы и хвоста списка;
• получение n-ого элемента;
• получение среза (slice) списка;
• добавление элемента в начало списка;
• добавление элемента в конец списка;
• удаление головы списка;
• удаление хвоста списка;
• удаление n-ого элемента;
• клонирование списка;
• расширение одного списка с помощью другого;
• строковое представление списка;
• преобразование в массив;
• преобразование в ассоциативный массив;
• применение функции к именам узлов списка;
• применение функции к значениям списка.

Реализация представлена ниже:

import std.algorithm;
import std.conv;
import std.stdio;
import std.string;

template addProperty(T, string propertyVariableName, string propertyName)
{
	import std.string : format;

	const char[] addProperty = format(
		`
		private %2$s %1$s;
		
		void set%3$s(%2$s %1$s)
		{
		
			this.%1$s = %1$s;
		
		}
		
		%2$s get%3$s()
		{
		
			return %1$s;
		
		}
		`,
		propertyVariableName,
		T.stringof,
		propertyName
	);
}

class Link(T)
{

	mixin(addProperty!(string, "name", "Name"));
	mixin(addProperty!(T, "value", "Value"));
	mixin(addProperty!(Link!T, "next", "Next"));
	
	this(T)(string name, T value)
	{
		this.name = name;
		this.value = value;
	}
	
	override string toString()
	{
		return format("Link(name=%s, value=%s)", name, to!string(value));
	}

}

class LinkedList(T)
{
	private
	{
		Link!T first;
	}

	// создание списка
	static LinkedList!T create(T)(Link!T head)
	{
		LinkedList!T list = new LinkedList!T;
	
		list.addFront(head.getName, head.getValue);
	
		return list;
	}
	
	static LinkedList!T create(T)(Link!T head, Link!T tail)
	{
	
		LinkedList!T list = new LinkedList!T;
	
		list.addFront(head.getName, head.getValue);
	
		list.addBack(tail.getName, tail.getValue);
	
		return list;
	}
	
	this()
	{
		first = null;
	}
	
	// пустой ли список ?
	bool empty()
	{
		return (first is null);
	}

	// длина списка
	size_t length()
	{
	
		size_t lengthOfList = 0;
	
		auto current = first;
	
		while (current !is null)
		{
			lengthOfList++;
	
			current = current.getNext;
		}
	
		return lengthOfList;
	
	}

	// голова списка
	LinkedList!T head()
	{
		LinkedList!T list = new LinkedList!T;
	
		if (first !is null)
		{
			list.addFront(
				first.getName,
				first.getValue
			);
		}
	
		return list;
	}
	
	// хвост списка
	LinkedList!T tail()
	{
		LinkedList!T list = new LinkedList!T;
		
		if (first.getNext !is null)
		{
			auto current = first.getNext;
		
			while (current !is null)
			{
				list.addBack(
					current.getName,
					current.getValue
				);
		
				current = current.getNext;
			}
		}
	
		return list;
	
	}

	// n-ый элемент
	auto reference(size_t index)
	{
		auto current = first;
	
		if (index < this.length)
		{
	
			for (int i = 0; i < index; i++)
			{
				current = current.getNext;
			}
		}
	
		return current;
	
	}
	
	// сечение списка
	auto slice(size_t begin, size_t end)
	{
		LinkedList!T list = new LinkedList!T;
	
		if ((0 <= begin) && (end < this.length) && (begin <= end))
		{
			for (size_t i = begin; i < end; i++)
			{
				auto element = this.reference(i);
	
				list.addBack(
					element.getName,
					element.getValue
				);
			}
		} 
	
	 	return list;
	}
	
	// добавление в начало списка
	void addFront(T)(string name, T value)
	{
		Link!T link = new Link!T(name, value);
	
		link.setNext(first);
	
		first = link;
	}
	
	// добавление в конец списка
	void addBack(T)(string name, T value)
	{
		Link!T link = new Link!T(name, value);
	
		auto current = first;
		auto previous = first;
	
		if (first !is null)
		{
			while (current !is null)
			{
				previous = current;
				current = current.getNext;
			}
	
			previous.setNext(link);
		}
		else
		{
			addFront(name, value);
		}
	}
	
	// удалить голову списка
	void excludeHead()
	{
		first = first.getNext;
	}
	
	// удалить хвост списка
	void excludeTail()
	{
		first.setNext(null);
	}
	
	// удалить элемент по его имени
	void remove(string name)
	{
		auto current = first;
		auto previous = first; 
	
	 	while(current.getName != name)
		{
			if (current.getNext !is null)
			{
				previous = current;
				current = current.getNext;
			}
		}
	
		if (current == first)
		{
			first = first.getNext;
		}
		else
		{
			previous.setNext(current.getNext);
		}
	}
	
	// копия списка
	LinkedList!T clone()
	{
		LinkedList!T list = new LinkedList!T;
	
		auto current = first;
	
		while (current !is null)
		{
			list.addBack(
				current.getName,
				current.getValue
			);
	
			current = current.getNext;
		}
	
		return list;
	}
	
	// добавить список
	void extend(T)(LinkedList!T list)
	{
		for (size_t i = 0; i < list.length; i++)
		{
			auto element = list.reference(i);
	
			addBack(
				element.getName,
				element.getValue
			);
		}
	}
	
	// строковое представление списка
	override string toString()
	{
		string[] accumulator;
	
		auto current = first;
	
		while (current !is null)
		{
			accumulator ~= current.toString;
			current = current.getNext;
		}
	
		return format("[%s]", accumulator.join(","));
	}
	
	// преобразование в массив
	T[] array()
	{
		T[] arrayN;
	
		auto current = first;
	
		while (current !is null)
		{
			arrayN ~= current.getValue;
			current = current.getNext;
		}
	
		return arrayN;
	}
	
	// преобразование в ассоциативный массив
	T[string] assocArray()
	{
		T[string] arrayN;
	
		auto current = first;
	
		while (current !is null)
		{
			arrayN[current.getName] = current.getValue;
			current = current.getNext;
		}
	
		return arrayN;
	}
	
	// применение функции к именам узлов списка
	auto applyToNames(alias Functional)()
	{
		LinkedList!T list = new LinkedList!T;
	
		auto current = first;
	
		while (current !is null)
		{
			list.addBack(
				Functional(current.getName),
				current.getValue
			);
	
			current = current.getNext;
		}
	
		return list;
	}
	
	// применение функции к значениям списка
	auto applyToValues(alias Functional)()
	{
		LinkedList!T list = new LinkedList!T;
	
		auto current = first;
	
		while (current !is null)
		{
			list.addBack(
				current.getName,
				Functional(current.getValue)
			);
	
			current = current.getNext;
		}
	
		return list;
	}
}

Вот простая демонстрация всех возможностей:

string func(string s)
{
	return s.toUpper;
}

void main()
{
	LinkedList!string a = new LinkedList!string;
	
	writefln("Empty list: %s", a);
	
	a.addBack("A", "Heart");
	a.addBack("B", "Desire");
	a.addBack("C", "Will");
	a.addBack("D", "Rock");
	a.addBack("E", "Peace");
	a.addBack("F", "One");
	a.addBack("G", "by");
	a.addBack("H", "Fire");
	
	writefln("Non-Empty list: %s", a);
	writefln("Head of list: %s", a.head);
	writefln("Tail of list: %s", a.tail);
	writefln("Length of list: %s", a.length);
	writefln("Is empty: %s", a.empty);
	
	a.remove("E");
	
	writefln("Remove E: %s", a);
	
	a.addFront("0", "TESTING");
	
	writefln("Add 0: %s", a);
	
	a.extend(a.clone);
	
	writefln("Extending with clone: %s", a);
	writefln("7th element: %s", a.reference(7u));
	writefln("Slice from 3 to 7: %s", a.slice(3u, 7u));
	writefln("Applying toLower: %s", a.applyToNames!toLower);
	writefln("Applying toUpper: %s", a.applyToValues!func);
}