Last active
August 6, 2021 06:54
-
-
Save ChanMenglin/13f36ed371cfc071f02d2c684ad79bc1 to your computer and use it in GitHub Desktop.
C# LinkedList
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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++; | |
} | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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