链表算法数据结构及图（单项、双项）

terry 2年前 (2023-09-27) 阅读数 64 #数据结构与算法

数组是软件开发过程中非常重要的数据结构，但数组至少有两个限制：

元素大小必须在编译时确定
数组在内存中是连续的。插入或删除需要移动字段中的其他数据

字段适合处理对插入或删除不敏感的一定长度的数据。如果数据变化频繁，则需要选择其他数据结构。链表是一种逻辑简单且实用的数据结构，几乎所有编程语言都支持。我们从最简单的链条结构开始，根据需求的变化逐步完善，以满足产品的需求。

1。单向链表

单向链表由节点组成。每个节点都是一组信息，包括元素本身和下一个节点的地址。节点在内存中不连续分布。程序运行过程中可以根据需要动态创建节点。这对链表的长度没有逻辑限制。限制的是堆的大小。在单向链表中，每个节点存储下一个节点的地址，如下所示：

其实我们更关心的是基于数据结构的算法。链表是一种简单的数据组织方法，适合于中等量的数据，我们只能探索添加、删除和搜索链表。对于更复杂的流量需求，最好使用更高级的数据结构。

首先定义一个链表：

#ifndef INT_LINKED_LIST
#define INT_LINKED_LIST

class Node {
public:
	//构造函数，创建一个节点
	Node(int el = 0, Node* ptr = nullptr) {
		info = el;
		next = ptr;
	}
	//节点的值
	int info;
	//下一个节点地址
	Node* next;
};

class NodeList {
public:
	//构造函数，创建一个链表，用于管理节点
	NodeList() {
		head = tail = nullptr;
	}
	//节点插入到头部
	void addToHead(int);
	//节点插入到尾部
	void addToTail(int);
	//删除头部节点
	int  deleteFromHead();
	//删除尾部节点
	int  deleteFromTail();
	//删除指定节点
	void deleteNode(int);
private:
	//头指针、尾指针
	Node *head, *tail;
};

#endif
复制代码

这里有两个类用来表示节点和管理节点的链表。其中，节点有两个成员变量，分别是当前节点的值和指向下一个节点的指针。链表还有两个成员变量，分别指向头节点和尾节点。链表class有5个成员方法，分别表示添加、删除和搜索节点。我们来看看这三个操作在链表上的表现。

单向链表的操作相对简单。这里没有使用代码，而是直接使用动画，这样更容易理解。

假设现有一个链表如下：

向头部插入一个节点

向头部插入节点的逻辑比较简单，算法的复杂度可以在一个时间内完成固定时间O(1),这意味着无论链表中有多少个节点，这个函数执行的操作次数永远不会超过某个常数c.注意这个操作的实现取决于指针head。否则无法确定主节点的地址，算法的复杂度会大大增加。

节点插入尾部

尾部插入节点的逻辑与插入头部类似。算法的复杂度也是O(1)。不同的是，这个操作的实现依赖于指针tail，否则无法确定端节点地址，算法复杂度会显着增加。

删除头节点

头节点删除操作的算法复杂度也是O(1)。这个操作依赖于指针head，通过head指针可以直接获取下一个节点的地址，所以复杂度很低。

删除终端节点

注意，终端节点删除算法的复杂度为O(n)，是之前

❙大小的两倍。这是因为我们需要一个临时指针 p 从起始节点到倒数第二个节点。因为删除尾节点后，尾指针需要向头节点的方向移动一次，但在链表中无法直接获取倒数第二个节点的地址，只能依靠遍历，这就造成了算法上升到 O(n)。单向链表没有更好的解决方案。后面我们需要改进链表的结构来避免这种情况。

删除指定节点

删除指定节点的算法复杂度也不尽如人意。在最好的情况下，需要 O(1) 时间，在最坏的平均情况下，需要 O(n)。通过动态图我们可以看到，我们定义了指针P指向目标节点，节点Q指向目标节点的前驱节点。这两个变量的作用是纠正单向链表的方向，缺一不可。

一些基于单向链表的操作的算法复杂度无法满足我们的需求。主要适用于末端节点的删除和指定节点的删除。它们的平均复杂度达到O(n)，相比于O(1)，增加了两个数量级。为了改进算法，我们需要修改链表的结构。对于删除一个末端节点，瓶颈是我们无法直接获取该末端节点的前驱地址。我们可以通过在节点中添加一个指向前一个节点的指针来解决这个问题。这就是所谓的双向链表。

2。双向链表

双向链表看起来像这样：

首先，定义：

#ifndef INT_LINKED_LIST
#define INT_LINKED_LIST

class Node {
public:
	//构造函数，创建一个节点
	Node(int el = 0, Node* p = nullptr, Node* q = nullptr) {
		info = el;
                pre  = p;
		next = q;
	}
	//节点的值
	int info;
        //前一个节点地址
        Node* pre;
	//下一个节点地址
	Node* next;
};

class NodeList {
public:
	//构造函数，创建一个链表，用于管理节点
	NodeList() {
		head = tail = nullptr;
	}
	//节点插入到头部
	void addToHead(int);
	//节点插入到尾部
	void addToTail(int);
	//删除头部节点
	int  deleteFromHead();
	//删除尾部节点
	int  deleteFromTail();
	//删除指定节点
	void deleteNode(int);
private:
	//头指针、尾指针
	Node *head, *tail;
};

#endif复制代码

基于双向链表的操作与单链表非常相似。我们从单链表扩展了双链表。，目的是改进删除端节点的算法。

删除终端节点

可以看到终端节点删除算法的复杂度已经降低到O(1)。事实上，指针pre不仅简化了尾节点的删除，其他O(1)的操作也被简化了，因为有了‼，就不需要了定义任何临时指针。

即便如此，我们还是增加了空间的利用，以减少时间消耗。本质上，这是一种空间与时间的交换。对于现代软件开发来说，硬件不再是主要瓶颈，一些空间成本是值得的。

也许有人知道所谓的循环单向链表和循环双向链表。这些是什么？

循环单向链表与单向链表的区别：

区别在于下一个结束节点指针指向循环中的主节点。此时头指针可能不存在。如果继续定义头指针，只会更加方便，但不再不可或缺。

循环双向链表与双向链表的区别：

同理，根据需要添加指针head。循环链表和普通链表没有太大区别，可以根据自己的需要进行选择。

到目前为止，我们还有一个问题没有解决，那就是删除指定节点。这个操作本质上是一个搜索问题。为了优化搜索算法，我们需要不断改变链表的结构。其实上面的链表已经足够满足需求了，因为我们假设对象是中等量的数据，O(n)级别的操作是可以接受的，而对于更复杂的数据，需要更复杂的数据结构。有了学习的机会，你就可以继续你的学业。毕竟，俗话说得好——积累越多，收获越多。

作者：BackSlash
来源：掘金