第四节：顺序表剖析及利用数组手撸“动态数组ArryList”

一. 基础

1.前言

　　(1). 顺序表的标准解释：顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙，这个时候我们会发现数组和顺序表的性质很类似，实际上顺序表就是基于数组来实现。

　　(2). 顺序表的特点：访问数据块，如果第一个元素位置为Loc，存储空间为n，那么第i个元素的存储地址为：Loc+(i-1)* n 。

注：我们发现很多资料里写顺序表包含数组，这个说法是不准确的，数组里还有动态数组呢，准确的说法是：顺序表是基于数组来实现的。

2.C#中对应的数据结构

　　(1).数组：可以声明各种类型的数组，比如int[]、string[] 等待,最基本的单位，能动态扩容！

　　(2).动态数组：ArrayList,基于数组实现,可以动态扩容，可以存储各种类型，因此存在拆箱装箱的性能损耗.

　　(3).动态泛型集合：List<T>,原理和ArrayList一样，只不过多了个泛型，避免拆箱装箱问题。

3. ArrayList分析

　　它有两个构造函数(无参和有参)，无参构造函数是默认空间容量的，默认为4; 有参构造函数是指定存储容量; 无论是默认还是指定,当添加元素空间不足的时候,扩容的规则都是原容量*2 . 下面是几个常用属性和方法：

(1).Count：获取当前元素的个数

(2).Capacity：占用的存储空间

(3).this[index]：索引器,获取和设置元素

(4).Add()：添加元素(加在最后面)

(5).Insert()：指定索引出插入元素

(6).RemoveAt()：删除指定索引的元素

(7).TrimToSize()：裁剪空间,使存储空间正好适合元素个数. 【实际案例中，轻易不要用，因为要开辟新的临时空间，进行copy分配切换，典型的用时间换空间！！】

下面分享两段代码，分别是默认容量、指定容量下，内存空间的变化：

            // 默认存储容量内存空间变化
            {
                Console.WriteLine("------------------------------ 默认存储容量内存空间变化--------------------------------");
                //List<int> mylist1 = new List<int>();
                ArrayList mylist1 = new ArrayList();
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");//0,0
                mylist1.Add(1); //4
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}"); //1,4
                mylist1.Add(2);
                mylist1.Add(3);
                mylist1.Add(4);
                mylist1.Add(5);  //4*2
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");  //5,8
                mylist1.Add(6);
                mylist1.Insert(6,7);  //索引为6的位置插入7
                mylist1.Add(8);
                mylist1.Add(9);   //8*2=16
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");  //9,16
                //mylist1.TrimExcess();  //List
                mylist1.TrimToSize();  //ArrayList
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");   //9,9
                mylist1.RemoveAt(7);  //删除索引7的元素
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");   //8,9
            }

            // 指定存储容量的内存空间变换
            {
                Console.WriteLine("------------------------------指定存储容量的内存空间变换--------------------------------");
                List<int> mylist1 = new List<int>(2);
                //ArrayList mylist1 = new ArrayList();
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");//0,2
                mylist1.Add(1);
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}"); //1,2
                mylist1.Add(2);
                mylist1.Add(3);   //3,4
                mylist1.Add(4);   //4,4
                mylist1.Add(5);   //5,8
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");  //5,8
                mylist1.Add(6);
                mylist1.Insert(6, 7);  //索引为6的位置插入7
                mylist1.Add(8);
                mylist1.Add(9);
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");  //9,16
                mylist1.TrimExcess();  //List
                //mylist1.TrimToSize();  //ArrayList
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");
                mylist1.RemoveAt(7);  //删除索引7的元素
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");   //8,9
            }

二. 提高

1. 手撸ArrayList

(1).核心分析：基于数组来实现，特别注意下面代码：

int[] array=new int[5];
array.add(1);

分析上述代码，元素个数即 array.Count 等于1; 所占的存储空间即 array.length 等于5.

(2). 用到的核心方法：

Array.Copy 数组的复制：public static void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length);

将sourceArray数组从索引sourceIndex起，进行复制，复制的长度为length，然后粘贴到destinationArray数组中，从索引destinationIndex处进行覆盖接收。

代码分享：

  1  /// <summary>
  2     /// 自己实现ArrayList
  3     /// </summary>
  4     public class MyArrayList
  5     {
  6         private int _count;  //元素的个数 (默认是0)
  7         private object[] _arrayList; // 存放数据的数组
  8         private int _defaultCapacity = 4;  //默认容量
  9 
 10         private static object[] zArrayList = new object[0];   //私有的静态变量,只创建一次
 11 
 12         /// <summary>
 13         /// 默认容量
 14         /// </summary>
 15         public MyArrayList()
 16         {
 17             _arrayList = zArrayList;   //当系统多处new MyArrayList，且使用默认容量,不需要重复创建
 18         }
 19         /// <summary>
 20         /// 指定容量
 21         /// </summary>
 22         /// <param name="capacity"></param>
 23         public MyArrayList(int capacity)
 24         {
 25             if (capacity < 0)
 26             {
 27                 throw new ArgumentOutOfRangeException("不能指定负数");
 28             }
 29             if (capacity == 0)
 30             {
 31                 _arrayList = zArrayList;
 32             }
 33             if (capacity > 0)
 34             {
 35                 _arrayList = new object[capacity];
 36             }
 37 
 38         }
 39 
 40         //返回元素的个数（只读）
 41         public virtual int Count
 42         {
 43             get
 44             {
 45                 return this._count;
 46             }
 47         }
 48         //存储空间的获取和设置(重点！！！)
 49         public int Capacity
 50         {
 51             get
 52             {
 53                 return _arrayList.Length;
 54             }
 55             set
 56             {
 57                 if (value != _arrayList.Length)  //新设置的容量和原容量不相等的时候才需要设置
 58                 {
 59                     if (value < _count)
 60                     {
 61                         throw new ArgumentOutOfRangeException("容量太小");
 62                     }
 63                     //开辟一个新的内存空间来存储
 64                     object[] tempArray = new object[value];
 65                     if (_count > 0)
 66                     {
 67                         //复制粘贴操作
 68                         Array.Copy(_arrayList, 0, tempArray, 0, _count);
 69                     }
 70                     _arrayList = tempArray;
 71                 }
 72 
 73             }
 74         }
 75         //裁剪空间
 76         public void TrimToSize()
 77         {
 78             this.Capacity = this._count;
 79         }
 80 
 81         //索引器处理
 82         public object this[int index]
 83         {
 84             get
 85             {
 86                 if (index >= _count || index < 0)
 87                 {
 88                     throw new ArgumentOutOfRangeException("索引越界");
 89                 }
 90                 return _arrayList[index];
 91             }
 92             set
 93             {
 94                 if (index >= _count || index < 0)
 95                 {
 96                     throw new ArgumentOutOfRangeException("索引越界");
 97                 }
 98                 _arrayList[index] = value;
 99             }
100         }
101 
102 
103         /// <summary>
104         /// 扩容
105         /// </summary>
106         public void EnlargeCapacity()
107         {
108             //当元素个数和存储空间相等的时候,需要扩容
109             if (_count == _arrayList.Length)
110             {
111                 int num = _arrayList.Length == 0 ? _defaultCapacity : _arrayList.Length * 2;
112                 this.Capacity = num;
113             }
114         }
115 
116         /// <summary>
117         /// 增加元素,加在最后面
118         /// </summary>
119         public void Add(object data)
120         {
121             EnlargeCapacity();
122             _arrayList[_count] = data; //添加元素
123             _count++;   //元素个数 加1
124         }
125         public virtual void Insert(int index, object data)
126         {
127             //注：这里是index >_count ，而不是>=，等于的时候表示在末位插入
128             if (index > _count || index < 0)
129             {
130                 throw new ArgumentOutOfRangeException("索引越界");
131             }
132             EnlargeCapacity();
133             //表示不是在最后的位置进行插入 （index = count 表示最后位置插入）
134             //（index < count 表示中间位置插入）
135             if (index < _count)
136             {
137                 //需要移动元素
138                 Array.Copy(_arrayList, index, _arrayList, index + 1, _count - index);
139             }
140             _arrayList[index] = data;
141             _count++;   //元素个数 加1
142 
143         }
144         public virtual void RemoveAt(int index)
145         {
146             if (index >= _count || index < 0)
147             {
148                 throw new ArgumentOutOfRangeException("索引越界");
149             }
150 
151             if (index < _count - 1) //表示不是删除最后的位置,需要移动 (index=count-1 表示删除的是最后一个位置)
152             {
153                 Array.Copy(_arrayList, index + 1, _arrayList, index, _count - index - 1);
154             }
155             _count--;  //元素个数 减1
156             _arrayList[_count] = null;  //把最后一个元素滞空(无论上面移动与否，都需要把最后一个滞空)
157 
158             //这里暂时不裁剪空间
159         }
160 
161 
162     }

View Code

代码测试，分析内存空间变化

   {
                Console.WriteLine("------------------------------手撸代码测试--------------------------------");
                MyArrayList mylist1 = new MyArrayList(2);
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");//0,2
                mylist1.Add(1);
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}"); //1,2
                mylist1.Add(2);
                mylist1.Add(3);   //3,4
                mylist1.Add(4);   //4,4
                mylist1.Add(5);   //5,8
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");  //5,8
                mylist1.Add(6);
                //mylist1.Add(7);
                mylist1.Insert(6, 7);  //索引为6的位置插入7
                mylist1.Add(8);
                mylist1.Add(9);
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");  //9,16
                mylist1.TrimToSize();  //ArrayList
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");  //9,9
                mylist1.RemoveAt(7);  //删除索引7的元素
                Console.WriteLine($"length:{mylist1.Count},所占内存空间：{mylist1.Capacity}");   //8,9
            }

2. 优缺点总结

优点：

(1).算法简单，描述逻辑关系不需要额外增加内存。

(2).索引访问数据性能更优。

缺点：

(1).空间需要手动分配，不足则溢出;反之，空间闲置浪费。

(2).动态数据解决了空间固定的问题,但是空间浪费，频繁添加数据，会导致存储空间不断重新分配，影响性能。

(3). 删除和插入操作慢，需要数据大范围移动，影响算法速度。

作者 : Yaopengfei(姚鹏飞)
博客地址 : http://www.cnblogs.com/yaopengfei/
声明1 : 如有错误，欢迎讨论，请勿谩骂^_^。
声明2 : 原创博客请在转载时保留原文链接或在文章开头加上本人博客地址，否则保留追究法律责任的权利。