玲珑骰子安红豆，入骨相思知不知。
接下来要介绍的几种数据结构,都涉及到一个概念:”节点”,比如单链表,双链表,二叉树,图.基于节点的数据结构,在某些时候具有性能上的独特优势.
首先我们按照从简单到复杂的顺序来,这篇我们介绍第一个基于节点的数据结构:”链表”.
单链表
单链表和数组一样,也是相同数据的一个集合,事实上,数组能做的,单链表同样能做.某些方面而且做的还比数组更好,但是我们也不能知道这个特性就把在使用中的数组全部都用单链表来替换,单链表的实现方式跟数组是不一样的,在不用的场景下,它们的性能也不一样.
我们知道,刚开始讲数组的时候,数组在声明的时候要确定它的长度,计算机好提前规划好连续的空间来存放数据.
比如我们声明了一个长度为4的数组 ,它在内存中的表现如同上表格.而且它的寻找某个值只需要知道下标就能找到这个值,为什么呢?因为这个数组代表它在内存中的地址,知道下标之后直接内存地址+下标,就能立马找到这个值了.
但是单链表与数组不同,它的存储方式并不是连续的.它的开头地址可以是任何地址,它的下一个元素也可以是任意一个地址,这个元素与元素就是”节点”,那么既然不是连续的,按照下标来寻找某个值就走不通了,那么怎么办呢?
这里就要说明一个单链表的一个重要的特性,与数组不同,数组的每个元素里面只存在这个值,其他的什么都不存,但是链表就不一样了,它不仅要存本身的值,还要存下一个元素的地址,那么这与数组相比,单链表的一个元素占用的地方就比数组多了一个.
注:上面一个颜色代表一个元素占用的空间,第一个元素中存的值是1,后面的存着下一个元素的内存地址,通过第一个元素的内存地址找到第二个元素,通过第二个元素中的内存地址再找第三个.如此类推,所以,相同的元素,单链表占用的空间要比数组大一倍.
相对于数组而言,单链表的好处就是它可以将元素放在内存中的任意一个位置,无需事先占用连续的内存空间.但是也有坏处,因为它无法像数组一样立马找到第100位元素,它首先得找到第一个元素,通过第一个元素的指向,找到第二个元素,再根据第二个元素的指向,找到第三个元素,以此类推,一直找到第100号元素.
c#中已经有内置的链表List<T>,但是!注意啊,这个名称虽然叫链表,但是不等同于单链表.虽然它们的名字很像,但是内部实现并不一样,List<T>也叫数组链表,里面有一个数组,那么它与数组有什么关系呢?其实,它的底层结构也是数组,但是它为什么又能动态的分配长度呢?表现的和单链表差不多,其实说到这里就不得不说到ArrayList,这里贴上他们之间各自的区别特性:
一、数组(Array)
数组具有以下的特点：
- 数组属于线性结构，在内存中是连续存放的。
- 数组的元素类型必须相同。
- 数组可以直接通过下标访问。
- 数组的查找速度非常快，新增和删除速度慢。
- 数组在初始化时要指定数组长度。
二、动态数组(ArrayList)
动态数组具有以下的特点：
- ArrayList的底层其实就是一个数组。
- ArrayList在声明时不必指定长度，会根据存储的数据动态的增加或减少长度。
- ArrayList会把所有的元素都当做Object处理，因此可以存储不同数据类型的元素。
- 插入和删除一个元素时，会移动它之后所有元素的位置，效率低，频繁进行插入或者删除元素推荐使用LinkedList。
- ArrayList是非类型安全的，在插入和删除元素时会进行拆箱和装箱问题，影响性能，效率低。
三、泛型List
泛型List具有以下的特点：
- List是ArrayList的泛型类。
- 泛型List需要在声明时指定具体的类型。
- 泛型List没有装箱和拆箱操作，因此List比ArrayList效率高而且类型安全。
那么看到这里就明白了,List是个加强版的ArrayList,而ArrayList从某种角度上来说就是一个可以自由更改长度的数组.说到底List<T>说到底就是一个底层是数组的一个可以动态更改长度的数据结构.
说以它和我们将要讲的单链表除了名字有点像之外,其他没有一点关系.
单链表的增加一个数据,首先找到目标地点,将之前的链接关系断掉.然后再将链接链到新的元素上:
比如要在的元素2和3之间插入一个2.5,那么里面该怎么操作呢?首先通过链表一个一个的链接找到2的位置,然后发现它的连接的是3,但是这里要再加一个2.5,所以,要把这个链接断掉,将2.5随便存在内存中的位置,然后把2这个元素的链接链接到2.5这个元素上,但是这就完了吗?显然没有,因为2.5后面还要链接到3上,所以我们再把2.5后面同样链接上3.
如果要删除一个元素,直接就断开它的链接就好了,比如我们要删除2这个元素.
首先断开1与2的链接,重新把链接链接到2.5的元素上,不用担心内存中还存在的2元素,GC会删除它的.好了,简单的讲解了单链表的原理.
下面就来演示一下单链表的写法:
(以下代码来自于:https://blog.csdn.net/m1234567q/article/details/52584514 ,尊重原创,注明来源)
首先是声明一个泛型类
public class Node<T>
{
private T data; //数据域,当前结点的数据
private Node<T> next; //引用域,即下一结点
//构造器：数据域+引用域，普通结点
public Node(T item, Node<T> p)
{
data = item;
next = p;
}
//构造器：引用域，头结点
public Node(Node<T> p)
{
next = p;
}
//构造器：数据域，尾结点
public Node(T val)
{
data = val;
next = null;
}
//构造器：无参数
public Node()
{
data = default(T);
next = null;
}
//数据域属性
public T Data
{
get
{
return data;
}
set
{
data = value;
}
}
//引用域属性
public Node<T> Next
{
get
{
return next;
}
set
{
next = value;
}
}
}
其次,声明链表类
public class MyLinkList<T>
{
private Node<T> head; //单链表的头结点
//头结点属性
public Node<T> Head
{
get
{
return head;
}
set
{
head = value;
}
}
//构造器
public MyLinkList()
{
head = null;
}
//求单链表的长度
public int GetLength()
{
Node<T> p = head;
int len = ;
while (p != null)
{
++len;
p = p.Next;
}
return len;
}
//清空单链表
public void Clear()
{
head = null;
}
//判断单链表是否为空
public bool IsEmpty()
{
if (head == null)
{
return true;
}
else
{
return false;
}
}
//在单链表的末尾添加新元素
public void Append(T item)
{
Node<T> q = new Node<T>(item);
Node<T> p = new Node<T>();
if (head == null)
{
head = q;
return;
}
p = head;
while (p.Next != null)
{
p = p.Next;
}
p.Next = q;
}
然后是操作的增删改查
//在单链表的第i个结点的位置后插入一个值为item的结点
public void InsertPost(T item, int i)
{
if (IsEmpty() || i < || i >GetLength())
{
Debug.Log("LinkList is empty or Positionis error!");
return;
}
if (i == )
{
Node<T> q = new Node<T>(item);
q.Next = head.Next;
head.Next = q;
return;
}
Node<T> p = head;
int j = ;
while (p != null && j < i)
{
p = p.Next;
++j;
}
if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p.Next;
p.Next = q;
}
}
//删除单链表的第i个结点
public T Delete(int i)
{
if (IsEmpty() || i < || i >GetLength())
{
Debug.Log("LinkList is empty or Positionis error!");
return default(T);
}
Node<T> q = new Node<T>();
if (i == )
{
q = head;
head = head.Next;
return q.Data;
}
Node<T> p = head;
int j = ;
while (p.Next != null && j < i)
{
++j;
q = p;
p = p.Next;
}
if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Debug.Log("The " + i + "th node is not exist!");
return default(T);
}
}
//获得单链表的第i个数据元素
public T GetElem(int i)
{
if (IsEmpty() || i < )
{
Debug.Log("LinkList is empty or positionis error! ");
return default(T);
}
Node<T> p = new Node<T>();
p = head;
int j = ;
while (p.Next != null && j < i)
{
++j;
p = p.Next;
}
if (j == i)
{
return p.Data;
}
else
{
Debug.Log("The " + i + "th node is not exist!");
return default(T);
}
}
//在单链表中查找值为value的结点
public int Locate(T value)
{
if (IsEmpty())
{
Debug.Log("LinkList is Empty!");
return -1;
}
Node<T> p = new Node<T>();
p = head;
int i = ;
while (!p.Data.Equals(value) &&p.Next != null)
{
p = p.Next;
++i;
}
return i;
}
最后是打印链表中的元素
public void Display()
{
Node<T> p = new Node<T>();
p = this.head;
while (p != null)
{
Debug.Log(p.Data + " ");
p = p.Next;
}
}
最后在unity中测试
void Start ()
{
MyLinkList<string> myLinkList = new MyLinkList<string>(); //实例化一个单链表
Debug.Log(myLinkList.GetLength()); //获取长度
//添加元素
myLinkList.Append("good");
myLinkList.Append("monring");
myLinkList.Append("lwk");
myLinkList.Insert("!", ); //在i结点前插元素，位置错误测试
myLinkList.InsertPost("!", ); //在i结点后插元素，位置错误测试
myLinkList.InsertPost("!", ); //后插元素
myLinkList.Insert(",", ); //前插元素
myLinkList.Display(); //显示链表元素
Debug.Log(myLinkList.GetElem());//获取结点,并显示
myLinkList.Delete(); //删除结点
myLinkList.Display();
Debug.Log(myLinkList.GetLength()); //显示链表长度
}
双链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
这个图可能看的比较复杂了,重点体现出它的元素在内存中的无序性,可以发现一个中间的元素,它会有2个指针指向它,前一个元素的尾结点,后一个元素的头结点.那么双链表对与单链表来说,它不仅仅是结构比他复杂,而且空间占用也比单链表的多.那么双链表对于单链表来说,有哪些优势呢?
双链表由链表内的一个点（不是头结点也不是尾结点），可以访问整个链表上的结点；单链表只能访问该点以后的结点，不能向前访问.
看,这就是最大的优点,那么我们要不要再把单链表换成双链表呢?当然不可以了.任何数据结构每个都有每个数据的优势.我已经不止一次说过数据结构要具体问题具体分析,不能看到一个数据结构比较高级,不能见一个用一个.
下面来介绍怎么使用双链表
第一步、定义一个接口
双链表也是线性表的实现之一，所有这个接口和上一篇单链的是一样的
线性表接口定义：线性表的实现有 顺序表、单链表{双向链表、循环链表}
interface IListDs<T>
{
int GetLength();//求长度
void Clear();//清空操作
bool IsEmpty();//判断线性表是否为空
void Add(T item);//添加数据
void Insert(T item, int index);//插入数据
T Delete(int index);//删除数据
T GetElement(int index);//取数据
T this[int index] { get; }//索引器取数据
int Locate(T value);//按照值查找数据
}
第二步、定义存储数据的类
这个类和单链的类是几乎一样的，只是多了一个前引用而已
class DbNode<T>
{
private T data;//储存数据（数据域）
private DbNode<T> prev;//前引用
private DbNode<T> next;//后引用
/// <summary>
/// 构造方法，值和后引用
/// </summary>
/// <param name="value"></param>
/// <param name="dbNode"></param>
public DbNode(T value,DbNode<T> dbNode)
{
data = value;
next = dbNode;
}
/// <summary>
/// 构造方法，后引用
/// </summary>
/// <param name="dbNode"></param>
public DbNode(DbNode<T> dbNode)
{
next = dbNode;
}
/// <summary>
/// 构造方法，值
/// </summary>
/// <param name="value"></param>
public DbNode(T value)
{
data = value;
next = null;
}
/// <summary>
/// 构造方法，默认
/// </summary>
public DbNode()
{
data = default(T);
next = null;
}
/// <summary>
/// 数据属性，可以get和set
/// </summary>
public T Data
{
get { return data; }
set { data = value; }
}
/// <summary>
/// 前引用属性，可以get和set
/// </summary>
public DbNode<T> Prev
{
get { return prev; }
set { prev = value; }
}
/// <summary>
/// 后引用属性，可以get和set
/// </summary>
public DbNode<T> Next
{
get { return next; }
set { next = value; }
}
}
第三步、以双链表的方式实现线性表接口
到这里的实现方式上和单链表有一些区别了，首先我在双链表的实现上加了一个 计数器 和 尾节点储存类，这样做的好出就是，当我需要增、删、改、查 的时候（这些动作都需要先定位到数据），我可以根据计数器的长度判断，我是从表头往后遍历还是从表尾往前遍历，这样其实节省了很大一步的时间在查找数据上相对于单链，因为单链只能选择一个方向，
class DbLinkList<T> : IListDs<T>
{
private DbNode<T> head;//储存头节点
private DbNode<T> tail;//储存尾节点
private int length;//计数器
/// <summary>
/// 无参构造方法
/// </summary>
public DbLinkList()
{
head = null;
tail = new DbNode<T>(default(T));
length = ;
}
/// <summary>
/// 索引器取值
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T this[int index]
{
get { return GetNode(index).Data; }
}
/// <summary>
/// 增加元素
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
DbNode<T> newDbNode = new DbNode<T>(item);
if (head == null)//第一次添加数据
{
//同时给头赋值并和尾建立引用（尾没有值）
head = newDbNode;
head.Next = tail;
tail.Prev = head;
}
else
{
DbNode<T> temp = tail.Prev;//拿到尾节点的前一个
temp.Next = newDbNode;
newDbNode.Prev = temp;
newDbNode.Next = tail;
tail.Prev = newDbNode;
}
length++;
}
/// <summary>
/// 清空表
/// </summary>
public void Clear()
{
head = null;
tail = new DbNode<T>(default(T));
length = ;
}
// 根据下标删除元素
public T Delete(int index)
{
T data;//返回值
if (index == )//下标为头节点
{
data = head.Data;
head = head.Next;
length--;
}
else if (index > GetLength() - || index < )//下标不存在
{
data = default(T);
Console.WriteLine("错误，索引不存在");
}
else//下标存在
{
data = GetNode(index).Data;
DbNode<T> tempPrev = GetNode(index).Prev;
DbNode<T> tempNext = GetNode(index).Next;
tempPrev.Next = tempNext;
tempNext.Prev = tempPrev;
length--;
}
return data;
}
/// <summary>
/// 查找元素
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T GetElement(int index)
{
return GetNode(index).Data;
}
/// <summary>
/// 表长
/// </summary>
/// <returns></returns>
public int GetLength()
{
return length;
}
/// <summary>
/// 插入元素
/// </summary>
/// <param name="item"></param>
/// <param name="index"></param>
public void Insert(T item, int index)
{
DbNode<T> insertDbNode = new DbNode<T>(item);
if (index == )
{
DbNode<T> temp = head;
head = insertDbNode;
temp.Prev = head;
head.Next = temp;
length++;
}
else if (index > GetLength() - )//下标超出调用Add
{
Add(item);
}
else if (index < )
{
Console.WriteLine("错误,索引不存在");
}
else
{
//测试 -1
DbNode<T> temp = GetNode(index);
DbNode<T> tempPrev = GetNode(index).Prev;
temp.Prev = insertDbNode;
tempPrev.Next = insertDbNode;
insertDbNode.Prev = tempPrev;
insertDbNode.Next = temp;
length++;
}
}
/// <summary>
/// 表是是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return GetLength() == ;
}
/// <summary>
/// 返回值对应的下标
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int Locate(T value)
{
for (int i = ; i < GetLength(); i++)
{
if (value.Equals(this[i]))
{
return i;
}
}
Console.WriteLine("值不存在");
return -1;
}
// 返回索引对应的 DbNode ,私有方法，只在类里面使用，
private DbNode<T> GetNode(int index)
{
if (index == )//下标为头节点
{
if (head != null)
{
return head;
}
else
{
Console.WriteLine("数组为空");
return null;
}
}
else if (index == (GetLength() - ))//下标为最后一个
{
return tail.Prev;
}
else if (index > GetLength() - || index < ) //下标为不存在
{
Console.WriteLine("错误索引不存在");
return null;
}
else//下标存在
{
if (index <= (GetLength() / ))//索引在表前半段
{
DbNode<T> temp = head;
for (int i = ; i <= index; i++)//遍历次数等于index
{
temp = temp.Next;
}
return temp;
}
else
{
DbNode<T> temp = tail;
//遍历次数等于 GetLength() - index次（因为你是从tail开始的，他不算长度）
for (int i = GetLength() - index; i > ; i--)
{
temp = temp.Prev;
}
return temp;
}
}
}
}
上面的代码比较重要的就是最后的私有方法DbNode，这是比单链能快速定位到数据的关键
使用双链表
DbLinkList<int> dbLinkList = new DbLinkList<int>();
DateTime beforsSave = System.DateTime.Now;
Console.WriteLine("双链写入开始");
for (int i = ; i < ; i++)
{
dbLinkList.Add(i);
}
Console.WriteLine("双链写入完毕");
DateTime aftersSave = System.DateTime.Now;
TimeSpan saves = aftersSave.Subtract(beforsSave);
Console.WriteLine("双链耗时{0}ms", saves.TotalMilliseconds);
DateTime beforsRead = System.DateTime.Now;
Console.WriteLine("双链读取开始");
for (int i = ; i < (dbLinkList.GetLength() / ); i++)
{
int temp=dbLinkList[i];
}
Console.WriteLine("双链读取完毕");
DateTime aftersRead = System.DateTime.Now;
TimeSpan reads = aftersRead.Subtract(beforsRead);
Console.WriteLine("双链读取耗时{0}ms", reads.TotalMilliseconds);
Console.ReadKey();
(原文链接：https://blog.csdn.net/mars___z/article/details/89412593尊重原创,注明作者)
总结
其实,以上的单双链表在我的工作过程中,并没有太多的涉及,我用的最多的还是List<T>,其实在我们游戏开发中,使用list已经足够我们使用了,但是数据结构的文章必然要介绍,所以我就用网上现成的代码来讲解了,如果你喜欢自己造轮子,可以写在你的工具类中使用.
…END…