Skip to content

Instantly share code, notes, and snippets.

@ChanMenglin
Last active August 6, 2021 06:54
Show Gist options
  • Save ChanMenglin/13f36ed371cfc071f02d2c684ad79bc1 to your computer and use it in GitHub Desktop.
Save ChanMenglin/13f36ed371cfc071f02d2c684ad79bc1 to your computer and use it in GitHub Desktop.
C# LinkedList
using System;
using System.Runtime.dll;
namespace DataStructures_Algorithms
{
class LinkedList<T> where T : class
{
public LinkedListNode<T> head { get; set; }
public LinkedListNode<T> tail { get; set; }
public int length
{
get
{
if (this.IsEmpty()) return 0;
int i = 0;
LinkedListNode<T> current = this.head;
while (current.next != null)
{
current = current.next;
i++;
}
return i;
}
}
public bool IsEmpty()
{
return this.head == null;
}
public LinkedList<T> Prepend(T data)
{
LinkedListNode<T> node = new LinkedListNode<T>(data);
if (this.IsEmpty())
{
this.head = node;
this.tail = node;
}
else
{
node.next = this.head;
this.head = node;
}
return this;
}
public LinkedList<T> Append(T data)
{
LinkedListNode<T> node = new LinkedListNode<T>(data);
if (this.IsEmpty())
{
this.head = node;
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
return this;
}
public bool Contains(T data)
{
if (this.IsEmpty()) return false;
LinkedListNode<T> current = this.head;
while (current != null && current.data != data)
{
current = current.next;
}
if (current == null) return false;
return true;
}
public bool Delete(T data)
{
if (this.IsEmpty()) return false;
if (this.head.data == data)
{
if (this.head == this.tail)
{
this.head = null;
this.tail = null;
}
else
{
this.head = this.head.next;
}
return true;
}
LinkedListNode<T> current = this.head;
while (current.next != null && current.next.data != data)
{
current = current.next;
}
if (current.next != null)
{
if (current.next == this.tail)
{
this.tail = current;
}
current.next = current.next.next;
return true;
}
return false;
}
public System.Collections.IEnumerator GetEnumerator()
{
LinkedListNode<T> current = this.head;
while (current != null)
{
yield return current.data;
current = current.next;
}
}
public System.Collections.Generic.IEnumerable<T> Traverse()
{
LinkedListNode<T> current = this.head;
while (current != null)
{
yield return current.data;
current = current.next;
}
}
}
}
using System;
namespace DataStructures_Algorithms
{
class LinkedListNode<T> {
public T data { get; set; }
public LinkedListNode<T> next { get; set; }
public LinkedListNode(T data) {
this.data = data;
this.next = null;
}
}
}
using Xunit;
using Moq;
namespace DataStructures_Algorithms.Tests
{
public class LinkedListTest
{
[Fact]
public void AppendTest()
{
var list = new LinkedList<string>();
var str1 = "1";
var str2 = "2";
list.Append(str1).Append(str2);
Assert.Equal(list.head.data, str1);
Assert.Equal(list.tail.data, str2);
}
[Fact]
public void PrependTest() {
var list = new LinkedList<string>();
var str1 = "1";
var str2 = "2";
list.Append(str1).Prepend(str2);
Assert.Equal(list.head.data, str2);
Assert.Equal(list.tail.data, str1);
}
[Fact]
public void IsEmptyTest() {
var list = new LinkedList<string>();
Assert.True(list.IsEmpty());
var str1 = "1";
list.Append(str1);
Assert.False(list.IsEmpty());
Assert.Equal(list.head.data, str1);
Assert.Equal(list.tail.data, str1);
}
[Fact]
public void LengthTest() {
var list = new LinkedList<string>();
Assert.Equal(0, list.length);
var str1 = "1";
var str2 = "2";
list.Append(str1).Append(str2);
Assert.Equal(2, list.length);
Assert.Equal(list.head.data, str1);
Assert.Equal(list.tail.data, str2);
}
[Fact]
public void DeleteTest() {
var list = new LinkedList<string>();
Assert.False(list.Delete("1"));
var str1 = "1";
var str2 = "2";
var str3 = "3";
var str4 = "4";
list.Append(str1).Append(str2).Append(str3).Append(str4);
Assert.True(list.Delete(str1));
Assert.Equal(list.head.data, str2);
Assert.Equal(list.tail.data, str4);
Assert.True(list.Delete(str4));
Assert.Equal(list.head.data, str2);
Assert.Equal(list.tail.data, str3);
Assert.True(list.Delete(str2));
Assert.True(list.Delete(str3));
Assert.Null(list.head);
Assert.Null(list.tail);
Assert.False(list.Delete("a"));
}
[Fact]
public void ContainsTest()
{
var list = new LinkedList<string>();
var str1 = "1";
var str2 = "2";
var str3 = "3";
list.Append(str1).Append(str2).Append(str3);
Assert.True(list.Contains(str1));
Assert.True(list.Contains(str2));
Assert.True(list.Contains(str3));
Assert.False(list.Contains("a"));
}
[Fact]
public void ForeachTest() {
var list = new LinkedList<string>();
for (int i = 0; i < 10; i++)
{
list.Append(i.ToString());
}
int n = 0;
foreach (string item in list)
{
Assert.Equal(n, int.Parse(item));
n++;
}
}
}
}
using System;
namespace DataStructures_Algorithms
{
class Program
{
static void Main(string[] args)
{
LinkedList<string> list = new LinkedList<string>();
list.Append("b").Prepend("a").Append("c");
LinkedListNode<string> node = list.head;
System.Console.WriteLine(list.Delete("c"));
foreach (var item in list)
{
System.Console.WriteLine(item);
}
foreach (var item in list.Traverse())
{
System.Console.WriteLine(item);
}
System.Console.WriteLine(list.Contains("c"));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment