了解集合本质必须要知晓的概念01-链表

古城微笑少年丶 2021-10-19 16:12 311阅读 0赞

如果想对集合(系列)有本质的了解，链表是一个必须了解的概念。本篇主要包括：

● 链表的由来和定义  
● 创建一个单向链表  
● 其它链表

链表的由来和定义

在现实生活中，我们把不同的商品放在一个购物车中。而在面向对象的世界里，有时候，也需要把不同类型的数据放到一起，组成一个集合。集合中的元素并不是彼此孤立的，在C\#中，如何表达集合元素间的关系呢？

借助"自引用类"可以确立集合元素间的关系。比如有这样一个自引用类：

public class Node

{

public int Data{
       get;set;}

public Node Next{
       get;set;}

public Node(int dataValue)

{}

}

Node类的最大特点是：存在一个Node类型的属性，这个属性指向Node的另一个实例，Next属性也称为"引用链"。放到集合的场景中来说就是：把多个Node实例放到一个集合中，每一个Node实例包含一个Next属性指向下一个Node实例。而该集合中的最后一个Node实例会指向null。用图表示就是：

[![1][]][1 1]

> 链表就是自引用类对象的线性集合，即序列。

由于每个自引用对象是由引用链链接起来，所以叫链表。堆栈与队列是约束版的链表，而二叉查找数是非线性数据结构。

链表的节点或元素虽然在逻辑上是连续的、线性的，当其内存不是连续存储的；数组元素在内存中是连续的，所以我们才可以通过索引来访问数组元素。

创建一个单向链表

首先创建一个节点，是一个自引用类：

namespace LinkedListLibrary

{

public class ListNode

{

//当前节点对象

public object Data { get; private set; }

//Next属性也称为链，指向另一个ListNode对象实例，这样就把2个ListNode对象实例链接起来了

public ListNode Next { get; set; }

public ListNode(object dataValue): this(dataValue, null)

{

}

public ListNode(object dataValue, ListNode nextNode)

{

Data = dataValue;

Next = nextNode;

}

再模拟一个链表，如下：

namespace LinkedListLibrary

{

public class List

{

private ListNode firstNode;

private ListNode lastNode;

private string name;

public List(string listName)

{

name = listName;

firstNode = lastNode = null;

}

public List() : this("list"){}

......

//如果第一个节点是null，那就说明集合为空

public bool IsEmpty()

{

return firstNode == null;

}

以上，如果第一个节点为null，那就说明该链表为空。List类提供了IsEmpty方法用来判断链表是否为空。List还包含另外5个重要的方法，下面展开来说。

在链表的的第一个节点前插入。

//在最前面插入元素、节点

public void InsertAtFront(object insertItem)

{

if (IsEmpty())//如果集合为空，加进来一个元素，相当于第一个节点和第二个节点相同，都是新加的元素

{

firstNode = lastNode = new ListNode(insertItem);

}

else //如果集合不为空，第一个节点就是新加的元素,原先的第一个节点变为下一个节点

{

firstNode = new ListNode(insertItem, firstNode);

}

以上，当集合不为空的情况下，实际上是把新添加的节点设为第一个节点，并把新的第一个节点的引用链指向原先的第一个节点。

在链表的最后一个节点后插入。

public void InsertAtBack(object insertItem)

{

if (IsEmpty())//如果原先集合为空，第一个节点和最后一个节点就是新加的节点

{

firstNode = lastNode = new ListNode(insertItem);

}

else//如果原先的集合不为空，最后一个节点的属性值就是新加的节点

{

lastNode = lastNode.Next = new ListNode(insertItem);

}

以上，当集合不为空的情况下，实际上是把新添加的节点设置成最后一个节点，并把新的最后一个节点的引用链指向null。

移除链表最前面的节点。

//移除最前面的元素、节点

//即重新设置第一个节点的Next属性

public object RemoveFromFront()

{

if (IsEmpty())

throw new EmptyListException(name);

//从第一个节点中取出节点对象

object removeItem = firstNode.Data;

if (firstNode == lastNode) //如果集合中只有一个元素

{

firstNode = lastNode = null;

}

else //正常情况下，把firstNode的Next属性所指向的节点赋值给第一个节点

{

firstNode = firstNode.Next;

}

return removeItem;

}

以上，本质是把原先排在第二位置的节点设置成第一个节点。

移除链表最后面的节点。

//移除最后面的元素、节点

public object RemoveFromBack()

{

if (IsEmpty())

{

throw new EmptyListException();

}

//从最后一个节点中获取节点对象

object removeItem = lastNode.Data;

if (firstNode == lastNode)//如果当前集合只有一个节点

{

firstNode = lastNode = null;

}

else

{

//先把第一个节点作为当前节点

ListNode current = firstNode;

//改变除最后一个节点之外的节点的值

while (current.Next != lastNode)

{

current = current.Next;

}

//最后current变成倒数第二个节点

lastNode = current;

current.Next = null;//最后一个节点的Next属性为null，即没有指向另一个节点

}

return removeItem;

}

以上，从第一个节点开始，一直循环到倒数第二个节点，current就像一个指针，每指到一个节点，就把该节点的下面一个节点设置为当前节点。最后，把倒数第二个节点设置为最后一个节点。 把Current的引用链设置为null，让其能被垃圾回收机制回收。

打印链表。

//打印显示

public void Display()

{

if (IsEmpty())

{

Console.WriteLine("集合" + name + "为空");

}

else

{

Console.WriteLine("集合的名称是：" + name);

//先把第一个节点作为当前节点

ListNode current = firstNode;

while (current != null)

{

//把当前节点对象打印出来

Console.Write(current.Data + " ");

//把下一个节点设置为当前节点

current = current.Next;

}

Console.WriteLine("\n");

}

以上，从第一个节点开始，一直循环到最后一个节点，current就像一个指针，每打印一个节点，就把当前节点设置为下一个节点，一直循环下去。

EmptyListException用来抛出链表为空的异常。

namespace LinkedListLibrary

{

public class EmptyListException : Exception

{

public EmptyListException() : base("当前集合为空"){}

public EmptyListException(string name) : base("集合" + name + "为空"){}

public EmptyListException(string exception, Exception inner) : base(exception, inner){}

}

客户端调用：

using LinkedListLibrary;

namespace ListTest

{

class Program

{

static void Main(string[] args)

{

List list = new List();

bool aBoolean = true;

char aChar = 'a';

int anInt = 12;

string aStr = "hi";

list.InsertAtFront(aBoolean);

list.Display();

list.InsertAtFront(aChar);

list.Display();

list.InsertAtBack(anInt);

list.Display();

list.InsertAtBack(aStr);

list.Display();

object removeObject;

try

{

removeObject = list.RemoveFromFront();

Console.WriteLine(removeObject + "被删除了...");

list.Display();

removeObject = list.RemoveFromFront();

Console.WriteLine(removeObject + "被删除了...");

list.Display();

removeObject = list.RemoveFromBack();

Console.WriteLine(removeObject + "被删除了...");

list.Display();

removeObject = list.RemoveFromBack();

Console.WriteLine(removeObject + "被删除了...");

list.Display();

}

catch (EmptyListException emptyListException)

{

Console.Error.WriteLine("\n" + emptyListException);

}

Console.ReadKey();

}

[![2][]][2 1]

其它链表

以上，创建的是单向链表，其特点是第一个节点开始包含引用链，每个节点的引用链指向下一个节点，最后一个节点的引用链为null。单向链表只能从一个方向遍历。

环形单向链表与单向链表的区别是：其最后一个节点的引用链指向第一个节点。环形单向链表也只能从一个方向遍历，只不过遍历到最后一个节点后，又回到第一个节点重新开始遍历。

双向链表的第一个节点只包含指向下一个节点的引用链，最后一个节点只包含指向上一个节点的引用链，其它节点同时包含指向前一个节点和后一个节点的引用链。双向链表支持向前和向后遍历。

环形双向链表与双向链表的区别是：第一个节点向后引用链指向最后一个节点，而最后一个节点的向前引用链指向第一个节点。

参考资料：

Visual C\# 2008大学教程--（第三版）

**“了解集合本质必须要知晓的概念”系列包括：**

### [了解集合本质必须要知晓的概念01-链表][01-] ###

### [了解集合本质必须要知晓的概念02-堆栈][02-] ###

### [了解集合本质必须要知晓的概念03-队列][03-] ###

### [了解集合本质必须要知晓的概念04-二叉查找树][04-] ###

转载于:https://www.cnblogs.com/darrenji/p/3885635.html

[1]: /images/20211019/80031d59f79e41d89826d2803c8a38c1.png
[1 1]: https://images0.cnblogs.com/blog/417212/201408/011824524779091.png
[2]: /images/20211019/d492220a1fe74db496051aa0bfd9a21f.png
[2 1]: https://images0.cnblogs.com/blog/417212/201408/011824529772006.png
[01-]: http://www.cnblogs.com/darrenji/p/3885635.html
[02-]: http://www.cnblogs.com/darrenji/p/3890483.html
[03-]: http://www.cnblogs.com/darrenji/p/3890618.html
[04-]: http://www.cnblogs.com/darrenji/p/3897426.html