顺序存储结构

Array

• 引用类型（托管堆）
• 初始化时需要设置默认值
• 实现自己的ArrayList

   1 using System;  2 using System.Collections.Generic;  3 using System.Linq;  4 using System.Text;  5  6 namespace ConsoleAppMyArrayList  7 {  8 public class MyArrayList  9  {  10 //容量  11 private const int _defaultCapacity = 4;  12 //存放数组元素  13 private object[] _items;  14 //数组大小  15 private int _size;  16 //元素个数为0的数组状态  17 private static readonly object[] emptyArray = new object[0];  18  19 public MyArrayList()  20  {  21 this._items = emptyArray;  22  }  23  24 public MyArrayList( int capacity)  25  {  26 if (capacity<0)  27  {  28 throw new ArgumentOutOfRangeException(nameof(capacity),"ArrayList的容量不可为负数！");  29  }  30 this._items = new object[capacity];  31  }  32  33 //索引器  34 public virtual object this[int index]  35  {  36 get  37  {  38 if (index<0||index>=this._size)  39  {  40 throw new ArgumentOutOfRangeException(nameof(index),"索引超出范围！");  41  }  42 return this._items[index];  43  }  44  45 set  46  {  47 if (index < 0 || index >= this._size)  48  {  49 throw new ArgumentOutOfRangeException(nameof(index), "索引超出范围！");  50  }  51 this._items[index] = value;  52  }  53  54  }  55  56 //当前数组元素个数  57 public virtual int Count  58  {  59 get { return this._size ;}  60  }  61  62 //数组的容量  63 public virtual int Capacity  64  {  65 get { return this._items.Length; }  66 set  67  {  68 if (value!=this._items.Length)  69  {  70 if (value<this._size)  71  {  72 throw new ArgumentOutOfRangeException(nameof(value),"容量太小");  73  }  74 if (value > 0)  75 { //开辟新内存空间存储元素  76 object[] dest = new object[value];  77 if (this._size > 0)  78 { //搬动元素  79 Array.Copy(this._items, 0, dest, 0, this._size);  80  }  81 this._items = dest;  82  }  83 else//数组最小的空间为4  84  {  85 this._items=new object[_defaultCapacity];  86  }  87  }  88  }  89  }  90  91 //元素的添加  92 public virtual int Add(object value)  93 { //当空间已满  94 if (this._size==this._items.Length)  95  {  96 this.EnsureCapacity(this._size+1);  97  }  98 this._items[this._size] = value;  99 return this._size++; 100  } 101 102 //扩容 103 private void EnsureCapacity(int p) 104  { 105 if (this._items.Length<p) 106 { //空间加倍 107 int num = (this._items.Length == 0) ? _defaultCapacity : (this._items.Length * 2); 108 if (num < p) 109  { 110 num = p; 111  } 112 this.Capacity = num; 113  } 114  } 115 116 //指定位置插入元素 117 public virtual void Insert( int index,object value) 118  { 119 if (index<0||index>this._size) 120  { 121 throw new ArgumentOutOfRangeException(nameof(index),"索引超出范围！"); 122  } 123 if (this._size==this._items.Length) 124  { 125 this.EnsureCapacity(this._size + 1); 126  } 127 if (index<this._size) 128  { 129 Array.Copy(this._items, index, this._items, index + 1, this._size - index); 130  } 131 this._items[index] = value; 132 this._size++; 133  } 134 135 //移除指定索引的元素 136 public virtual void Remove(int index) 137  { 138 if (index < 0 || index > this._size) 139  { 140 throw new ArgumentOutOfRangeException(nameof(index), "索引超出范围！"); 141  } 142 this._size--; 143 if (index<this._size) 144  { 145 Array.Copy(this._items,index+1,this._items,index,this._size-index); 146  } 147 this._items[this._size]=null; 148  } 149 150 //裁剪空间 151 public virtual void TrimToSize() 152  { 153 this.Capacity = this._size; 154  } 155  } 156 }

   

链式存储结构

链表

1. 单向链表

2. 循环链表

   • 实现自己的循环链表

      1 using System;  2  3 namespace ConsoleAppLinked  4 {  5 class CirculLinkedList  6  {  7 //元素个数  8 private int count;  9  10 //尾指针  11 private Node tail;  12  13 //当前节点的前节点  14 private Node CurrPrev;  15  16  17 //增加元素  18 public void Add(object value)  19  {  20 Node newNode = new Node(value);  21 if (tail==null)  22 { //链表为空  23 tail = newNode;  24 tail.next = newNode;  25 CurrPrev = newNode;  26  }  27 else  28 { //链表不为空，把元素增加到链表结尾  29 newNode.next = tail.next;  30 tail.next = newNode;  31  32 if (CurrPrev==tail)  33  {  34 CurrPrev = newNode;  35  }  36 tail = newNode;  37  }  38 count++;  39  }  40  41 //删除当前元素  42 public void RemoveCurrNode()  43  {  44 //为null代表为空表  45 if (tail == null)  46  {  47 throw new NullReferenceException("集合中没有任何元素！");  48  }  49 else if (count==1)  50  {  51 tail = null;  52 CurrPrev = null;  53  }  54 else  55  {  56 if (CurrPrev.next==tail)  57  {  58 tail = CurrPrev;  59  }  60 CurrPrev.next = CurrPrev.next.next;  61  }  62 count--;  63  }  64  65 //当前节点移动步数  66 public void Move(int step)  67  {  68 if (step<0)  69  {  70 throw new ArgumentOutOfRangeException("step", "移动步数不可为负数！");  71  }  72 if (tail==null)  73  {  74 throw new NullReferenceException("链表为空！");  75  }  76 for (int i = 0; i < step; i++)  77  {  78 CurrPrev = CurrPrev.next;  79  }  80  }  81  82 //获得当前节点  83 public object Current  84  {  85 get { return CurrPrev.next.item ;}  86  }  87  88 public override string ToString()  89  {  90 if (tail==null)  91  {  92 return string.Empty;  93  }  94 string s = "";  95 Node temp = tail.next;  96 for (int i = 0; i < count; i++)  97  {  98 s += temp.ToString() + " ";  99 temp = temp.next; 100  } 101 return s; 102  } 103 104 105 public int Count 106  { 107 get { return count ;} 108  } 109 110 private class Node 111  { 112 public Node(object value) 113  { 114 item = value; 115  } 116 //放置数据 117 public object item; 118 public CirculLinkedList.Node next; 119 public override string ToString() 120  { 121 return item.ToString(); 122  } 123  } 124  } 125 }

      

3. 双向链表