C#-ArrayList

如果要动态地改变数组所占用内存空间的大小，则需以数组为基础进一步抽象，以实现这个功能。以图2.2的学生宿舍为例，为了使A班的所学生住在连续的宿舍内，可以把A班的学生全部搬迁到连续的5间空宿舍内。其效果如图2.6所示：

现实中，为了让一个班新加入的10个学生能跟原来的学生住在一起而把班级整体搬迁，这样的做法显示不合适，因为搬迁的成本太高。但在计算机中，内存成片区域间的拷贝成本是非常低的，这样的解决方案是合理可行的。

但是这个解决方案还存在问题，如果一个班级频繁地有新学生加入，为了保证学生能住在连续的宿舍内，整个班级就不得不频繁地搬迁。可以采用以空间换时间的做法来解决这个问题，在学生每次搬迁时，都让班级宿舍的数量是原来的两倍。也就是说，如果原来一个班级有4间宿舍，搬迁后就变为8间，再次搬迁则变为16间。如图2.2所示，A班的宿舍为201～208。206～208这三间宿舍做为本班备用宿舍，不再允许其他班级的学生搬入。

C#中的ArrayList正是采用上述方法来动态改变数组大小的。ArrayList又被称为动态数组，它的存储空间可以被动态改变，同时还拥有添加、删除元素的功能。

下面列出了ArrayList的部分核心代码：

【ArrayList.cs】

1   using System;

2   namespace LinearList

3   {

4       public class ArrayList

5       {

6           // 成员变量

7           private const int _defaultCapacity = 4; //默认初始容量

8           private object[] _items; //用于存放元素的数组

9           private int _size; //指示当前元素个数

10          //当元素个数为零时的数组状态

11          private static readonly object[] emptyArray = new object[0];

12          // 方法

13          public ArrayList() //默认构造方法

14          {   //这样做可以避免元素个数为零时的访问出错

15              this._items = emptyArray;

16          }

17          //指定ArrayList初始容量的构造方法

18          public ArrayList(int capacity)

19          {

20              if (capacity < 0)

21              {   //当容量参数为负数时引发异常

22                  throw new ArgumentOutOfRangeException("capacity",

23                      "为ArrayList指定的初始容量不能为负数");

24              }

25              //按照capacity参数指定的长度的值初始化数组

26              this._items = new object[capacity];

27          }

28          //添加一个方法

29          public virtual int Add(object value)

30          {   //当空间满时

31              if (this._size == this._items.Length)

32              {   //调整空间

33                  this.EnsureCapacity(this._size + 1);

34              }

35              this._items[this._size] = value; //添加元素

36              return this._size++; //使长度加

37          }

38          //动态调整数组空间

39          private void EnsureCapacity(int min)

40          {

41              if (this._items.Length < min)

42              {   //空间加倍

43                  int num = (this._items.Length == 0) ?

44                      _defaultCapacity : (this._items.Length * 2);

45                  if (num < min)

46                  {

47                      num = min;

48                  }

49                  //调用Capacity的set访问器以按照num的值调整数组空间

50                  this.Capacity = num;

51              }

52          }

53          //在指定索引入插入指定元素

54          public virtual void Insert(int index, object value)

55          {

56              if ((index < 0) || (index > this._size))

57              {

58                  throw new ArgumentOutOfRangeException("index", "索引超出范围");

59              }

60              if (this._size == this._items.Length)

61              {   //当空间满时调整空间

62                  this.EnsureCapacity(this._size + 1);

63              }

64              if (index < this._size)

65              {   //插入点后面的所有元素向后移动一位

66                  Array.Copy(this._items, index,

67                      this._items, index + 1, this._size - index);

68              }

69              this._items[index] = value; //插入元素

70              this._size++; //使长度加

71          }

72          //移除指定索引的元素

73          public virtual void RemoveAt(int index)

74          {

75              if ((index < 0) || (index >= this._size))

76              {

77                  throw new ArgumentOutOfRangeException("index", "索引超出范围");

78              }

79              this._size--; //使长度减

80              if (index < this._size)

81              {   //使被删除元素后的所有元素向前移动一位

82                  Array.Copy(this._items, index + 1,

83                      this._items, index, this._size - index);

84              }

85              this._items[this._size] = null; //最后一位空出的元素置空

86          }

87          //裁减空间，使存储空间正好适合元素个数

88          public virtual void TrimToSize()

89          {

90              this.Capacity = this._size;

91          }

92          // 属性

93          public virtual int Capacity //指示ArrayList的存储空间

94          {

95              get

96              {

97                  return this._items.Length;

98              }

99              set

100             {

101                 if (value != this._items.Length)

102                 {

103                     if (value < this._size)

104                     {

105                         throw new ArgumentOutOfRangeException("value", "容量太小");

106                     }

107                     if (value > 0)

108                     {   //开辟一块新的内存空间存储元素

109                         object[] destinationArray = new object[value];

110                         if (this._size > 0)

111                         {   //把元素搬迁到新空间内

112                             Array.Copy(this._items, 0,

113                                 destinationArray, 0, this._size);

114                         }

115                         this._items = destinationArray;

116                     }

117                     else //最小空间为_defaultCapacity所指定的数目，这里是

118                     {

119                         this._items = new object[_defaultCapacity];

120                     }

121                 }

122             }

123         }

124         public virtual int Count //只读属性，指示当前元素个数

125         {

126             get

127             {

128                 return this._size;

129             }

130         }

131         public virtual object this[int index] //索引器

132         {

133             get //获取指定索引的元素值

134             {

135                 if ((index < 0) || (index >= this._size))

136                 {

137                     throw new ArgumentOutOfRangeException("index", "索引超出范围");

138                 }

139                 return this._items[index];

140             }

141             set //设置指定索引的元素值

142             {

143                 if ((index < 0) || (index >= this._size))

144                 {

145                     throw new ArgumentOutOfRangeException("index", "索引超出范围");

146                 }

147                 this._items[index] = value;

148             }

149         }

150     }

151 }

上述代码通过在一个数组（第8行代码的成员变量_items）的基础上做进一步抽象，构建了一个可动态改变空间的顺序表ArrayList，并实现了一些基础操作，下面对之进行一一介绍。

1.    初始化

这里实现了2种初始方法，第一种为13～16行代码，它把顺序表空间初始化为一个0长度数组。这样做的目的是为了调用方便。做为成员变量的object类型数组_items默认会被初始化为null，如果不把它初始化为0长度数组，在使用代码 ArrayList arr = new ArrayList() 来创建ArrayList后试图访问它的Count属性将会导致错误发生。

第二种初始化方法为18～27行代码，它根据capacity参数所指定的值来初始化_items数组的长度，如果初始化一个长度为100的ArrayList数组可以使用如下代码：

ArrayList arr = new ArrayList(100)

当可以预见ArrayList所操作的大概元素个数时，使用这种方法可以在一定程序上避免数组重复创建和数据迁移，以提高性能和减少内存垃圾回收的压力。

2.    动态改变存储空间操作

39～52行的EnsureCapacity(int min)方法用于空间不足时使空间加倍，从代码：

int num = (this._items.Length == 0) ? _defaultCapacity : (this._items.Length * 2);

可以得知，当元素个数为0是，空间增长为4，否则将翻倍。改变空间大小的代码是在Capacity属性中的set访问器中实现的（代码99～122行）。代码

object[] destinationArray = new object[value];

创建了一个新的object数组，它在内存中开辟了一个新的空间用于存放元素。代码

Array.Copy(this._items, 0, destinationArray, 0, this._size);

把_items数组中的元素全部拷贝到新数组destinationArray中，可以把它理解为数据搬新家。最后通过

this._items = destinationArray;

使用于存放数据的成员变量_items指向新的数组对象destinationArray。

88～91行的TrimToSize()方法用于裁减多余空间，实际的裁减操作也是在Capacity属性中的set访问器中实现。这个操作也会导致数组的重新创建和数据迁移，建议一般情况下不使用此操作，除非集合中的剩余空间很多。

3.    元素的读写操作

131～149行代码实现了一个索引器，这样就可以使用中括号加索引号来读取和给元素赋值，使ArrayList的使用看上去和数组很相似。

4.    元素的添加和插入操作

29～37行的Add(object value)方法实现了添加元素的功能。元素添加在集合的末尾，成员变量_size用于指示当前元素个数，它总是指向集合中的最后一个元素。

54～71行的Insert(int index, object value)方法用于在指定索引处插入一个元素。为了保证顺序表中的每个元素物理上相邻，插入点后面的所有元素都将后移一位，其效果如图2.7(a)所示。

1.    元素的删除操作

73～86行的RemoveAt(int index)方法用于删除指定索引的元素，删除指定元素后，删除点后的所有元素将向前移动一位其效果如图2.7(b)所示。

下面对ArrayList类进行测试。

【例2-1】ArrayList的使用

新建一个控制台应用程序，并在项目中把上面的ArrayList.cs文件做为一个【现有项】添加进去。在代码窗体前面使用如下语句加入LinearList命名空间：

using LinearList;

并在Main方法中输入如下代码：

1  static void Main(string[] args)

2  {

3      ArrayList arr = new ArrayList();

4      Console.WriteLine("arr现在的容量为：" + arr.Capacity + "  长度为:" + arr.Count);

5      arr.Add(1); //添加一个元素

6      Console.WriteLine("arr现在的容量为：" + arr.Capacity + "  长度为:" + arr.Count);

7      for (int i = 2; i <= 5; i++)

8      {   //添加4个元素，完成后元素总数达到5个

9          arr.Add(i);

10     }

11     Console.WriteLine("arr现在的容量为：" + arr.Capacity + "  长度为:" + arr.Count);

12     for (int i = 6; i <= 9; i++)

13     {   //添加4个元素，完成后元素总数达到9个

14         arr.Add(i);

15     }

16     Console.WriteLine("arr现在的容量为：" + arr.Capacity + "  长度为:" + arr.Count);

17     for (int i = 0; i < arr.Count; i++) //打印所有元素

18     {

19         Console.Write(i + "  ");

20     }

21     //删除两个元素

22     arr.RemoveAt(arr.Count - 1);

23     arr.RemoveAt(arr.Count - 1);

24     Console.WriteLine(); //换行

25     for (int i = 0; i < arr.Count; i++) //打印所有元素

26     {

27         Console.Write(i + "  ");

28     }

29     Console.WriteLine(); //换行

30     Console.WriteLine("arr现在的容量为：" + arr.Capacity + "  长度为:" + arr.Count);

31     arr.TrimToSize(); //载减多余空间

32     Console.WriteLine("arr现在的容量为：" + arr.Capacity + "  长度为:" + arr.Count);

33 }

运行结果：如图2.8所示。

由运行结果可以得知，数组对象arr的容量随着元素的不断增加，从0→4→8→16不断改变，在删除两个元素之后，容量还保持在16不变，在通过调用TrimToSize()裁减空间后，容量最终变为7。

2.2.4 类型安全

数组和ArrayList的本质区别在于前者是类型安全的，而后者不是类型安全的。ArrayList为了兼容所有类型的对象，使用了object数组，这给使用带来了一些的麻烦。如下例所示：

【例2-2】数组和ArrayList的对比

本例使用了C#类库中的ArrayList而不是前面自定义的ArrayList，它存在于System.Collections命名空间中。新建一个控制台应用程序，引入System.Collections命名空间，并在Main()方法中输入如下代码：

1  static void Main(string[] args)

2  {

3      int[] arr = new int[2];

4      arr[0] = 5;

5      arr[1] = 6;

6      int result = arr[0] * arr[1];

7      Console.WriteLine(result);

8      ArrayList arrL = new ArrayList();

9      arrL.Add(5);

10     arrL.Add(6);

11     result = (int)arrL[0] * (int)arrL[1];

12     Console.WriteLine(result);

13 }

运行结果：

30

30

本例使用数组和ArrayList分别做了相同的事情，但使用方法却大相径庭。首先数组在创建时就已经确定只接收int类型数据，并且它的长度是固定的。而ArrayList则可以接收任意object类型，而事实上，C#中的所有类均是<span