链表数据结构
什么是链表？
链表是一种线性数据结构，可以存储通过链接（即指针）连接在一起的"节点"集合。链表节点并非存储在连续的位置，而是使用指向不同内存位置的指针链接起来。节点由数据值和指向链表中下一个节点地址的指针组成。
链表是一种动态线性数据结构，其内存大小可以在运行时根据插入或删除操作进行分配或释放，这有助于高效利用系统内存。链表可用于实现各种数据结构，例如堆栈、队列、图、哈希映射等。
链表以指向第一个节点的头节点开始。每个节点都包含一个 data 指针，该指针保存与该节点相关的实际数据（值），以及一个 next 指针，该指针保存链表中下一个节点的内存地址。链表中的最后一个节点称为尾节点，它指向 null，表示链表结束。
链表与数组
数组的大小在创建时就已确定，因此数组的长度是固定的，而链表的长度是动态的，可以动态地在链表中添加任意数量的节点。数组可以容纳类似类型的数据类型，而链表可以存储不同数据类型的各种节点。
链表的类型
以下是各种类型的链表。
单链表
单链表的一个节点包含两个"桶"；一个桶保存数据，另一个桶保存列表下一个节点的地址。由于同一列表中的两个节点之间只有一条链接，因此只能单向遍历。
双向链表
双向链表的一个节点包含三个"桶"；一个存储桶保存数据，另一个存储桶保存列表中前一个节点和下一个节点的地址。由于列表中的节点从两侧相互连接，因此列表会被遍历两次。
循环链表
循环链表既可以存在于单链表，也可以存在于双向链表中。
由于循环链表的最后一个节点和第一个节点是相连的，因此该链表的遍历将一直持续下去，直到链表断开。
链表的基本操作
链表的基本操作包括插入、删除、查找、显示和删除元素以给定键为基数。这些操作在单链表上执行，如下所示 −
插入 − 在列表开头添加一个元素。
删除 − 删除列表开头的一个元素。
显示 − 显示完整列表。
搜索 − 使用给定键搜索元素。
删除 − 使用给定键删除元素。
链表 - 插入操作
在链表中添加新节点需要多个步骤。我们将通过图表来学习。首先，使用相同的结构创建一个节点，并找到需要插入的位置。
假设我们在 A（左节点）和 C（右节点）之间插入一个节点 B（新节点）。然后将 B 指向 C 的下一个节点 −
新节点.next -> 右节点;
它应该看起来像这样 −
现在，左边的下一个节点应该指向新节点。
LeftNode.next -> NewNode;
这会将新节点置于两者中间。新的列表应该看起来像这样 −
链表中的插入操作可以通过三种不同的方式完成。它们的解释如下 −
在开头插入
在此操作中，我们在列表的开头添加一个元素。
算法1. 开始 2. 创建一个节点来存储数据 3. 检查列表是否为空 4. 如果列表为空，则将数据添加到该节点，并将头指针赋给该节点。 5. 如果列表不为空，则将数据添加到一个节点并链接到 当前头节点。将头指针赋给新添加的节点。 6. 结束示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
printf("
[");
//从头开始
while(p != NULL) {
printf(" %d ",p->data);
p = p->next;
}
printf("]");
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void main(){
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
printf("链接列表： ");
// 打印列表
printList();
}
输出
链接列表： [ 50 44 30 22 12 ]
#include <bits/stdc++.h>
#include <string>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
cout << "
[";
//从头开始
while(p != NULL) {
cout << " " << p->data << " ";
p = p->next;
}
cout << "]";
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
int main(){
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
cout << "链接列表： ";
// 打印列表
printList();
}
输出
链接列表： [ 50 44 30 22 12 ]
public class Linked_List {
static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;
// 显示列表
static void printList() {
node p = head;
System.out.print("
[");
//从头开始
while(p != null) {
System.out.print(" " + p.data + " ");
p = p.next;
}
System.out.print("]");
}
//在开头插入
static void insertatbegin(int data) {
//创建链接
node lk = new node(data);;
// 将其指向旧的第一个节点
lk.next = head;
//将first指向新的第一个节点
head = lk;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
System.out.print("链接列表： ");
// 打印列表
printList();
}
}
输出
链接列表： [50 44 30 22 12 ]
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class SLL:
def __init__(self):
self.head = None
# 打印链接列表
def listprint(self):
printval = self.head
print("链接列表： ")
while printval is not None:
print (printval.data)
printval = printval.next
def AddAtBeginning(self,newdata):
NewNode = Node(newdata)
# 将新节点的下一个值更新为现有节点
NewNode.next = self.head
self.head = NewNode
l1 = SLL()
l1.head = Node("731")
e2 = Node("672")
e3 = Node("63")
l1.head.next = e2
e2.next = e3
l1.AddAtBeginning("122")
l1.listprint()
输出
链接列表： 122 731 672 63
在末尾插入
在此操作中，我们在列表末尾添加一个元素。
算法1. 开始 2. 创建新节点并分配数据 3. 找到最后一个节点 4. 将最后一个节点指向新节点 5. 结束示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
printf("
[");
//从头开始
while(p != NULL) {
printf(" %d ",p->data);
p = p->next;
}
printf("]");
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void insertatend(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
struct node *linkedlist = head;
// 将其指向旧的第一个节点
while(linkedlist->next != NULL)
linkedlist = linkedlist->next;
//将first指向新的第一个节点
linkedlist->next = lk;
}
void main(){
int k=0;
insertatbegin(12);
insertatend(22);
insertatend(30);
insertatend(44);
insertatend(50);
printf("链接列表： ");
// 打印列表
printList();
}
Output
链接列表： [ 12 22 30 44 50 ]
#include <bits/stdc++.h>
#include <string>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
cout << "
[";
//从头开始
while(p != NULL) {
cout << " " << p->data << " ";
p = p->next;
}
cout << "]";
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void insertatend(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
struct node *linkedlist = head;
// 将其指向旧的第一个节点
while(linkedlist->next != NULL)
linkedlist = linkedlist->next;
//将first指向新的第一个节点
linkedlist->next = lk;
}
int main(){
insertatbegin(12);
insertatend(22);
insertatend(30);
insertatend(44);
insertatend(50);
cout << "链接列表： ";
// 打印列表
printList();
}
Output
链接列表： [ 12 22 30 44 50 ]
public class Linked_List {
static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;
// 显示列表
static void printList() {
node p = head;
System.out.print("
[");
//从头开始
while(p != null) {
System.out.print(" " + p.data + " ");
p = p.next;
}
System.out.print("]");
}
//在开头插入
static void insertatbegin(int data) {
//创建链接
node lk = new node(data);;
// 将其指向旧的第一个节点
lk.next = head;
//将first指向新的第一个节点
head = lk;
}
static void insertatend(int data) {
//创建链接
node lk = new node(data);
node linkedlist = head;
// 将其指向旧的第一个节点
while(linkedlist.next != null)
linkedlist = linkedlist.next;
//将first指向新的第一个节点
linkedlist.next = lk;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatend(22);
insertatend(30);
insertatend(44);
insertatend(50);
System.out.print("链接列表： ");
// 打印列表
printList();
}
}
Output
链接列表： [ 12 22 30 44 50 ]
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LL:
def __init__(self):
self.head = None
def listprint(self):
val = self.head
print("链接列表：")
while val is not None:
print(val.data)
val = val.next
l1 = LL()
l1.head = Node("23")
l2 = Node("12")
l3 = Node("7")
l4 = Node("14")
l5 = Node("61")
# 将第一个节点链接到第二个节点
l1.head.next = l2
# 将第二个节点链接到第三个节点
l2.next = l3
l3.next = l4
l4.next = l5
l1.listprint()
输出
链接列表： 23 12 7 14 61
在给定位置插入
在此操作中，我们将在列表的任意位置添加一个元素。
算法1. 开始 2. 创建新节点并为其分配数据 3. 迭代直到找到位置处的节点 4. 指向新的第一个节点 5. 结束示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
printf("
[");
//从头开始
while(p != NULL) {
printf(" %d ",p->data);
p = p->next;
}
printf("]");
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void insertafternode(struct node *list, int data){
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
lk->next = list->next;
list->next = lk;
}
void main(){
int k=0;
insertatbegin(12);
insertatbegin(22);
insertafternode(head->next, 30);
printf("链接列表： ");
// 打印列表
printList();
}
Output
链接列表： [ 22 12 30 ]
#include <bits/stdc++.h>
#include <string>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
cout << "
[";
//从头开始
while(p != NULL) {
cout << " " << p->data << " ";
p = p->next;
}
cout << "]";
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void insertafternode(struct node *list, int data){
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
lk->next = list->next;
list->next = lk;
}
int main(){
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertafternode(head->next,44);
insertafternode(head->next->next, 50);
cout << "链接列表： ";
// 打印列表
printList();
}
Output
链接列表： [ 30 22 44 50 12 ]
public class Linked_List {
static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;
// 显示列表
static void printList() {
node p = head;
System.out.print("
[");
//从头开始
while(p != null) {
System.out.print(" " + p.data + " ");
p = p.next;
}
System.out.print("]");
}
//在开头插入
static void insertatbegin(int data) {
//创建链接
node lk = new node(data);;
// 将其指向旧的第一个节点
lk.next = head;
//将first指向新的第一个节点
head = lk;
}
static void insertafternode(node list, int data) {
node lk = new node(data);
lk.next = list.next;
list.next = lk;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertafternode(head.next, 50);
insertafternode(head.next.next, 33);
System.out.println("链接列表： ");
// 打印列表
printList();
}
}
输出
链接列表： [44 30 50 33 22 12 ]
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class SLL:
def __init__(self):
self.head = None
# 打印链接列表
def listprint(self):
printval = self.head
print("链接列表： ")
while printval is not None:
print (printval.data)
printval = printval.next
# 添加节点的函数
def InsertAtPos(self,nodeatpos,newdata):
if nodeatpos is None:
print("The mentioned node is absent")
return
NewNode = Node(newdata)
NewNode.next = nodeatpos.next
nodeatpos.next = NewNode
l1 = SLL()
l1.head = Node("731")
e2 = Node("672")
e3 = Node("63")
l1.head.next = e2
e2.next = e3
l1.InsertAtPos(l1.head.next, "122")
l1.listprint()
输出
链接列表： 731 672 122 63
链表 - 删除操作
删除操作也是一个多步骤的过程。我们将通过图示来学习。首先，使用搜索算法找到要删除的目标节点。
目标节点的左（上一个）节点现在应该指向目标节点的下一个节点 −
LeftNode.next -> TargetNode.next;
这将删除指向目标节点的链接。现在，使用以下代码，我们将删除目标节点指向的内容。
TargetNode.next -> NULL;
我们需要使用已删除的节点。我们可以将其保留在内存中，否则，我们只需释放内存并完全擦除目标节点即可。
如果将节点插入到列表的开头，也应采取类似的步骤。在链表末尾插入时，链表的倒数第二个节点应指向新节点，而新节点将指向 NULL。
链表的删除操作也有三种不同的方式。具体如下：−
从头删除
在这个链表的删除操作中，我们从链表的开头删除一个元素。为此，我们将头指针指向第二个节点。
算法1. 开始 2. 将头指针赋值给链表中的下一个节点 3. 结束示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
printf("
[");
//从头开始
while(p != NULL) {
printf(" %d ",p->data);
p = p->next;
}
printf("]");
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void deleteatbegin(){
head = head->next;
}
int main(){
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(40);
insertatbegin(55);
printf("链接列表： ");
// 打印列表
printList();
deleteatbegin();
printf("
删除后的链表： ");
// 打印列表
printList();
}
输出
链接列表： [ 55 40 30 22 12 ] 删除后的链表： [ 40 30 22 12 ]
#include <bits/stdc++.h>
#include <string>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
cout << "
[";
//从头开始
while(p != NULL) {
cout << " " << p->data << " ";
p = p->next;
}
cout << "]";
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void deleteatbegin(){
head = head->next;
}
int main(){
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
cout << "链接列表： ";
// 打印列表
printList();
deleteatbegin();
cout << "
删除后的链表： ";
printList();
}
输出
链接列表： [ 50 44 30 22 12 ] 删除后的链表： [ 44 30 22 12 ]
public class Linked_List {
static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;
// 显示列表
static void printList() {
node p = head;
System.out.print("
[");
//从头开始
while(p != null) {
System.out.print(" " + p.data + " ");
p = p.next;
}
System.out.print("]");
}
//在开头插入
static void insertatbegin(int data) {
//创建链接
node lk = new node(data);;
// 将其指向旧的第一个节点
lk.next = head;
//将first指向新的第一个节点
head = lk;
}
static void deleteatbegin() {
head = head.next;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
insertatbegin(33);
System.out.print("链接列表： ");
// 打印列表
printList();
deleteatbegin();
System.out.print("
删除后的链表： ");
// 打印列表
printList();
}
}
输出
链接列表： [ 33 50 44 30 22 12 ] 删除后的链表： [ 50 44 30 22 12 ]
#python 代码使用链接列表从开头进行删除。
from typing import Optional
class Node:
def __init__(self, data: int, next: Optional['Node'] = None):
self.data = data
self.next = next
class LinkedList:
def __init__(self):
self.head = None
#显示列表
def print_list(self):
p = self.head
print("
[", end="")
while p:
print(f" {p.data} ", end="")
p = p.next
print("]")
#在开头插入
def insert_at_begin(self, data: int):
lk = Node(data)
#将其指向旧的第一个节点
lk.next = self.head
#point firt to new first node
self.head = lk
def delete_at_begin(self):
self.head = self.head.next
if __name__ == "__main__":
linked_list = LinkedList()
linked_list.insert_at_begin(12)
linked_list.insert_at_begin(22)
linked_list.insert_at_begin(30)
linked_list.insert_at_begin(44)
linked_list.insert_at_begin(50)
#print list
print("链接列表： ", end="")
linked_list.print_list()
linked_list.delete_at_begin()
print("删除后的链表： ", end="")
linked_list.print_list()
输出
链接列表： [ 50 44 30 22 12 ] 删除后的链表： [ 44 30 22 12 ]
末尾删除
在这个链表的删除操作中，我们从列表末尾删除一个元素。
算法1. 开始 2. 迭代直到找到列表中的倒数第二个元素。 3. 将 NULL 赋给列表中的倒数第二个元素。 4. 结束示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
printf("
[");
//从头开始
while(p != NULL) {
printf(" %d ",p->data);
p = p->next;
}
printf("]");
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void deleteatend(){
struct node *linkedlist = head;
while (linkedlist->next->next != NULL)
linkedlist = linkedlist->next;
linkedlist->next = NULL;
}
void main(){
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(40);
insertatbegin(55);
printf("链接列表： ");
// 打印列表
printList();
deleteatend();
printf("
删除后的链表： ");
// 打印列表
printList();
}
Output
链接列表： [ 55 40 30 22 12 ] 删除后的链表： [ 55 40 30 22 ]
#include <bits/stdc++.h>
#include <string>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
while(p != NULL) {
cout << " " << p->data << " ";
p = p->next;
}
}
// 在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void deleteatend(){
struct node *linkedlist = head;
while (linkedlist->next->next != NULL)
linkedlist = linkedlist->next;
linkedlist->next = NULL;
}
int main(){
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
cout << "链接列表： ";
// 打印列表
printList();
deleteatend();
cout << "
删除后的链表： ";
printList();
}
Output
链接列表： 50 44 30 22 12 删除后的链表： 50 44 30 22
public class Linked_List {
static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;
// 显示列表
static void printList() {
node p = head;
System.out.print("
[");
//从头开始
while(p != null) {
System.out.print(" " + p.data + " ");
p = p.next;
}
System.out.print("]");
}
//在开头插入
static void insertatbegin(int data) {
//创建链接
node lk = new node(data);;
// 将其指向旧的第一个节点
lk.next = head;
//将first指向新的第一个节点
head = lk;
}
static void deleteatend() {
node linkedlist = head;
while (linkedlist.next.next != null)
linkedlist = linkedlist.next;
linkedlist.next = null;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
insertatbegin(33);
System.out.print("链接列表： ");
// 打印列表
printList();
//deleteatbegin();
deleteatend();
System.out.print("
删除后的链表： ");
// 打印列表
printList();
}
}
Output
链接列表： [ 33 50 44 30 22 12 ] 删除后的链表： [ 33 50 44 30 22 ]
#python 代码使用链接列表从开头进行删除。
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
#显示列表
def printList(self):
p = self.head
print("
[", end="")
while p != None:
print(" " + str(p.data) + " ", end="")
p = p.next
print("]")
#在开头插入
def insertatbegin(self, data):
#创建链接
lk = Node(data)
#将其指向旧的第一个节点
lk.next = self.head
#指向新的第一个节点
self.head = lk
def deleteatend(self):
linkedlist = self.head
while linkedlist.next.next != None:
linkedlist = linkedlist.next
linkedlist.next = None
if __name__ == "__main__":
linked_list = LinkedList()
linked_list.insertatbegin(12)
linked_list.insertatbegin(22)
linked_list.insertatbegin(30)
linked_list.insertatbegin(40)
linked_list.insertatbegin(55)
#print list
print("链接列表： ", end="")
linked_list.printList()
linked_list.deleteatend()
print("删除后的链表： ", end="")
linked_list.printList()
输出
链接列表： [ 55 40 30 22 12 ] 删除后的链表： [ 55 40 30 22 ]
在给定位置删除
在这个链表的删除操作中，我们删除链表中任意位置的元素。
算法1. 开始 2. 迭代直到找到链表中当前位置的节点。 3. 将链表中当前节点的相邻节点赋值给其前一个节点。 4. 结束示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
printf("
[");
//从头开始
while(p != NULL) {
printf(" %d ",p->data);
p = p->next;
}
printf("]");
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void deletenode(int key){
struct node *temp = head, *prev;
if (temp != NULL && temp->data == key) {
head = temp->next;
return;
}
// 找到要删除的键
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// 如果键不存在
if (temp == NULL) return;
// 删除节点
prev->next = temp->next;
}
void main(){
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(40);
insertatbegin(55);
printf("链接列表： ");
// 打印列表
printList();
deletenode(30);
printf("
删除后的链表： ");
// 打印列表
printList();
}
输出
链接列表： [ 55 40 30 22 12 ] 删除后的链表： [ 55 40 22 12 ]
#include <bits/stdc++.h>
#include <string>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
cout << "
[";
//从头开始
while(p != NULL) {
cout << " " << p->data << " ";
p = p->next;
}
cout << "]";
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void deletenode(int key){
struct node *temp = head, *prev;
if (temp != NULL && temp->data == key) {
head = temp->next;
return;
}
// 找到要删除的键
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// 如果键不存在
if (temp == NULL) return;
// 删除节点
prev->next = temp->next;
}
int main(){
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
cout << "链接列表： ";
// 打印列表
printList();
deletenode(30);
cout << "
删除后的链表： ";
printList();
}
输出
链接列表： [ 50 44 30 22 12 ] 删除后的链表： [ 50 44 22 12 ]
public class Linked_List {
static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;
// 显示列表
static void printList() {
node p = head;
System.out.print("
[");
//从头开始
while(p != null) {
System.out.print(" " + p.data + " ");
p = p.next;
}
System.out.print("]");
}
//在开头插入
static void insertatbegin(int data) {
//创建链接
node lk = new node(data);;
// 将其指向旧的第一个节点
lk.next = head;
//将first指向新的第一个节点
head = lk;
}
static void deletenode(int key) {
node temp = head;
node prev = null;
if (temp != null && temp.data == key) {
head = temp.next;
return;
}
// 找到要删除的键
while (temp != null && temp.data != key) {
prev = temp;
temp = temp.next;
}
// 如果键不存在
if (temp == null) return;
// 删除节点
prev.next = temp.next;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
insertatbegin(33);
System.out.print("链接列表： ");
// 打印列表
printList();
//deleteatbegin();
//deleteatend();
deletenode(12);
System.out.print("
删除后的链表： ");
// 打印列表
printList();
}
}
输出
链接列表： [ 33 50 44 30 22 12 ] 删除后的链表： [ 33 50 44 30 22 ]
#使用链接列表在给定位置进行删除的 Python 代码。
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# 显示列表
def printList(self):
p = self.head
print("
[", end="")
#从头开始
while(p != None):
print(" ", p.data, " ", end="")
p = p.next
print("]")
#在开头插入
def insertatbegin(self, data):
#创建链接
lk = Node(data)
# 将其指向旧的第一个节点
lk.next = self.head
#指向新的第一个节点
self.head = lk
def deletenode(self, key):
temp = self.head
if (temp != None and temp.data == key):
self.head = temp.next
return
# 找到要删除的键
while (temp != None and temp.data != key):
prev = temp
temp = temp.next
# If the key is not present
if (temp == None):
return
# 删除节点
prev.next = temp.next
llist = LinkedList()
llist.insertatbegin(12)
llist.insertatbegin(22)
llist.insertatbegin(30)
llist.insertatbegin(40)
llist.insertatbegin(55)
print("原始链表：", end="")
# print list
llist.printList()
llist.deletenode(30)
print("删除后的链表： ", end="")
# print list
llist.printList()
输出
原始链表： [ 55 40 30 22 12 ] 删除后的链表： [ 55 40 22 12 ]
链表 - 反转操作
此操作非常复杂。我们需要让头节点指向链表的尾节点，并反转整个链表。
首先，我们遍历到链表的末尾。它应该指向 NULL。现在，我们让它指向它的前一个节点 -
我们必须确保尾节点不是真正的尾节点。因此，我们会设置一个临时节点，看起来像是头节点指向尾节点。现在，我们将使所有左侧节点逐一指向其前一个节点。
除头节点指向的节点（第一个节点）外，所有节点都应指向其前一个节点，使其成为新的后继节点。第一个节点将指向 NULL。
我们将使用临时节点将头节点指向新的首节点。
算法
反转链表的步骤如下 −
1. START 2. 我们使用三个指针执行反转： prev、next、head。 3. 将当前节点指向 head，并将其下一个值赋给 prev 节点。 4. 对列表中的所有节点重复步骤 3。 5. 将 head 赋值给 prev 节点。
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
printf("
[");
//从头开始
while(p != NULL) {
printf(" %d ",p->data);
p = p->next;
}
printf("]");
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void reverseList(struct node** head){
struct node *prev = NULL, *cur=*head, *tmp;
while(cur!= NULL) {
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
*head = prev;
}
void main(){
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(40);
insertatbegin(55);
printf("链接列表： ");
// 打印列表
printList();
reverseList(&head);
printf("
反向链表： ");
printList();
}
输出
链接列表： [ 55 40 30 22 12 ] 反向链表： [ 12 22 30 40 55 ]
#include <bits/stdc++.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
printf("
[");
//从头开始
while(p != NULL) {
printf(" %d ",p->data);
p = p->next;
}
printf("]");
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void reverseList(struct node** head){
struct node *prev = NULL, *cur=*head, *tmp;
while(cur!= NULL) {
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
*head = prev;
}
int main(){
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(40);
insertatbegin(55);
printf("链接列表： ");
// 打印列表
printList();
reverseList(&head);
printf("
反向链表： ");
printList();
return 0;
}
输出
链接列表： [ 55 40 30 22 12 ] 反向链表： [ 12 22 30 40 55 ]
public class Linked_List {
static Node head;
static class Node {
int data;
Node next;
Node (int value) {
data = value;
next = null;
}
}
// 显示列表
static void printList(Node node) {
System.out.print("
[");
//从头开始
while(node != null) {
System.out.print(" " + node.data + " ");
node = node.next;
}
System.out.print("]");
}
static Node reverseList(Node head) {
Node prev = null;
Node cur = head;
Node temp = null;
while (cur != null) {
temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
head = prev;
return head;
}
public static void main(String args[]) {
Linked_List list = new Linked_List();
list.head = new Node(33);
list.head.next = new Node(50);
list.head.next.next = new Node(44);
list.head.next.next.next = new Node(22);
list.head.next.next.next.next = new Node(12);
System.out.print("链接列表： ");
// 打印列表
list.printList(head);
head = list.reverseList(head);
System.out.print("
Reversed linked list ");
list.printList(head);
}
}
Output
链接列表： [ 33 50 44 22 12 ] Reversed linked list [ 12 22 44 50 33 ]
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class SLL:
def __init__(self):
self.head = None
# 打印链接列表
def listprint(self):
printval = self.head
print("链接列表： ")
while printval is not None:
print (printval.data)
printval = printval.next
def reverse(self):
prev = None
curr = self.head
while(curr is not None):
next = curr.next
curr.next = prev
prev = curr
curr = next
self.head = prev
l1 = SLL()
l1.head = Node("731")
e2 = Node("672")
e3 = Node("63")
l1.head.next = e2
e2.next = e3
l1.listprint()
l1.reverse()
print("反转后：")
l1.listprint()
输出
链接列表： 731 672 63 反转后： 链接列表： 63 672 731
链表 - 搜索操作
使用键值元素在列表中搜索元素。此操作与数组搜索相同；将列表中的每个元素与给定的键值元素进行比较。
算法
1 开始 2 如果列表不为空，则迭代检查列表 是否包含键值 3 如果键值元素不在列表中，则搜索失败 4 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
printf("
[");
//从头开始
while(p != NULL) {
printf(" %d ",p->data);
p = p->next;
}
printf("]");
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
int searchlist(int key){
struct node *temp = head;
while(temp != NULL) {
if (temp->data == key) {
return 1;
}
temp=temp->next;
}
return 0;
}
void main(){
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(40);
insertatbegin(55);
printf("链接列表： ");
// 打印列表
printList();
int ele = 30;
printf("
要搜索的元素是： %d", ele);
k = searchlist(30);
if (k == 1)
printf("
Element is found");
else
printf("
Element is not found in the list");
}
输出
链接列表： [ 55 40 30 22 12 ] 要搜索的元素是： 30 Element is found
#include <bits/stdc++.h>
#include <string>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
cout << "
[";
//从头开始
while(p != NULL) {
cout << " " << p->data << " ";
p = p->next;
}
cout << "]";
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
int searchlist(int key){
struct node *temp = head;
while(temp != NULL) {
if (temp->data == key) {
return 1;
}
temp=temp->next;
}
return 0;
}
int main(){
int k = 0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
cout << "链接列表： ";
// 打印列表
printList();
int ele = 16;
cout<<"
要搜索的元素是： "<<ele;
k = searchlist(ele);
if (k == 1)
cout << "
Element is found";
else
cout << "
Element is not found in the list";
}
输出
链接列表： [ 50 44 30 22 12 ] 要搜索的元素是： 16 Element is not found in the list
public class Linked_List {
static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;
// 显示列表
static void printList() {
node p = head;
System.out.print("
[");
//从头开始
while(p != null) {
System.out.print(" " + p.data + " ");
p = p.next;
}
System.out.print("]");
}
//在开头插入
static void insertatbegin(int data) {
//创建链接
node lk = new node(data);;
// 将其指向旧的第一个节点
lk.next = head;
//将first指向新的第一个节点
head = lk;
}
static int searchlist(int key) {
node temp = head;
while(temp != null) {
if (temp.data == key) {
return 1;
}
temp=temp.next;
}
return 0;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
insertatbegin(33);
System.out.print("链接列表： ");
// 打印列表
printList();
int ele = 44;
System.out.print("
要搜索的元素是： " + ele);
k = searchlist(ele);
if (k == 1)
System.out.println("
Element is found");
else
System.out.println("
Element is not found in the list");
}
}
输出
链接列表： [ 33 50 44 30 22 12 ] 要搜索的元素是： 44 Element is found
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class SLL:
def listprint(self):
printval = self.head
print("链接列表： ")
while printval is not None:
print (printval.data)
printval = printval.next
def __init__(self):
self.head = None
def search(self, x):
count = 0
# Initialize current to head
current = self.head
# 循环直到当前不等于 None
while current != None:
if current.data == x:
print("Element is found")
count = count + 1
current = current.next
if count == 0:
print("Element is not found in the list")
l1 = SLL()
l1.head = Node("731")
e2 = Node("672")
e3 = Node("63")
l1.head.next = e2
e2.next = e3
l1.listprint()
ele = "63"
print("要搜索的元素是： ", ele);
l1.search(ele)
输出
链接列表： 731 672 63 要搜索的元素是： 63 Element is found
链表 - 遍历操作
遍历操作按顺序遍历列表中的所有元素，并按该顺序显示这些元素。
算法
1. 开始 2. 当列表不为空且未到达列表末尾时， 打印每个节点中的数据 3. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
printf("
[");
//从头开始
while(p != NULL) {
printf(" %d ",p->data);
p = p->next;
}
printf("]");
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void main(){
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
printf("链接列表： ");
// 打印列表
printList();
}
输出
链接列表： [ 30 22 12 ]
#include <bits/stdc++.h>
#include <string>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
while(p != NULL) {
cout << " " << p->data << " ";
p = p->next;
}
}
// 在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
int main(){
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
cout << "链接列表： ";
// 打印列表
printList();
}
输出
链接列表： 50 44 30 22 12
public class Linked_List {
static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;
// 显示列表
static void printList() {
node p = head;
System.out.print("
[");
//从头开始
while(p != null) {
System.out.print(" " + p.data + " ");
p = p.next;
}
System.out.print("]");
}
//在开头插入
static void insertatbegin(int data) {
//创建链接
node lk = new node(data);;
// 将其指向旧的第一个节点
lk.next = head;
//将first指向新的第一个节点
head = lk;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
insertatbegin(33);
System.out.print("链接列表： ");
// 打印列表
printList();
}
}
输出
链接列表： [ 33 50 44 30 22 12 ]
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class SLL:
def __init__(self):
self.head = None
# 打印链接列表
def listprint(self):
printval = self.head
print("链接列表： ")
while printval is not None:
print (printval.data)
printval = printval.next
l1 = SLL()
l1.head = Node("731")
e2 = Node("672")
e3 = Node("63")
l1.head.next = e2
e2.next = e3
l1.listprint()
输出
链接列表： 731 672 63
链表 - 完整实现
以下是各种编程语言中链表的完整实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
printf("
[");
//从头开始
while(p != NULL) {
printf(" %d ",p->data);
p = p->next;
}
printf("]");
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void insertatend(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
struct node *linkedlist = head;
// 将其指向旧的第一个节点
while(linkedlist->next != NULL)
linkedlist = linkedlist->next;
//将first指向新的第一个节点
linkedlist->next = lk;
}
void insertafternode(struct node *list, int data){
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
lk->next = list->next;
list->next = lk;
}
void deleteatbegin(){
head = head->next;
}
void deleteatend(){
struct node *linkedlist = head;
while (linkedlist->next->next != NULL)
linkedlist = linkedlist->next;
linkedlist->next = NULL;
}
void deletenode(int key){
struct node *temp = head, *prev;
if (temp != NULL && temp->data == key) {
head = temp->next;
return;
}
// 找到要删除的键
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// 如果键不存在
if (temp == NULL) return;
// 删除节点
prev->next = temp->next;
}
int searchlist(int key){
struct node *temp = head;
while(temp != NULL) {
if (temp->data == key) {
return 1;
}
temp=temp->next;
}
return 0;
}
void main(){
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatend(30);
insertatend(44);
insertatbegin(50);
insertafternode(head->next->next, 33);
printf("链接列表： ");
// 打印列表
printList();
deleteatbegin();
deleteatend();
deletenode(12);
printf("
删除后的链表： ");
// 打印列表
printList();
insertatbegin(4);
insertatbegin(16);
printf("
更新后的链接列表： ");
printList();
k = searchlist(16);
if (k == 1)
printf("
Element is found");
else
printf("
Element is not present in the list");
}
输出
链接列表： [ 50 22 12 33 30 44 ] 删除后的链表： [ 22 33 30 ] 更新后的链接列表： [ 16 4 22 33 30 ] Element is found
#include <bits/stdc++.h>
#include <string>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
// 显示列表
void printList(){
struct node *p = head;
cout << "
[";
//从头开始
while(p != NULL) {
cout << " " << p->data << " ";
p = p->next;
}
cout << "]";
}
//在开头插入
void insertatbegin(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
// 将其指向旧的第一个节点
lk->next = head;
//将first指向新的第一个节点
head = lk;
}
void insertatend(int data){
//创建链接
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
struct node *linkedlist = head;
// 将其指向旧的第一个节点
while(linkedlist->next != NULL)
linkedlist = linkedlist->next;
//将first指向新的第一个节点
linkedlist->next = lk;
}
void insertafternode(struct node *list, int data){
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
lk->next = list->next;
list->next = lk;
}
void deleteatbegin(){
head = head->next;
}
void deleteatend(){
struct node *linkedlist = head;
while (linkedlist->next->next != NULL)
linkedlist = linkedlist->next;
linkedlist->next = NULL;
}
void deletenode(int key){
struct node *temp = head, *prev;
if (temp != NULL && temp->data == key) {
head = temp->next;
return;
}
// 找到要删除的键
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// 如果键不存在
if (temp == NULL) return;
// 删除节点
prev->next = temp->next;
}
int searchlist(int key){
struct node *temp = head;
while(temp != NULL) {
if (temp->data == key) {
temp=temp->next;
return 1;
} else
return 0;
}
return key;
}
int main(){
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatend(30);
insertatend(44);
insertatbegin(50);
insertafternode(head->next->next, 33);
cout << "链接列表： ";
// 打印列表
printList();
deleteatbegin();
deleteatend();
deletenode(12);
cout << "
删除后的链表： ";
// 打印列表
printList();
insertatbegin(4);
insertatbegin(16);
cout << "
更新后的链接列表： ";
printList();
k = searchlist(16);
if (k == 1)
cout << "
Element is found";
else
cout << "
Element is not present in the list";
return 0;
}
输出
链接列表： [ 50 22 12 33 30 44 ] 删除后的链表： [ 22 33 30 ] 更新后的链接列表： [ 16 4 22 33 30 ] Element is found
public class Linked_List {
static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;
// 显示列表
static void printList() {
node p = head;
System.out.print("
[");
//从头开始
while(p != null) {
System.out.print(" " + p.data + " ");
p = p.next;
}
System.out.print("]");
}
//在开头插入
static void insertatbegin(int data) {
//创建链接
node lk = new node(data);;
// 将其指向旧的第一个节点
lk.next = head;
//将first指向新的第一个节点
head = lk;
}
static void insertatend(int data) {
//创建链接
node lk = new node(data);
node linkedlist = head;
// 将其指向旧的第一个节点
while(linkedlist.next != null)
linkedlist = linkedlist.next;
//将first指向新的第一个节点
linkedlist.next = lk;
}
static void insertafternode(node list, int data) {
node lk = new node(data);
lk.next = list.next;
list.next = lk;
}
static void deleteatbegin() {
head = head.next;
}
static void deleteatend() {
node linkedlist = head;
while (linkedlist.next.next != null)
linkedlist = linkedlist.next;
linkedlist.next = null;
}
static void deletenode(int key) {
node temp = head;
node prev = null;
if (temp != null && temp.data == key) {
head = temp.next;
return;
}
// 找到要删除的键
while (temp != null && temp.data != key) {
prev = temp;
temp = temp.next;
}
// 如果键不存在
if (temp == null) return;
// 删除节点
prev.next = temp.next;
}
static int searchlist(int key) {
node temp = head;
while(temp != null) {
if (temp.data == key) {
temp=temp.next;
return 1;
}
}
return 0;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatend(30);
insertatend(44);
insertatbegin(50);
insertafternode(head.next.next, 33);
System.out.print("链接列表： ");
// 打印列表
printList();
deleteatbegin();
deleteatend();
deletenode(12);
System.out.print("
删除后的链表： ");
// 打印列表
printList();
insertatbegin(4);
insertatbegin(16);
System.out.print("
更新后的链接列表： ");
printList();
k = searchlist(16);
if (k == 1)
System.out.print("
Element is found");
else
System.out.print("
Element is not present in the list");
}
}
输出
链接列表： [ 50 22 12 33 30 44 ] 删除后的链表： [ 22 33 30 ] 更新后的链接列表： [ 16 4 22 33 30 ] Element is found
class LLNode:
def __init__(self, data=None):
self.data = data
self.next = None
class LL:
def __init__(self):
self.head = None
def listprint(self):
printval = self.head
while printval is not None:
print(printval.data)
printval = printval.next
def AddAtBeginning(self,newdata):
NewNode = LLNode(newdata)
# 将新节点的下一个值更新为现有节点
NewNode.next = self.head
self.head = NewNode
# 在某个位置添加节点的函数
def InsertAtPos(self,nodeatpos,newdata):
if nodeatpos is None:
print("The mentioned node is absent")
return
NewNode = LLNode(newdata)
NewNode.next = nodeatpos.next
nodeatpos.next = NewNode
def reverse(self):
prev = None
curr = self.head
while(curr is not None):
next = curr.next
curr.next = prev
prev = curr
curr = next
self.head = prev
def search(self, x):
count = 0
# Initialize current to head
current = self.head
# 循环直到当前不等于 None
while current != None:
if current.data == x:
print("Element is found")
count = count + 1
current = current.next
if count == 0:
print("Element is not found in the list")
l1 = LL()
l1.head = LLNode("23")
l2 = LLNode("12")
l3 = LLNode("7")
l4 = LLNode("14")
l5 = LLNode("61")
# 将第一个节点链接到第二个节点
l1.head.next = l2
# 将第二个节点链接到第三个节点
l2.next = l3
l3.next = l4
l4.next = l5
print("原始链表：")
l1.listprint()
l1.AddAtBeginning("45")
l1.InsertAtPos(l1.head.next.next, "4")
print("更新后的链接列表：")
l1.listprint()
l1.reverse()
print("反向链表：")
l1.listprint()
l1.search("7")
输出
原始链表： 23 12 7 14 61 更新后的链接列表： 45 23 12 4 7 14 61 反向链表： 61 14 7 4 12 23 45 Element is found
