C#实现自定义的 LinkedList 和 ArrayList前言：总结：

80 阅读 0 评论 53 点赞

我是靠谱客的博主糟糕微笑，最近开发中收集的这篇文章主要介绍C#实现自定义的 LinkedList 和 ArrayList前言：总结：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言：

本篇文章是我在实习阶段的一道练习题，代码是我的思想加上导师的指导写出来的，我觉得对我的编程能力有一定的提高，因此我将代码分享出来，希望可以帮助那些需要的人。

题目描述：

简介：写一个链表的数据结构，要求实现IList<T>接口。

具体要求：

1、使用代码规范。

2、至少对IList中的Add，Remove，Insert，Indexer，IEnumerator进行单元测试。

3、对上述每个单元测试方法至少书写4种不同的单元测试。

4、要求从Object派生，实现System.Collections.Generic.IList<T>。

5、内部存储不能使用.NET内置链表。

分析：题目要求实现linkedList（内部使用链表实现），在此我多余实现了ArrayList（内部使用数组实现），通过这两种方式的实现链表，我对实现中的一些变量临界条件有了更准确的判断，并且通过导师的指导，对编程的认识有了一定的提高。

ArrayList.cs = 数组 + 迭代器 + 精细的控制与异常

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
namespace MyList
{
public class ArrayList<T> : IList<T>
{
/// <summary>
/// default capacity
/// </summary>
private int defaultCapacity;
/// <summary>
/// storage data
/// </summary>
private T[] array;
/// <summary>
/// number of elements
/// </summary>
private int count;
/// <summary>
/// 扩容因子，默认为1，翻倍扩展
/// dilatancy factor, the default is 1 that is double expansion
/// </summary>
private double dilatancyFactor;
/// <summary>
/// custom iterator
/// </summary>
private MyIEnumerator<T> myIEnumerator;
/// <summary>
/// init data
/// </summary>
private void initData()
{
Debug.WriteLine("init data ......");
defaultCapacity = 8;
count = 0;
dilatancyFactor = 1;
}
public ArrayList()
{
initData();
array = new T[defaultCapacity];
myIEnumerator = new MyIEnumerator<T>(this.array);
}
public ArrayList(int capacity)
{
initData();
this.defaultCapacity = capacity;
array = new T[defaultCapacity];
myIEnumerator = new MyIEnumerator<T>(this.array);
}
public ArrayList(double dilatancyFactor)
{
initData();
this.dilatancyFactor = dilatancyFactor;
array = new T[defaultCapacity];
myIEnumerator = new MyIEnumerator<T>(this.array);
}
public ArrayList(int capacity, double dilatancyFactor)
{
initData();
this.defaultCapacity = capacity;
this.dilatancyFactor = dilatancyFactor;
array = new T[defaultCapacity];
myIEnumerator = new MyIEnumerator<T>(this.array);
}
public T this[int index] {
get {
if(index < 0 || index >= count)
{
throw new ArgumentOutOfRangeException("index");
} else
{
return array[index];
}
}
set {
if (index < 0 || index >= count)
{
throw new ArgumentOutOfRangeException("index");
}
else
{
array[index] = value;
}
}
}
public int Count => count;
public bool IsReadOnly => false;
/// <summary>
/// add element
/// </summary>
/// <param name="item">element</param>
public void Add(T item)
{
if (count >= defaultCapacity)
{
Reset();//扩容 dilatation
}
array[count++] = item;
}
public void Clear()
{
T[] newArray = new T[this.defaultCapacity];
this.array = newArray;
count = 0;//注意count置0
}
public bool Contains(T item)
{
int index = this.IndexOf(item);
if(index == -1)
{
Debug.WriteLine("list no exit this item");
throw new ArgumentException("item");
} else
{
return true;
}
}
/// <summary>
/// copy the element from list to array and start with arrayIndex
/// </summary>
/// <param name="array">target array</param>
/// <param name="arrayIndex">arrayIndex</param>
public void CopyTo(T[] array, int arrayIndex)
{
int targetArrayLength = array.Length;
//first judge whether the target arrayIndex is mistaken
if(arrayIndex < 0 || arrayIndex >= targetArrayLength)
{
Debug.WriteLine("arrayIndex out of bound");
throw new ArgumentOutOfRangeException("arrayIndex");
}
//second judge whether the array capacity is mistaken
if(this.count + arrayIndex > targetArrayLength)
{
throw new ArgumentException("array");
} else
{
//copy
Array.Copy(this.array, 0, array, arrayIndex, count);
}
}
/// <summary>
/// get the list enumerator
/// </summary>
/// <returns></returns>
public IEnumerator<T> GetEnumerator()
{
//我决定当用户调用迭代器时重新new一个迭代器出来，因为这里我是通过将数组传递进去，而当当前数组的
//引用（地址）在reset时被改变之后，我的迭代器中的数组仍是之前的数组
//return (IEnumerator<T>)new MyIEnumerable<T>(this.array);
//既然数组引用可以更换，那么迭代器的引用也可以更换，哈哈
return (IEnumerator<T>)this.myIEnumerator;
}
/// <summary>
/// return the item's index
/// </summary>
/// <param name="item">value</param>
/// <returns>if -1 is returned,it means that this element is not found</returns>
public int IndexOf(T item)
{
int index = -1;
for(int i = 0; i < count; i++)
{
try
{
if(Object.Equals(array[i], item))
{
return i;
}
//if (array[i].Equals(item))
//{
//
return i;
//}
}
catch (NullReferenceException e)
{
Debug.WriteLine("数组中含有空值，出现空指针异常");
throw e;
}
}
return index;
}
/// <summary>
/// intert an element to list
/// </summary>
/// <param name="index">the index in array</param>
/// <param name="item">the value </param>
public void Insert(int index, T item)
{
if (index >= count)//判断参数是否有误
{
Debug.WriteLine("insert method' argument has error");
throw new ArgumentOutOfRangeException("index");
} else
{
if (count >= defaultCapacity)//判断是否需要扩容
{
Reset(); //扩容
}
//将元素向后移动
for (int i = count; i > index; i--)
{
array[i] = array[i - 1];
}
//插入元素
array[index] = item;
count++;
}
}
/// <summary>
/// remove the element in list
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public bool Remove(T item)
{
int index = -1;
//找到需要删除的节点下标
for(int i = 0; i < count; i++)
{
if (array[i].Equals(item))
{
index = i;
break;
}
}
//要删除的元素不存在
if(index == -1)
{
Debug.WriteLine("the will be removed element does not exist");
return false;
}
//移动元素
for (int j = index; j < count - 1; j++)
{
array[j] = array[j + 1];
}
count--;
return true;
}
/// <summary>
/// remove element according to the index
/// </summary>
/// <param name="index">the index</param>
public void RemoveAt(int index)
{
if(index >= count)
{
Debug.WriteLine("the argument 'index' out of range");
throw new IndexOutOfRangeException("index");
} else
{
for (int i = index; i < count - 1; i++)
{
array[i] = array[i + 1];
}
}
}
public override string ToString()
{
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.Append("[");
for (int i = 0; i < count; i++)
{
stringBuilder.Append(array[i] + ((i != count - 1) ? "," : ""));
}
stringBuilder.Append("]");
return stringBuilder.ToString();
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public int GetCapacity()
{
return defaultCapacity;
}
/// <summary>
/// reset configuration argument
/// </summary>
private void Reset()
{
Console.WriteLine("开始扩容……");
//扩容
defaultCapacity += Convert.ToInt32(defaultCapacity * dilatancyFactor);
T[] newArray = new T[defaultCapacity];
//复制数据
for (int i = 0; i < array.Length; i++)
{
newArray[i] = array[i];
}
//将新数组的引用赋值给旧数组
array = newArray;
//迭代器中的数组仍然需要更新
this.myIEnumerator = new MyIEnumerator<T>(array);
}
/// <summary>
///
set the element according to the index
/// </summary>
/// <param name="index"></param>
/// <param name="value"></param>
private void SetValue(int index, T value)
{
if(index >= count)
{
throw new IndexOutOfRangeException("index");
} else
{
array[index] = value;
}
}
}
enum ErrorStatus
{
NO_ELEMENT_TO_BE_DELETE,
THE_ELEMENT_INDEX_ERROR,
THE_TARGET_ARRAY_INDEX_ERROR,
THE_TARGET_ARRAY_LENGTH_TOO_SMALL,
THE_INDEX_OUT_OF_BOUND,
}
class MyException : ApplicationException
{
private String message;
private ErrorStatus status;
public MyException(String message, ErrorStatus status)
{
this.message = message;
this.status = status;
}
public String Info()
{
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.Append("Exception info { ");
stringBuilder.Append("message : [" + this.message + "], ");
stringBuilder.Append("status : [" + this.status + "]");
stringBuilder.Append(" }");
return stringBuilder.ToString();
}
}
/// <summary>
///
custom iterator
/// </summary>
/// <typeparam name="T"></typeparam>
class MyIEnumerator<T> : IEnumerator<T>
{
T[] array;
int index = -1;
int count;
public MyIEnumerator(T[] array)
{
this.array = array;
}
public T Current => GetCurrent();
object IEnumerator.Current => GetCurrent();
public void Dispose()
{
Console.WriteLine("释放资源……");
}
public bool MoveNext()
{
count = this.GetCount();
index++;
return index < count;
}
public void Reset()
{
index = -1;
}
private T GetCurrent()
{
try
{
return array[index];
}
catch (IndexOutOfRangeException e)
{
Debug.WriteLine(e.Message);
throw e;
}
}
private int GetCount()
{
int i;
for(i = 0; i < array.Length; i++)
{
if(array[i] != null)
{
} else
{
break;
}
}
return i;
}
}
}

LinkedList.cs = 链表（节点） + 迭代器 + 精细的控制与异常

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
namespace MyList2
{
internal class MyNode<T>
{
public T Data { get; set; }
public MyNode<T> Next { get; set; }
public MyNode(T data)
{
this.Data = data;
}
}
public class MyLinkedList<T> : IList<T>
{
private MyNode<T> _head;
private int _count = 0;
public T this[int index]
{
get
{
CheckArrayIndex(index, _count);
var node = this.FindNodeByIndex(index);
return node.Data;
}
set
{
CheckArrayIndex(index, _count);
var node = this.FindNodeByIndex(index);
node.Data = value;
}
}
public int Count => _count;
public bool IsReadOnly => false;
/// <summary>
/// add element
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
var newNode = new MyNode<T>(item);
if (_count == 0)
{
_head = newNode;
}
else
{
this.FindNodeByIndex(_count - 1).Next = newNode;
}
_count++;
}
/// <summary>
/// clear linkedList
/// </summary>
public void Clear()
{
_head = null;
_count = 0;//set 0
}
/// <summary>
/// judge linkedList weather contain the item
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public bool Contains(T item)
{
int index = IndexOf(item);
if(index == -1)
{
return false;
}
return true;
}
public void CopyTo(T[] array, int arrayIndex)
{
CheckArrayIndex(arrayIndex, array.Length);
if(arrayIndex + _count > array.Length)
{
throw new ArgumentOutOfRangeException("array,arrayIndex");
}
MyNode<T> temp = _head;
while(temp != null)
{
array[arrayIndex++] = temp.Data;
temp = temp.Next;
}
}
public IEnumerator<T> GetEnumerator()
{
var node = _head;
while (node != null)
{
yield return node.Data;//中断返回，并不影响后续语句的执行
node = node.Next;
}
}
/// <summary>
/// get index that the item in linkedList
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public int IndexOf(T item)
{
int index = -1;
MyNode<T> temp = _head;
while(temp != null)
{
index++;
//这种比较数据不进行装箱拆箱操作
if(System.Collections.Generic.EqualityComparer<T>.Default.Equals(temp.Data, item))
{
return index;
}
temp = temp.Next;
}
return -1;
}
/// <summary>
/// insert the item into linkedList
/// </summary>
/// <param name="index"></param>
/// <param name="item"></param>
public void Insert(int index, T item)
{
CheckArrayIndex(index, _count);
var newNode = new MyNode<T>(item);
if (index == 0)//head insert
{
newNode.Next = _head;
_head = newNode;
}
else
{
var preNode = this.FindNodeByIndex(index - 1);
newNode.Next = preNode.Next;
preNode.Next = newNode;
}
_count++;
}
/// <summary>
/// delete element by item
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public bool Remove(T item)
{
int index = this.IndexOf(item);
if(index <= -1)
{
return false;
}
this.RemoveAt(index);
return true;
}
/// <summary>
/// delete element by index
/// </summary>
/// <param name="index"></param>
public void RemoveAt(int index)
{
CheckArrayIndex(index, _count);
if (index == 0)//remove _head
{
_head = _head.Next;
}
MyNode<T> preNode = FindNodeByIndex(index - 1);
MyNode<T> target = FindNodeByIndex(index);
preNode.Next = target.Next;
_count--;
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
private MyNode<T> FindNodeByIndex(int index)
{
MyNode<T> result = this._head;
while (index > 0)
{
result = result.Next;
index--;
}
return result;
}
private MyNode<T> FindNodeByValue(T value)
{
MyNode<T> temp = this._head;
while(temp != null)
{
if(System.Collections.Generic.Comparer<T>.Equals(temp.Data, value))
{
return temp;
}
}
return null;
}
/// <summary>
/// check index order by array.length
/// </summary>
/// <param name="index"></param>
/// <param name="length"></param>
private void CheckArrayIndex(int index, int length)
{
if (index < 0 || index >= length)
{
throw new ArgumentOutOfRangeException("index");
}
}
public override string ToString()
{
return string.Join<T>(",", this);
//return String.Join(",", this);
}
}
class MyIEnumerator<T> : IEnumerator<T> {
MyNode<T> head;
MyNode<T> current;
public MyIEnumerator(MyNode<T> head)
{
this.head = head;
this.current = head;
}
public T Current => GetCurrent();
object IEnumerator.Current => GetCurrent();
public void Dispose()
{
Console.WriteLine("释放资源……");
}
public bool MoveNext()
{
if(current != null)
{
if(current == head)
{
return true;
}
current = current.next;
return true;
}
return false;
}
private T GetCurrent()
{
return current.data;
}
/// <summary>
/// reset the head
/// </summary>
/// <param name="head"></param>
public void _ResetHead(MyNode<T> head)
{
this.head = head;
}
public void Reset()
{
throw new NotImplementedException();
}
}
}