我要评论
链表是由节点组成的动态数据结构，每个节点都包含数据和指向下一个节点的指针。与数组不同，链表不需要连续内存，因此非常适合动态调整大小。
初始节点（称为 head）用作遍历的起点。相比之下，虽然数组具有固定大小，但链表允许实时修改大小。它们的非连续内存分配可最大限度地提高存储效率，尤其是在连续内存不可用时。值得注意的是，链表在插入和删除操作方面表现出色，在恒定时间内执行它们，与以线性时间执行这些任务的数组形成鲜明对比。
什么是单向链表？
单向链表是通用链表的一种特殊情况。在单向链表中，每个节点只链接到序列中的下一个节点，即如果我们从列表的第一个节点开始遍历，我们只能朝一个方向移动（双关语）。
除了数据之外，单向链表的 node 只存储下一个元素的地址，如下所示。以下是节点的 java 表示形式。
class node{
int data;
node next;
}
对于链表，我们维护一个特殊的指针，称为 s head。此指针存储列表的第一个节点的地址。此外，最后一个节点不能再有下一个元素。因此，我们通过将 null 分配给链表的下一个来指示链表的末尾。
单向链表上的操作
1. 插入
可以通过以下方式在单向链表中插入：
- 开始时插入在单向链表的开头插入新节点按以下方式执行。
- 使新节点指向 head。
- 使 head 指向新节点。
在开始时插入一个新节点是一个 o（1） 操作。
void insertatstart(node newnode, node head){
newnode.data = 10;
newnode.next = head;
head.next = newnode;
}
- 在某个节点之后插入在单向链表中的某个节点之后插入新节点按以下方式执行：
- 到达所需的节点，在此之后将插入新节点。
- 使新节点指向当前节点的下一个元素。
- 使当前节点指向新节点。 在某个节点之后插入一个新节点是 o（n） 操作。
void insertaftertargetnode(node newnode, node head, int target){
newnode.data = 10;
node temp = head;
while(temp.data != target){
temp = temp.next;
}
newnode.next = temp.next;
temp.next = newnode;
}
- 最后插入在单向链表的末尾插入一个新节点是以以下方式执行的，
- 从头开始刷新列表并到达最后一个节点。
- 使最后一个节点指向新节点。
- 使新节点指向 null，标记列表的末尾。 在末尾插入新节点是 o（n） 操作。
void insertatend(node newnode, node head){
newnode.data = 10;
node temp = head;
while(temp.next != null){
temp = temp.next;
}
temp.next = newnode;
newnode.next = null;
}
2. 删除
单向链表中的删除可以通过以下方式执行：
-
开始时
删除 单向链表的第一个节点可以按如下方式删除，- 使 head 指向其下一个元素。
删除单向链表的第一个节点是 o（1） 操作。
void deleteatfirst(node head){
head = head.next;
}
- 中间删除
特定节点后的删除可以通过以下方式形成，
- 到达所需的节点，之后将删除该节点。
- 使当前节点指向下一个元素的下一个。
在特定节点之后删除节点是 o（n） 操作。
void deleteaftertarget(node head, int target){
node temp = head;
while(temp.data != target){
temp = temp.next;
}
temp.next= temp.next.next;
}
- 最后删除
最后一个节点的删除按以下方式执行：
- 到达 ssingle linke list 的倒数第二个节点。
- 使倒数第二个节点点为空。
删除最后一个节点是 o（n） 操作。
void deletelast(node head){
node temp = head;
while(temp.next.next != null){
temp = temp.next;
}
temp.next = null;
}
3. 显示
为了显示整个单向链表，我们需要从头到尾遍历它。
与数组相比，链表节点不能随机访问。因此，要到达第 n 个元素，我们必然要遍历所有 （n-1） 个元素。
由于遍历了整个链表，因此该操作会花费我们 o（n） 的时间复杂度。以下 java 代码段显示了如何显示整个单向链表。
void display(node head){
node temp = head;
while(temp != null){
system.out.println(temp.data);
temp = temp.next;
}
}
4. 搜索
要搜索单向链表中的元素，我们需要从一开始就遍历链表。
在每个节点上，我们执行查找以确定是否已找到目标，如果是，则返回目标节点，否则我们将移动到下一个元素。
在最坏的情况下，我们最终可能会访问列表中的所有节点，因此在单向链表中搜索元素会花费我们 o（n） 的操作时间。
node search(node head, int target){
node temp = head;
while(temp != null && temp.data != target){
temp = temp.next;
}
return temp;
}
我们能做得更好吗？
假设整个单向链表已经按升序方式排序。我们可以在链表上应用二进制搜索并在 o（log n） 时间内完成我们的搜索操作吗？
事实证明，我们不能，即使链表已经排序，我们也无法对它执行二进制搜索。二进制搜索对集合起作用的重要事项之一是，集合的任何位置都必须在恒定时间内随机访问。数组遵循此属性，因为我们可以在恒定时间内专门访问任何数组元素。
但是，对于链表，这种随机访问是被禁止的。单向链表的任何元素都只能按顺序访问，这使得二进制搜索完全无效。
链表的用途
链表的一些实际应用如下：
- 用于存储单变量或双变量多项式。
- 充当某些数据结构（如队列、堆栈、图形）的基础。
- 按操作系统划分的文件分配方案的策略。
- 跟踪辅助磁盘中的可用空间。所有可用空间都可以链接在一起。
- 回合制游戏可以使用循环链表来决定将要玩哪个玩家。一旦玩家完成回合，我们就会进入下一个玩家。
- 保留音乐、视频、图像、网页等相互链接并允许在它们之间按顺序遍历的项目的记录。
结论
在本文中，我们探讨了单向链表的整个新世界。我们讨论了它的起源原因并研究了它的代表性。遍历了它的所有操作和好处，我们终于承认了它的一些实际应用。
发表评论