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

在本教程中，您将学习链表上的不同操作。此外，您还将发现 C/C++ ，Python 和 Java 中链表操作的实现。
如何遍历链表
如何将元素添加到链表
如何从链表中删除
完整的链表操作程序

原文： https://www.programiz.com/dsa/linked-list-operations

在本教程中，您将学习链表上的不同操作。此外，您还将发现 C/C++ ，Python 和 Java 中链表操作的实现。

现在您已经了解了链表和它们的类型的基本概念，是时候深入了解可以执行的常见操作了。

请记住两个要点：

head指向链表的第一个节点
最后一个节点的next指针是NULL，因此，如果下一个当前节点是NULL，我们已经到达链表的末尾。

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

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

如何遍历链表

显示链表的内容非常简单。我们继续将临时节点移至下一个节点并显示其内容。

当temp为NULL时，我们知道我们已经到达链表的末尾，因此我们退出了while循环。

struct node *temp = head;
printf("\n\nList elements are - \n");
while(temp != NULL)
{
     printf("%d --->",temp->data);
     temp = temp->next;
}

该程序的输出为：

List elements are - 
1 --->2 --->3 --->

如何将元素添加到链表

您可以将元素添加到链表的开始，中间或结尾。

添加到开头

为新节点分配内存
存储数据
更改新节点的next指向head
将head更改为指向最近创建的节点

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = head;
head = newNode;

添加到最后

为新节点分配内存
存储数据
遍历到最后一个节点
将最后一个节点的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;

添加到中间

分配内存并存储新节点的数据
遍历到新节点所需位置之前的节点
更改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;

如何从链表中删除

您可以从开头，结尾或特定位置删除。

从头删除

将head指向第二个节点

head = head->next;

从结尾删除

遍历到倒数第二个元素
将其next指针更改为null

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

从中间删除

遍历到要删除的元素之前的元素
更改next指针以将节点从链中排除

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

完整的链表操作程序

# Linked list operations in Python
# Create a node
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    # Insert at the beginning
    def insertAtBeginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    # Insert after a node
    def insertAfter(self, node, data):
        if node is None:
            print("The given previous node must inLinkedList.")
            return
        new_node = Node(data)
        new_node.next = node.next
        node.next = new_node
    # Insert at the end
    def insertAtEnd(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while (last.next):
            last = last.next
        last.next = new_node
    # Deleting a node
    def deleteNode(self, position):
        if self.head == None:
            return
        temp_node = self.head
        if position == 0:
            self.head = temp_node.next
            temp_node = None
            return
        # Find the key to be deleted
        for i in range(position - 1):
            temp_node = temp_node.next
            if temp_node is None:
                break
        # If the key is not present
        if temp_node is None:
            return
        if temp_node.next is None:
            return
        next = temp_node.next.next
        temp_node.next = None
        temp_node.next = next
    def printList(self):
        temp_node = self.head
        while (temp_node):
            print(str(temp_node.item) + " ", end="")
            temp_node = temp_node.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('Linked list:')
    llist.printList()
    print("\nAfter deleting an element:")
    llist.deleteNode(3)
    llist.printList()

// Linked list operations in Java
class LinkedList {
  Node head;
  // Create a node
  class Node {
    int item;
    Node next;
    Node(int d) {
      item = d;
      next = null;
    }
  }
  public void insertAtBeginning(int data) {
    // insert the item
    Node new_node = new Node(data);
    new_node.next = head;
    head = new_node;
  }
  public void insertAfter(Node prev_node, int data) {
    if (prev_node == null) {
      System.out.println("The given previous node cannot be null");
      return;
    }
    Node new_node = new Node(data);
    new_node.next = prev_node.next;
    prev_node.next = new_node;
  }
  public void insertAtEnd(int data) {
    Node new_node = new Node(data);
    if (head == null) {
      head = new Node(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 node = head;
    if (position == 0) {
      head = node.next;
      return;
    }
    // Find the key to be deleted
    for (int i = 0; node != null && i < position - 1; i++)
      node = node.next;
    // If the key is not present
    if (node == null || node.next == null)
      return;
    // Remove the node
    Node next = node.next.next;
    node.next = next;
  }
  public void printList() {
    Node node = head;
    while (node != null) {
      System.out.print(node.item + " ");
      node = node.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("Linked list: ");
    llist.printList();
    System.out.println("\nAfter deleting an element: ");
    llist.deleteNode(3);
    llist.printList();
  }
}

// Linked list operations in C

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

// Create a node
struct Node {
  int item;
  struct Node* next;
};

void insertAtBeginning(struct Node** ref, int data) {
  // Allocate memory to a node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // insert the item
  new_node->item = data;
  new_node->next = (*ref);

  // Move head to new node
  (*ref) = new_node;
}

// Insert a node after a node
void insertAfter(struct Node* node, int data) {
  if (node == NULL) {
    printf("the given previous node cannot be NULL");
    return;
  }

  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  new_node->item = data;
  new_node->next = node->next;
  node->next = new_node;
}

void insertAtEnd(struct Node** ref, int data) {
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  struct Node* last = *ref;

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

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

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

  last->next = new_node;
  return;
}

void deleteNode(struct Node** ref, int key) {
  struct Node *temp = *ref, *prev;

  if (temp != NULL && temp->item == key) {
    *ref = temp->next;
    free(temp);
    return;
  }
  // Find the key to be deleted
  while (temp != NULL && temp->item != key) {
    prev = temp;
    temp = temp->next;
  }

  // If the key is not present
  if (temp == NULL) return;

  // Remove the node
  prev->next = temp->next;

  free(temp);
}

// Print the linked list
void printList(struct Node* node) {
  while (node != NULL) {
    printf(" %d ", node->item);
    node = node->next;
  }
}

// Driver program
int main() {
  struct Node* head = NULL;

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

  printf("Linked list: ");
  printList(head);

  printf("\nAfter deleting an element: ");
  deleteNode(&head, 3);
  printList(head);
}

// Linked list operations in C++

#include <stdlib.h>
#include <iostream>

using namespace std;

// Create a node
struct Node {
  int item;
  struct Node* next;
};

void insertAtBeginning(struct Node** ref, int data) {

  // Allocate memory to a node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // insert the item
  new_node->item = data;
  new_node->next = (*ref);

  // Move head to new node
  (*ref) = new_node;
}

// Insert a node after a node
void insertAfter(struct Node* prev_node, int data) {
  if (prev_node == NULL) {
    cout << "the given previous node cannot be NULL";
    return;
  }

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

void insertAtEnd(struct Node** ref, int data) {
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  struct Node* last = *ref;

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

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

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

  last->next = new_node;
  return;
}

void deleteNode(struct Node** ref, int key) {
  struct Node *temp = *ref, *prev;

  if (temp != NULL && temp->item == key) {
    *ref = temp->next;
    free(temp);
    return;
  }
  // Find the key to be deleted
  while (temp != NULL && temp->item != key) {
    prev = temp;
    temp = temp->next;
  }

  // If the key is not present
  if (temp == NULL) return;

  // Remove the node
  prev->next = temp->next;

  free(temp);
}

// Print the linked list
void printList(struct Node* node) {
  while (node != NULL) {
    cout << node->item << " ";
    node = node->next;
  }
}

// Driver program
int main() {
  struct Node* head = NULL;

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

  cout << "Linked list: ";
  printList(head);

  cout << "\nAfter deleting an element: ";
  deleteNode(&head, 3);
  printList(head);
}

在本教程中，您将学习链表上的不同操作。 此外，您还将发现 C/C++ ，Python 和 Java 中链表操作的实现。