重生之数据结构与算法----数组&链表

简介

数据结构的本质，只有两种结构，数组与链表。其它的都是它的衍生与组合
算法的本质就是穷举。
数组

数组可以分为两大类，静态数组与动态数组。
静态数组的本质是一段连续的内存，因为是连续的，所以我们可以采用偏移量的方式来对元素实现快速访问。
而动态数组则是对静态数组的封装，使得更加方便操作元素。有了动态数组，后续的栈，哈希，队列都能更加优雅的实现。
静态数组

• 数组的超能力
  随机访问。只要任意一个索引，都能推测出元素的内存地址，而计算机的内存寻址能力为Log(1),所以数组的随机访问时间复杂度也同样为Log(1)
  
• 数组的局限性
  由于数组的大小是固定的，所以当数组满了，或者需要在中间插入/删除时。都需要移动元素，这时候时间复杂度就上升为Log(N)
  

动态数组

动态数组无法解决静态数组Log(N)的问题，它只是帮你隐藏了动态扩容与元素搬移的过程，以及更加易用的API。

数组随机访问的超能力源于数组连续的内存空间，而连续的内存空间就不可避免地面对元素搬移和扩缩容的问题

一个简单的动态数组

1. public class MyList<T>()
2.    
3. {
4.     //真正存储数据的底层
5.     private T[] arr = new T[5];
6.     //记录元素的数量
7.     public int Count { get; private set; }
11.     /// <summary>
12.     /// 增
13.     /// </summary>
14.     /// <param name="item"></param>
15.     public void Add(T item)
16.     {
17.         if (Count == arr.Length)
18.         {
19.             //扩容
20.             Resize(Count * 2);
21.         }
23.         arr[Count] = item;
24.         Count++;
25.     }
26.     /// <summary>
27.     /// 删
28.     /// </summary>
29.     /// <param name="idx"></param>
30.     public void RemoveAt(int idx)
31.     {
32.         if (Count == arr.Length / 4)
33.         {
34.             //缩容
35.             Resize(arr.Length / 2);
36.         }
37.         Count--;
38.         for (int i = idx; i < Count; i++)
39.         {
40.             arr[i] = arr[i + 1];
41.         }
42.         
43.         arr[Count] = default(T);
44.         
45.     }
46.     public void Remove(T item)
47.     {
48.         var idx = FindIndex(item);
49.         RemoveAt(idx);
50.     }
52.     /// <summary>
53.     /// 改
54.     /// </summary>
55.     /// <param name="idx"></param>
56.     /// <param name="newItem"></param>
57.     public void Put(int idx,T newItem)
58.     {
59.         arr[idx] = newItem;
60.     }
62.     /// <summary>
63.     /// 查
64.     /// </summary>
65.     /// <param name="item"></param>
66.     /// <returns></returns>
67.     public int FindIndex(T item)
68.     {
69.         for(int i = 0; i < arr.Length; i++)
70.         {
71.             if (item.Equals(arr[i]))
72.                 return i;
73.         }
75.         return -1;
76.     }
77.    
78.     /// <summary>
79.     /// 扩容/缩容操作
80.     /// </summary>
81.     /// <param name="initCapacity"></param>
82.     private void Resize(int initCapacity)
83.     {
84.         var newArray=new T[initCapacity];
86.         for(var i = 0; i < Count; i++)
87.         {
88.             newArray[i] = arr[i];
89.         }
91.         arr = newArray;
92.     }
93.    
94. }

复制代码

数组的变种：环形数组

有人可能会问了？数组不是一段连续的内存吗？怎么可能是环形的？
从物理角度出发，这确实不可能。但从逻辑角度出发，这是有可能的。
其核心内容就是利用求模运算

1.         public static void Run()
2.         {
3.             var arr = new int[] { 1, 2, 3, 4, 5, 6 };
4.             var i = 0;
5.             while (arr.Length > 0)
6.             {
7.                 Console.WriteLine(arr[i]);
8.                 //关键代码在此，当i遍历到末尾时，i+1与arr.Length去余数变成0
9.                 //从逻辑上完成了闭环
10.                 i = (i + 1) % arr.Length;
13.                 if ((i % arr.Length) == 0)
14.                 {
15.                     Console.WriteLine("完成了一次循环，i归零");
16.                     Thread.Sleep(1000);
17.                 }
18.             }
19.         }

复制代码

环形数组的关键在于，它维护了两个指针 start 和 end，start 指向第一个有效元素的索引，end 指向最后一个有效元素的下一个位置索引
环形数组解决了什么问题？数组在头部增删从O(N)，优化为O(1)

一个简单的环形数组

点击查看代码

1.     public class CircularArray<T>: IEnumerable<T>
2.     {
3.         public static void Run()
4.         {
5.             var arr = new CircularArray<string>();
6.             arr.AddLast("4");
7.             arr.AddLast("5");
8.             arr.AddFirst("3");
9.             arr.AddFirst("2");
10.             arr.AddFirst("1");
12.             foreach (var item in arr)
13.             {
14.                 Console.WriteLine(item);
15.             }
16.         }
19.         private T[] _array;
20.         private int _head;
21.         private int _tail;
22.         public int Count { get; private set; }
23.         public int Capacity { get; private set; }
25.         public CircularArray()
26.         {
27.             var capacity = 10;
28.             _array = new T[capacity];
29.             _head = 0;
30.             _tail = 0;
31.             Count = 0;
32.             Capacity = capacity;
33.         }
35.         /// <summary>
36.         /// 扩容/缩容
37.         /// </summary>
38.         /// <param name="capacity"></param>
39.         private void Resize(int capacity)
40.         {
41.             var newArr=new T[capacity];
43.             for(int i=0; i < Count; i++)
44.             {
45.                 newArr[i] = _array[(_head + i) % Capacity];
46.             }
47.             _array = newArr;
49.             //重置指针
50.             _head = 0;
51.             _tail = Count;
52.             Capacity = capacity;
53.         }
55.         /// <summary>
56.         /// 在头部添加元素
57.         /// O(1)
58.         /// </summary>
59.         /// <param name="item"></param>
60.         public void AddFirst(T item)
61.         {
62.             if (Count == Capacity)
63.             {
64.                 Resize(Capacity * 2);
65.             }
67.             _head = (_head - 1 + Capacity) % Capacity;
68.             _array[_head] = item;
69.             Count++;
70.         }
72.         /// <summary>
73.         /// 在尾部添加元素
74.         /// </summary>
75.         /// <param name="item"></param>
76.         public void AddLast(T item)
77.         {
78.             if (Count == Capacity)
79.             {
80.                 Resize(Capacity * 2);
81.             }
83.             _array[_tail] = item;
84.             _tail = (_tail + 1) % Capacity;
86.             Count++;
87.         }
89.         /// <summary>
90.         /// 在尾部删除
91.         /// </summary>
92.         public void RemoveLast()
93.         {
94.             _tail = (_tail - 1 + Capacity) % Capacity;
95.             _array[_tail] = default;
96.             Count--;
97.         }
99.         /// <summary>
100.         /// 在头部删除
101.         /// </summary>
102.         public void RemoveFirst()
103.         {
104.             _array[_head] = default;
105.             _head = (_head + 1) % Capacity;
106.             Count--;
107.         }
110.         /// <summary>
111.         /// 获取头部元素
112.         /// </summary>
113.         /// <returns></returns>
114.         public T GetFirst()
115.         {
116.             return _array[_head];
117.         }
119.         /// <summary>
120.         /// 获取尾部元素
121.         /// </summary>
122.         /// <returns></returns>
123.         public T GetLast()
124.         {
125.             return _array[(_tail - 1 + Capacity) % Capacity];
126.         }
128.         public T Get(int idx)
129.         {
130.             return _array[idx];
131.         }
134.         public IEnumerator<T> GetEnumerator()
135.         {
136.             for (int i = 0; i < Count; i++)
137.             {
139.                 var index = (_head + i) % Capacity;
140.                 yield return _array[index];
141.             }
142.         }
144.         IEnumerator IEnumerable.GetEnumerator()
145.         {
146.             return GetEnumerator();
147.         }
148.     }

复制代码

链表

链表分为单链表与双链表，单链表只有一个指针，指向next元素。双链表有两个指针，分别指向previous与next。
除此之外并无其它区别。主要功能区别在于能否向前遍历。
为什么需要链表

前面说到，数组的本质是一段连续的内存，当元素移动/扩容时，需要one by one 移动，花销很大。
那有没有一种能突破内存限制的数据结构呢？链表就应运而生。链表不需要连续内存，它们可以分配在天南海北，它们之间的联系靠next/prev链接，将零散的元素串成一个链式结构。
这么做有两个好处

• 提高内存利用率，分配在哪都可以。所以可以降低内存碎片
  
• 方便扩容与移动，只需要重新指向next/previous 即可实现增，删，改等操作，无需移动元素与扩容。
  

但万物皆有代价，因为链表的不连续性，所以无法利用快速随机访问来定位元素，只能一个一个的遍历来确定元素。因此链表的查询复杂度为Log(N)
一个简单的链表

1. public class MyLinkedList<T>
2. {
3.     public static void Run()
4.     {
5.         var linked = new MyLinkedList<string>();
7.         linked.AddLast("a");
8.         linked.AddLast("b");
9.         linked.AddLast("c");
10.         linked.AddLast("d");
13.         linked.Add(1, "bc");
14.         linked.Put(1, "aaaa");
15.         Console.WriteLine(linked.ToString()) ;
16.     }
17.     /// <summary>
18.     /// 虚拟头尾节点,有两个好处
19.     /// 1.无论链表是否为空， 两个虚拟节点都存在，避免很多边界值处理的情况。
20.     /// 2.如果要在尾部插入数据，如果不知道尾节点，那么需要复杂度退化成O(N),因为要从头开始遍历到尾部。
21.     /// </summary>
22.     private Node _head, _tail;
23.     public int Count { get; private set; }
25.     public MyLinkedList()
26.     {
27.         _tail = new Node();
28.         _head = new Node();
30.         _head.Next = _tail;
31.         _tail.Prev = _head;
32.     }
34.     public void AddLast(T item)
35.     {
36.         var prev = _tail.Prev;
37.         var next = _tail;
38.         var node = new Node(item);
40.         node.Next = next;
41.         node.Prev = prev;
43.         prev.Next = node;
44.         next.Prev = node;
46.         Count++;
47.     }
49.     public void AddFirst(T item)
50.     {
51.         var prev = _head;
52.         var next = _head.Next;
53.         var node=new Node(item);
55.         node.Prev= prev;
56.         node.Next= next;
58.         prev.Next= node;
59.         next.Prev = node;
61.         Count++;
62.     }
64.     public void Add(int idx,T item)
65.     {
66.         var t = Get(idx);
67.         var next = t.Next;
68.         var prev = t;
70.         var node = new Node(item);
71.         node.Next = next;
72.         node.Prev = prev;
74.         prev.Next = node;
75.         next.Prev = node;
77.     }
79.     public void Remove(int idx)
80.     {
81.         var t = Get(idx);
83.         var prev = t.Prev;
84.         var next = t.Next;
86.         prev.Next = next;
87.         next.Prev = next;
89.         t = null;
90.         Count--;
91.     }
93.     public void Put(int idx,T item)
94.     {
95.         var t = Get(idx);
96.         t.Value= item;
97.     }
99.     private Node? Get(int idx)
100.     {
101.         var node = _head.Next;
102.         //这里有个优化空间，可以通过idx在Count的哪个区间。从而决定从head还是从tail开始遍历
103.         for (int i = 0; i < idx; i++)
104.         {
105.             node = node.Next;
106.         }
107.         return node;
108.     }
109.    
111.     public override string ToString()
112.     {
113.         var sb = new StringBuilder();
114.         var node = _head.Next;
115.         while (node != null && node.Value != null)
116.         {
117.             sb.Append($"{node.Value}<->");
118.             node = node.Next;
119.         }
120.         sb.Append("null");
121.         return sb.ToString();
122.     }
123.     private class Node
124.     {
125.         public T? Value { get; set; }
126.         public Node Next { get; set; }
127.         public Node Prev { get; set; }
129.         public Node()
130.         {
131.             Value=default(T);
132.         }
133.         public Node(T value)
134.         {
135.             Value = value;
136.         }
137.     }
138. }

复制代码

链表的变种：跳表

在上面简单的例子中，查询的复杂度为O(N),插入的复杂度为O(1).
主要消耗在查询操作，只能从头结点开始，逐个遍历到目标节点。
所以我们优化的重点就在于优化查询。
上面的例子中，我们使用了虚拟头尾节点来空间换时间，提高插入效率。同样的，我们也可以采用这个思路来提高查询效率
跳表核心原理

1. index  0  1  2  3  4  5  6  7  8  9
2. node   a->b->c->d->e->f->g->h->i->j

复制代码

此时此刻，你想拿到h的节点，你需要从0开始遍历直到7。
这时候你就想，如果我能提前知道6的位置就好了，这样我就只需要Next就能快速得到h
调表就是如此

1. indexLevel   0-----------------------8-----10
2. indexLevel   0-----------4-----------8-----10
3. indexLevel   0-----2-----4-----6-----8-----10
4. indexLevel   0--1--2--3--4--5--6--7--8--9--10
5. nodeLevel    a->b->c->d->e->f->g->h->i->j->k

复制代码

调表在原链表的基础上，增加了多层索引，每向上一层，索引减少一半，所以索引的高度是O(log N)

• 首先从最高层索引开始往下搜，索引7在[0,8]区间
  
• 从节点0开始，发现7在【4,8】，拿到节点4的地址
  
• 从节点4开始，发现7在【6,8】，拿到节点6的地址
  
• 从节点6开始，发现7在【6,7】，最终找到节点7
  

在搜索的过程中，会经过O(log N)层索引，所以时间复杂度为O(log N)

调表实现比较复杂，当新增与删除时，还需考虑索引的动态调整，需要保证尽可能的二分，否则时间复杂度又会退化为O(N)
有点类似自平衡的二叉搜索数，不过相对来说比较简单。

一个简单的跳表

挖坑待埋

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！