跳到主要内容

链表操作：遍历、插入和删除

提示
  1. 基本操作：链表操作包括遍历（访问每个元素）、插入（添加新元素）、删除（移除元素）、搜索（查找节点）和排序（对节点进行排序）。
  2. 插入元素：可以在链表的开始、中间或末尾插入新元素，具体方法取决于插入位置。
  3. 删除元素：同样，从链表中删除元素可以在开始、末尾或特定位置进行，删除方法依赖于目标位置。

链表操作让我们能够在链表上执行不同的动作。例如，插入操作可以在链表中添加一个新元素。

这里是我们将在本文中介绍的一些基本链表操作。

  • 遍历 - 访问链表的每个元素
  • 插入 - 向链表添加新元素
  • 删除 - 移除现有元素
  • 搜索 - 在链表中查找节点
  • 排序 - 对链表的节点进行排序

在详细了解链表操作之前，请确保首先了解链表。

关于链表的注意事项​

  • head 指向链表的第一个节点
  • 最后一个节点的 next 指针是 NULL，所以如果下一个当前节点是 NULL，我们就到达了链表的末尾。

在所有示例中，我们假设链表有三个节点 1 --->2 --->3，节点结构如下所示：

struct node {
  int data;
  struct node *next;
};

遍历链表​

显示链表内容非常简单。我们持续将 temp 节点移动到下一个，并显示其内容。

当 temp 是 NULL 时，我们知道已经到达链表的末尾，所以跳出 while 循环。

struct node *temp = head;
printf("\n\n链表元素为 - \n");
while(temp != NULL) {
  printf("%d --->",temp->data);
  temp = temp->next;
}

该程序的输出将是：

链表元素为 -
1 --->2 --->3 --->

向链表中插入元素​

你可以将元素添加到链表的开始、中间或末尾。

1. 在开始处插入​

  • 为新节点分配内存
  • 存储数据
  • 改变新节点的 next 指向 head
  • 改变 head 指向最近创建的节点
struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = head;
head = newNode;

2. 在末尾插入​

  • 为新节点分配内存
  • 存储数据
  • 遍历到最后一个节点
  • 改变最后一个节点的 next 指向最近创建的节点
struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = NULL;

struct node *temp = head;
while(temp->next != NULL){
  temp = temp->next;
}

temp->next = newNode;

3. 在中间插入​

  • 为新节点分配内存并存储数据
  • 遍历到新节点所需位置之前的节点
  • 改变 next 指针以在中间包含新节点
struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;

struct node *temp = head;

for(int i=2; i < position; i++) {
  if(temp->next != NULL) {
    temp = temp->next;
  }
}
newNode->next = temp->next;
temp->next = newNode;

从链表中删除​

你可以从开始、末尾或特定位置删除。

1. 从开始处删除​

  • 将 head 指向第二个节点
head = head->next;

2. 从末尾删除​

  • 遍历到倒数第二个元素
  • 将其下一个指针更改为null
struct node* temp = head;
while(temp->next->next!=NULL){
  temp = temp->next;
}
temp->next = NULL;

3. 从中间删除​

  • 遍历到要删除的元素前面的元素
  • 更改下一个指针以排除链中的节点
for(int i=2; i< position; i++) {
  if(temp->next!=NULL) {
    temp = temp->next;
  }
}

temp->next = temp->next->next;

在链表上搜索元素​

您可以使用以下步骤使用循环在链表上搜索元素。我们正在在链表上查找 item。

  • 将 head 设置为当前节点 current。
  • 运行循环，直到当前节点 current 为 NULL，因为最后一个元素指向 NULL。
  • 在每次迭代中，检查节点的关键字是否等于 item。如果关键字与项目匹配，则返回 true，否则返回 false。
// 搜索节点
bool searchNode(struct Node** head_ref, int key) {
  struct Node* current = *head_ref;

  while (current != NULL) {
    if (current->data == key) return true;
      current = current->next;
  }
  return false;
}

对链表元素进行排序​

我们将使用简单的排序算法，冒泡排序，以升序排列链表元素。

  1. 将 head 设置为当前节点 current，并创建另一个节点 index 供以后使用。
  2. 如果 head 为null，则返回。
  3. 否则，运行循环直到最后一个节点（即 NULL）。
  4. 在每次迭代中，执行以下步骤 5-6。
  5. 将 current 的下一个节点存储在 index 中。
  6. 检查当前节点的数据是否大于下一个节点。如果大于，则交换 current 和 index。

查看 冒泡排序 文章，以更好地理解其工作原理。

// 对链表进行排序
void sortLinkedList(struct Node** head_ref) {
  struct Node *current = *head_ref, *index = NULL;
  int temp;

  if (head_ref == NULL) {
    return;
  } else {
    while (current != NULL) {
      // index 指向当前节点的下一个节点
      index = current->next;

      while (index != NULL) {
        if (current->data > index->data) {
          temp = current->data;
          current->data = index->data;
          index->data = temp;
        }
        index = index->next;
      }
      current = current->next;
    }
  }
}

Python、Java、C 和 C++ 中的链表操作​

Python Java C C++

# Python中的链表操作

# 创建节点
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:

    def __init__(self):
        self.head = None

    # 在开头插入
    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)

        new_node.next = self.head
        self.head = new_node

    # 在节点后插入
    def insertAfter(self, prev_node, new_data):

        if prev_node is None:
            print("给定的前一个节点必须在链表中。")
            return

        new_node = Node(new_data)
        new_node.next = prev_node.next
        prev_node.next = new_node

    # 在末尾插入
    def insertAtEnd(self, new_data):
        new_node = Node(new_data)

        if self.head is None:
            self.head = new_node
            return

        last = self.head
        while (last.next):
            last = last.next

        last.next = new_node

    # 删除节点
    def deleteNode(self, position):

        if self.head is None:
            return

        temp = self.head

        if position == 0:
            self.head = temp.next
            temp = None
            return

        # 查找要删除的键
        for i in range(position - 1):
            temp = temp.next
            if temp is None:
                break

        # 如果键不存在
        if temp is None:
            return

        if temp.next is None:
            return

        next = temp.next.next

        temp.next = None

        temp.next = next

    # 搜索元素
    def search(self, key):

        current = self.head

        while current is not None:
            if current.data == key:
                return True

            current = current.next

        return False

    # 对链表进行排序
    def sortLinkedList(self, head):
        current = head
        index = Node(None)

        if head is None:
            return
        else:
            while current is not None:
                # index 指向当前节点的下一个节点
                index = current.next

                while index is not None:
                    if current.data > index.data:
                        current.data, index.data = index.data, current.data

                    index = index.next
                current = current.next

    # 打印链表
    def printList(self):
        temp = self.head
        while (temp):
            print(str(temp.data) + " ", end="")
            temp = temp.next


if __name__ == '__main__':

    llist = LinkedList()
    llist.insertAtEnd(1)
    llist.insertAtBeginning(2)
    llist.insertAtBeginning(3)
    llist.insertAtEnd(4)
    llist.insertAfter(llist.head.next, 5)

    print('链表:')
    llist.printList()

    print("\n删除元素后:")
    llist.deleteNode(3)
    llist.printList()

    print()
    item_to_find = 3
    if llist.search(item_to_find):
        print(str(item_to_find) + " 已找到")
    else:
        print(str(item_to_find) + " 未找到")

    llist.sortLinkedList(llist.head)
    print("排序后的列表：")
    llist.printList()
// Java中的链表操作

class LinkedList {
  Node head;

  // 创建节点
  class Node {
    int data;
    Node next;

    Node(int d) {
      data = d;
      next = null;
    }
  }

  // 在开头插入
  public void insertAtBeginning(int new_data) {
    // 插入数据
    Node new_node = new Node(new_data);
    new_node.next = head;
    head = new_node;
  }

  // 在节点后插入
  public void insertAfter(Node prev_node, int new_data) {
    if (prev_node == null) {
      System.out.println("给定的前一个节点不能为null");
      return;
    }
    Node new_node = new Node(new_data);
    new_node.next = prev_node.next;
    prev_node.next = new_node;
  }

  // 在末尾插入
  public void insertAtEnd(int new_data) {
    Node new_node = new Node(new_data);

    if (head == null) {
      head = new Node(new_data);
      return;
    }

    new_node.next = null;

    Node last = head;
    while (last.next != null)
      last = last.next;

    last.next = new_node;
    return;
  }

  // 删除节点
  void deleteNode(int position) {
    if (head == null)
      return;

    Node temp = head;

    if (position == 0) {
      head = temp.next;
      return;
    }
    // 查找要删除的键
    for (int i = 0; temp != null && i < position - 1; i++)
      temp = temp.next;

    // 如果键不存在
    if (temp == null || temp.next == null)
      return;

    // 删除节点
    Node next = temp.next.next;

    temp.next = next;
  }

  // 搜索节点
  boolean search(Node head, int key) {
    Node current = head;
    while (current != null) {
      if (current.data == key)
        return true;
      current = current.next;
    }
    return false;
  }

  // 对链表进行排序
  void sortLinkedList(Node head) {
    Node current = head;
    Node index = null;
    int temp;

    if (head == null) {
      return;
    } else {
      while (current != null) {
        // index 指向当前节点的下一个节点
        index = current.next;

        while (index != null) {
          if (current.data > index.data) {
            temp = current.data;
            current.data = index.data;
            index.data = temp;
          }
          index = index.next;
        }
        current = current.next;
      }
    }
  }

  // 打印链表
  public void printList() {
    Node tnode = head;
    while (tnode != null) {
      System.out.print(tnode.data + " ");
      tnode = tnode.next;
    }

  }

  public static void main(String[] args) {
    LinkedList llist = new LinkedList();

    llist.insertAtEnd(1);
    llist.insertAtBeginning(2);
    llist.insertAtBeginning(3);
    llist.insertAtEnd(4);
    llist.insertAfter(llist.head.next, 5);

    System.out.println("链表: ");
    llist.printList();

    System.out.println("\n删除元素后: ");
    llist.deleteNode(3);
    llist.printList();

    System.out.println();
    int item_to_find = 3;
    if (llist.search(llist.head, item_to_find))
      System.out.println(item_to_find + " 已找到");
    else
      System.out.println(item_to_find + " 未找到");

    llist.sortLinkedList(llist.head);
    System.out.println("\n排序后的列表: ");
    llist.printList();
  }
}

这是一个Java中的链表操作示例。链表是一种常见的数据结构，可以用来存储和操作数据集合。此示例演示了如何在链表中执行插入、删除、搜索和排序等操作。

// C语言中的链表操作

#include <stdio.h>
#include <stdlib.h>

// 创建一个节点
struct Node {
  int data;
  struct Node* next;
};

// 在开头插入节点
void insertAtBeginning(struct Node** head_ref, int new_data) {
  // 分配内存给节点
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // 插入数据
  new_node->data = new_data;

  new_node->next = (*head_ref);

  // 将头指针移动到新节点
  (*head_ref) = new_node;
}

// 在节点后插入节点
void insertAfter(struct Node* prev_node, int new_data) {
  if (prev_node == NULL) {
    printf("给定的前一个节点不能为NULL");
    return;
  }

  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  new_node->data = new_data;
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

// 在末尾插入节点
void insertAtEnd(struct Node** head_ref, int new_data) {
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  struct Node* last = *head_ref; /* 用于步骤5 */

  new_node->data = new_data;
  new_node->next = NULL;

  if (*head_ref == NULL) {
    *head_ref = new_node;
    return;
  }

  while (last->next != NULL)
    last = last->next;

  last->next = new_node;
  return;
}

// 删除节点
void deleteNode(struct Node** head_ref, int key) {
  struct Node* temp = *head_ref, *prev;

  if (temp != NULL && temp->data == key) {
    *head_ref = temp->next;
    free(temp);
    return;
  }
  // 查找要删除的键
  while (temp != NULL && temp->data != key) {
    prev = temp;
    temp = temp->next;
  }

  // 如果键不存在
  if (temp == NULL) return;

  // 删除节点
  prev->next = temp->next;

  free(temp);
}

// 搜索节点
int searchNode(struct Node** head_ref, int key) {
  struct Node* current = *head_ref;

  while (current != NULL) {
    if (current->data == key) return 1;
    current = current->next;
  }
  return 0;
}

// 对链表进行排序
void sortLinkedList(struct Node** head_ref) {
  struct Node* current = *head_ref, *index = NULL;
  int temp;

  if (head_ref == NULL) {
    return;
  } else {
    while (current != NULL) {
      // index 指向当前节点的下一个节点
      index = current->next;

      while (index != NULL) {
        if (current->data > index->data) {
          temp = current->data;
          current->data = index->data;
          index->data = temp;
        }
        index = index->next;
      }
      current = current->next;
    }
  }
}

// 打印链表
void printList(struct Node* node) {
  while (node != NULL) {
    printf(" %d ", node->data);
    node = node->next;
  }
}

// 主程序
int main() {
  struct Node* head = NULL;

  insertAtEnd(&head, 1);
  insertAtBeginning(&head, 2);
  insertAtBeginning(&head, 3);
  insertAtEnd(&head, 4);
  insertAfter(head->next, 5);

  printf("链表: ");
  printList(head);

  printf("\n删除元素后: ");
  deleteNode(&head, 3);
  printList(head);

  int item_to_find = 3;
  if (searchNode(&head, item_to_find)) {
    printf("\n%d 已找到", item_to_find);
  } else {
    printf("\n%d 未找到", item_to_find);
  }

  sortLinkedList(&head);
  printf("\n排序后的列表: ");
  printList(head);
}

这是一个C语言中的链表操作示例。链表是一种常见的数据结构，可用于存储和操作数据集合。此示例演示了如何在链表中执行插入、删除、搜索和排序等操作。

// C++中的链表操作

#include <iostream>
using namespace std;

// 创建一个节点
struct Node {
  int data;
  struct Node* next;
};

void insertAtBeginning(struct Node** head_ref, int new_data) {
  // 为节点分配内存
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // 插入数据
  new_node->data = new_data;
  new_node->next = (*head_ref);

  // 移动头指针到新节点
  (*head_ref) = new_node;
}

// 在节点后插入节点
void insertAfter(struct Node* prev_node, int new_data) {
  if (prev_node == NULL) {
  cout << "给定的前一个节点不能为NULL";
  return;
  }

  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  new_node->data = new_data;
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

// 在末尾插入节点
void insertAtEnd(struct Node** head_ref, int new_data) {
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  struct Node* last = *head_ref; /* 用于步骤5*/

  new_node->data = new_data;
  new_node->next = NULL;

  if (*head_ref == NULL) {
  *head_ref = new_node;
  return;
  }

  while (last->next != NULL) last = last->next;

  last->next = new_node;
  return;
}

// 删除节点
void deleteNode(struct Node** head_ref, int key) {
  struct Node *temp = *head_ref, *prev;

  if (temp != NULL && temp->data == key) {
  *head_ref = temp->next;
  free(temp);
  return;
  }
  // 查找要删除的键
  while (temp != NULL && temp->data != key) {
  prev = temp;
  temp = temp->next;
  }

  // 如果键不存在
  if (temp == NULL) return;

  // 删除节点
  prev->next = temp->next;

  free(temp);
}

// 搜索节点
bool searchNode(struct Node** head_ref, int key) {
  struct Node* current = *head_ref;

  while (current != NULL) {
  if (current->data == key) return true;
  current = current->next;
  }
  return false;
}

// 对链表进行排序
void sortLinkedList(struct Node** head_ref) {
  struct Node *current = *head_ref, *index = NULL;
  int temp;

  if (head_ref == NULL) {
  return;
  } else {
  while (current != NULL) {
    // index 指向当前节点的下一个节点
    index = current->next;

    while (index != NULL) {
    if (current->data > index->data) {
      temp = current->data;
      current->data = index->data;
      index->data = temp;
    }
    index = index->next;
    }
    current = current->next;
  }
  }
}

// 打印链表
void printList(struct Node* node) {
  while (node != NULL) {
  cout << node->data << " ";
  node = node->next;
  }
}

// 主程序
int main() {
  struct Node* head = NULL;

  insertAtEnd(&head, 1);
  insertAtBeginning(&head, 2);
  insertAtBeginning(&head, 3);
  insertAtEnd(&head, 4);
  insertAfter(head->next, 5);

  cout << "链表: ";
  printList(head);

  cout << "\n删除元素后: ";
  deleteNode(&head, 3);
  printList(head);

  int item_to_find = 3;
  if (searchNode(&head, item_to_find)) {
  cout << endl << item_to_find << " 已找到";
  } else {
  cout << endl << item_to_find << " 未找到";
  }

  sortLinkedList(&head);
  cout << "\n排序后的列表: ";
  printList(head);
}

这是一个C++中的链表操作示例。链表是一种常见的数据结构，可用于存储和操作数据集合。此示例演示了如何在链表中执行插入、删除、搜索和排序等操作。

最后于 更新