简介
数据结构的本质，只有两种结构，数组与链表。其它的都是它的衍生与组合算法的本质就是穷举。
数组
数组可以分为两大类，静态数组与动态数组。静态数组的本质是一段连续的内存，因为是连续的，所以我们可以采用偏移量的方式来对元素实现快速访问。而动态数组则是对静态数组的封装，使得更加方便操作元素。有了动态数组，后续的栈，哈希，队列都能更加优雅的实现。
静态数组
数组的超能力随机访问。只要任意一个索引，都能推测出元素的内存地址，而计算机的内存寻址能力为 Log(1),所以数组的随机访问时间复杂度也同样为 Log(1)
数组的局限性由于数组的大小是固定的，所以当数组满了，或者需要在中间插入/删除时。都需要移动元素，这时候时间复杂度就上升为 Log(N)
动态数组
动态数组无法解决静态数组 Log(N)的问题，它只是帮你隐藏了动态扩容与元素搬移的过程，以及更加易用的 API。
数组随机访问的超能力源于数组连续的内存空间，而连续的内存空间就不可避免地面对元素搬移和扩缩容的问题
一个简单的动态数组
public class MyList<T>() { //真正存储数据的底层 private T[] arr = new T[5]; //记录元素的数量 public int Count { get; private set; }
/// <summary> /// 增 /// </summary> /// <param name="item"></param> public void Add(T item) { if (Count == arr.Length) { //扩容 Resize(Count * 2); }
arr[Count] = item; Count++; } /// <summary> /// 删 /// </summary> /// <param name="idx"></param> public void RemoveAt(int idx) { if (Count == arr.Length / 4) { //缩容 Resize(arr.Length / 2); } Count--; for (int i = idx; i < Count; i++) { arr[i] = arr[i + 1]; } arr[Count] = default(T); } public void Remove(T item) { var idx = FindIndex(item); RemoveAt(idx); }
/// <summary> /// 改 /// </summary> /// <param name="idx"></param> /// <param name="newItem"></param> public void Put(int idx,T newItem) { arr[idx] = newItem; }
/// <summary> /// 查 /// </summary> /// <param name="item"></param> /// <returns></returns> public int FindIndex(T item) { for(int i = 0; i < arr.Length; i++) { if (item.Equals(arr[i])) return i; }
return -1; } /// <summary> /// 扩容/缩容操作 /// </summary> /// <param name="initCapacity"></param> private void Resize(int initCapacity) { var newArray=new T[initCapacity];
for(var i = 0; i < Count; i++) { newArray[i] = arr[i]; }
arr = newArray; } }
复制代码
数组的变种：环形数组
有人可能会问了？数组不是一段连续的内存吗？怎么可能是环形的？从物理角度出发，这确实不可能。但从逻辑角度出发，这是有可能的。其核心内容就是利用求模运算
public static void Run() { var arr = new int[] { 1, 2, 3, 4, 5, 6 }; var i = 0; while (arr.Length > 0) { Console.WriteLine(arr[i]); //关键代码在此，当i遍历到末尾时，i+1与arr.Length去余数变成0 //从逻辑上完成了闭环 i = (i + 1) % arr.Length;
if ((i % arr.Length) == 0) { Console.WriteLine("完成了一次循环，i归零"); Thread.Sleep(1000); } } }
复制代码
环形数组的关键在于，它维护了两个指针 start 和 end，start 指向第一个有效元素的索引，end 指向最后一个有效元素的下一个位置索引环形数组解决了什么问题？数组在头部增删从 O(N)，优化为 O(1)
链表
链表分为单链表与双链表，单链表只有一个指针，指向 next 元素。双链表有两个指针，分别指向 previous 与 next。除此之外并无其它区别。主要功能区别在于能否向前遍历。
为什么需要链表
前面说到，数组的本质是一段连续的内存，当元素移动/扩容时，需要 one by one 移动，花销很大。那有没有一种能突破内存限制的数据结构呢？链表就应运而生。链表不需要连续内存，它们可以分配在天南海北，它们之间的联系靠 next/prev 链接，将零散的元素串成一个链式结构。
这么做有两个好处
提高内存利用率，分配在哪都可以。所以可以降低内存碎片
方便扩容与移动，只需要重新指向 next/previous 即可实现增，删，改等操作，无需移动元素与扩容。
但万物皆有代价，因为链表的不连续性，所以无法利用快速随机访问来定位元素，只能一个一个的遍历来确定元素。因此链表的查询复杂度为 Log(N)
一个简单的链表
public class MyLinkedList<T>{ public static void Run() { var linked = new MyLinkedList<string>();
linked.AddLast("a"); linked.AddLast("b"); linked.AddLast("c"); linked.AddLast("d");
linked.Add(1, "bc"); linked.Put(1, "aaaa"); Console.WriteLine(linked.ToString()) ; } /// <summary> /// 虚拟头尾节点,有两个好处 /// 1.无论链表是否为空， 两个虚拟节点都存在，避免很多边界值处理的情况。 /// 2.如果要在尾部插入数据，如果不知道尾节点，那么需要复杂度退化成O(N),因为要从头开始遍历到尾部。 /// </summary> private Node _head, _tail; public int Count { get; private set; }
public MyLinkedList() { _tail = new Node(); _head = new Node();
_head.Next = _tail; _tail.Prev = _head; }
public void AddLast(T item) { var prev = _tail.Prev; var next = _tail; var node = new Node(item);
node.Next = next; node.Prev = prev;
prev.Next = node; next.Prev = node;
Count++; }
public void AddFirst(T item) { var prev = _head; var next = _head.Next; var node=new Node(item);
node.Prev= prev; node.Next= next;
prev.Next= node; next.Prev = node;
Count++; }
public void Add(int idx,T item) { var t = Get(idx); var next = t.Next; var prev = t;
var node = new Node(item); node.Next = next; node.Prev = prev;
prev.Next = node; next.Prev = node;
}
public void Remove(int idx) { var t = Get(idx);
var prev = t.Prev; var next = t.Next;
prev.Next = next; next.Prev = next;
t = null; Count--; }
public void Put(int idx,T item) { var t = Get(idx); t.Value= item; }
private Node? Get(int idx) { var node = _head.Next; //这里有个优化空间，可以通过idx在Count的哪个区间。从而决定从head还是从tail开始遍历 for (int i = 0; i < idx; i++) { node = node.Next; } return node; }
public override string ToString() { var sb = new StringBuilder(); var node = _head.Next; while (node != null && node.Value != null) { sb.Append($"{node.Value}<->"); node = node.Next; } sb.Append("null"); return sb.ToString(); } private class Node { public T? Value { get; set; } public Node Next { get; set; } public Node Prev { get; set; }
public Node() { Value=default(T); } public Node(T value) { Value = value; } }}
复制代码
链表的变种：跳表
在上面简单的例子中，查询的复杂度为 O(N),插入的复杂度为 O(1).主要消耗在查询操作，只能从头结点开始，逐个遍历到目标节点。所以我们优化的重点就在于优化查询。
上面的例子中，我们使用了虚拟头尾节点来空间换时间，提高插入效率。同样的，我们也可以采用这个思路来提高查询效率
跳表核心原理
index 0 1 2 3 4 5 6 7 8 9node a->b->c->d->e->f->g->h->i->j
复制代码
此时此刻，你想拿到 h 的节点，你需要从0开始遍历直到7。这时候你就想，如果我能提前知道 6 的位置就好了，这样我就只需要 Next 就能快速得到h
调表就是如此
indexLevel 0-----------------------8-----10indexLevel 0-----------4-----------8-----10indexLevel 0-----2-----4-----6-----8-----10indexLevel 0--1--2--3--4--5--6--7--8--9--10nodeLevel 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)有点类似自平衡的二叉搜索数，不过相对来说比较简单。
文章转载自：叫我安不理
原文链接：https://www.cnblogs.com/lmy5215006/p/18736066
体验地址：http://www.jnpfsoft.com/?from=001YH
评论