Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Singly-linked IList<T> in C#
//Rextester.Program.Main is the entry point for your code. Don't change it. //Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5 using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Diagnostics; //Not needed for the list namespace Rextester { public class Program { public static void Main(string[] args) { Stopwatch timer = new Stopwatch(); List<uint> list = new List<uint>(); LinkList<uint> link = new LinkList<uint>(); uint amount = 1000; //edit as you wish! timer.Start(); for(uint x = 0; x < amount; x++) list.Add(x); timer.Stop(); Console.WriteLine(timer.Elapsed.TotalMilliseconds); timer.Reset(); timer.Start(); for(uint x = 0; x < amount; x++) link.Add(x); timer.Stop(); Console.WriteLine(timer.Elapsed.TotalMilliseconds); //As I test this on here LinkList seems slower, but on my machine it's faster... anyway, LinkList is a singly-linked list implimentation of IList<T>. } } class LinkList<T> : IList<T> { public int Count { get; private set; } public bool IsReadOnly { get { return false; } } public T this[int index] { get { return NodeAt(index).value; } set { NodeAt(index).value = value; } } private Node start = null; private Node end = null; public LinkList() { } public LinkList(T initial) { Add(initial); } public LinkList(IEnumerable<T> values) { AddRange(values); } private Node NodeAt(int index) { //tries to find a node at an index, returns null on faliure if (start == null || index < 0) return null; //invalid index or empty list Node current = start; for (int x = 0; x < index; x++) { if (current.Next == null) return null; //cannot retrieve at index current = current.Next; //to next node } return current; } private void InsertNode(Node n, int index) { //inserts a node at an index and links accordingly Node A = NodeAt(index); //node before insert pos Node B = NodeAt(index - 1); //node after insert pos if (B == null) //empty list { start = n; end = start; Count++; return; } else B.Next = n; if (A != null) n.Next = A; //next node exists else end = n; //no next node Count++; } private void AddNode(Node n) { //adds a node to the end of the list if (start == null) //empty list { start = n; end = n; Count = 1; } else //not empty list { Count++; end.Next = n; end = end.Next; } } private Node RemoveNode(int index) { //Removes a node at a position and relinks the list if (start == null) return null; //empty list Node toremove = NodeAt(index); if (toremove == null) return null; //no node at that position Node A = NodeAt(index + 1); //node after node to remove Node B = NodeAt(index - 1); //node before node to remove if (B == null) start = A; //no node before node to remove else B.Next = A; if (A == null) end = B; //no node after node to remove toremove.Next = null; //clearing removed node Count--; return toremove; } private IEnumerable<Node> EnumerateNodes() { Node current = start; while (current != null) { yield return current; current = current.Next; } } public T First() { if (start == null) throw new InvalidOperationException(); else return start.value; } public T Last() { if (end == null) throw new InvalidOperationException(); else return end.value; } public T FirstOrDefault() { if (start == null) return default(T); else return First(); } public void RemoveFirst() { RemoveNode(0); } public void RemoveLast() { RemoveNode(Count - 1); } public IEnumerable<T> Where(Func<T, bool> predicate) { foreach (Node n in EnumerateNodes()) if (predicate(n.value)) yield return n.value; } public IEnumerable<T> Where(Func<T, int, bool> predicate) { int index = 0; foreach (Node n in EnumerateNodes()) if (predicate(n.value, index++)) yield return n.value; } public IEnumerable<Out> Map<Out>(Func<T, Out> f) { foreach (Node n in EnumerateNodes()) yield return f(n.value); } public Out Fold<Out>(Out initial, Func<T, Out, Out> f) { Out tor = initial; foreach (Node n in EnumerateNodes()) tor = f(n.value, tor); return tor; } public Out Fold<Out>(Func<T, Out, Out> f) { return Fold(default(Out), f); } public int IndexOf(T item) { int index = 0; foreach (Node n in EnumerateNodes()) { if (n.Equals(item)) return index; index++; } return -1; } public void Insert(int index, T item) { if (index < 0 || index > Count) throw new ArgumentOutOfRangeException(); InsertNode(new Node(item), index); } public void RemoveAt(int index) { if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException(); RemoveNode(index); } public void Add(T item) { AddNode(new Node(item)); } public void AddRange(IEnumerable<T> items) { foreach (T t in items) Add(t); } public void Clear() { start = null; Count = 0; } public bool Contains(T item) { return IndexOf(item) != -1; } public void CopyTo(T[] array, int arrayIndex) { this.ToList().CopyTo(array, arrayIndex); } public bool Remove(T item) { int i = IndexOf(item); if (i == -1) return false; RemoveNode(i); return true; } public IEnumerator<T> GetEnumerator() { Node current = start; while (current != null) { yield return current.value; current = current.Next; } } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } public override bool Equals(object obj) { return (this as IList<T>).Equals(obj); } public override int GetHashCode() { return (this as IList<T>).GetHashCode(); } public override string ToString() { if (Count == 0) return "[]"; string res = Fold("[", ((i, o) => o + i.ToString() + ", ")); return res.Remove(res.Length - 2) + "]"; } private class Node { public T value; public Node Next = null; //pointer to the next node public Node(T value) { this.value = value; } } } }
run
|
edit
|
history
|
help
0
MultiThreading and CancellationToken
average and percentage
Test
NumsToVars
asdfghyjuytt4wed
Linq & lambdas
HMS abstract
Create URL Safe and Cryptographically Strong Short GUID
First pr
Bellman Ford algorithm helps to find the shortest path