数据结构（如何实现链表插入节点（详细实现代码）） _插入操作

本文概述

C ++
C
Java
python
C#
C ++
C
Java
python
C#
C ++
C
Java
python
C#
C ++
C
Java
python
C#
C ++
C
Java
python
C#

我们在上一篇文章中已经介绍了链表。我们还创建了一个包含3个节点的简单链表，并讨论了链表遍历。
本文讨论的所有程序均考虑以下链表的表示形式。
C ++

// A linked list node class Node { public : int data; Node *next; }; // This code is contributed by rathbhupendra

// A linked list node struct Node { int data; struct Node *next; };

Java

// Linked List Class class LinkedList { Node head; // head of list/* Node Class */ class Node { int data; Node next; // Constructor to create a new node Node( int d) {data = https://www.lsbin.com/d; next = null ; } } }

python

# Node class class Node:# Function to initialize the node object def __init__( self , data): self .data = https://www.lsbin.com/data# Assign data self . next = None# Initialize next as null# Linked List class class LinkedList:# Function to initialize the Linked List object def __init__( self ): self .head = None

/* Linked list Node*/ public class Node { public int data; public Node next; public Node( int d) {data = https://www.lsbin.com/d; next = null ; } }

在这篇文章中, 讨论了在链表中插入新节点的方法。可以通过三种方式添加节点
1)
在链接列表的最前面
2)
在给定节点之后。
3)
在链接列表的末尾。
推荐：请在"
实践
首先, 在继续解决方案之前。
在前面添加一个节点：(4个步骤)
新节点始终添加在给定链接列表的开头之前。新添加的节点成为链接列表的新头。例如, 如果给定的链接列表为10-> 15-> 20-> 25, 并且我们在前面添加了项目5, 则链接列表将变为5-> 10-> 15-> 20-> 25。让我们将添加到列表最前面的函数称为push()。 push()必须接收一个指向head指针的指针, 因为push必须更改head指针以指向新节点(请参见
这个
)

文章图片
【数据结构（如何实现链表插入节点（详细实现代码））】以下是在最前面添加节点的4个步骤。
C ++

/* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push(Node** head_ref, int new_data) { /* 1. allocate node */ Node* new_node = new Node(); /* 2. put in the data */ new_node-> data = https://www.lsbin.com/new_data; /* 3. Make next of new node as head */ new_node-> next = (*head_ref); /* 4. move the head to point to the new node */ (*head_ref) = new_node; } // This code is contributed by rathbhupendra

/* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push( struct Node** head_ref, int new_data) { /* 1. allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* 2. put in the data*/ new_node-> data= https://www.lsbin.com/new_data; /* 3. Make next of new node as head */ new_node-> next = (*head_ref); /* 4. move the head to point to the new node */ (*head_ref)= new_node; }

Java

/* This function is in LinkedList class. Inserts a new Node at front of the list. This method is defined inside LinkedList class shown above */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; }

python

# This function is in LinkedList class # Function to insert a new node at the beginning def push( self , new_data):# 1 & 2: Allocate the Node & #Put in the data new_node = Node(new_data)# 3. Make next of new Node as head new_node. next = self .head# 4. Move the head to point to new Node self .head = new_node

/* Inserts a new Node at front of the list. */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; }

push()的时间复杂度为O(1), 因为它要做的工作量是恒定的。
在给定节点之后添加节点：(5个步骤的过程)
我们获得了指向节点的指针, 并且在给定节点之后插入了新节点。

文章图片
C ++

// Given a node prev_node, insert a // new node after the given // prev_node void insertAfter(Node* prev_node, int new_data) {// 1. Check if the given prev_node is NULL if (prev_node == NULL) { cout < < "the given previous node cannot be NULL" ; return ; } // 2. Allocate new node Node* new_node = new Node(); // 3. Put in the data new_node-> data = https://www.lsbin.com/new_data; // 4. Make next of new node as // next of prev_node new_node-> next = prev_node-> next; // 5. move the next of prev_node // as new_node prev_node-> next = new_node; } // This code is contributed by anmolgautam818

/* Given a node prev_node, insert a new node after the given prev_node */ void insertAfter( struct Node* prev_node, int new_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { printf ( "the given previous node cannot be NULL" ); return ; } /* 2. allocate new node */ struct Node* new_node =( struct Node*) malloc ( sizeof ( struct Node)); /* 3. put in the data */ new_node-> data = https://www.lsbin.com/new_data; /* 4. Make next of new node as next of prev_node */ new_node-> next = prev_node-> next; /* 5. move the next of prev_node as new_node */ prev_node-> next = new_node; }

Java

/* This function is in LinkedList class. Inserts a new node after the given prev_node. This method is defined inside LinkedList class shown above */ public void insertAfter(Node prev_node, int new_data) { /* 1. Check if the given Node is null */ if (prev_node == null ) { System.out.println( "The given previous node cannot be null" ); return ; } /* 2. Allocate the Node & 3. Put in the data*/ Node new_node = new Node(new_data); /* 4. Make next of new Node as next of prev_node */ new_node.next = prev_node.next; /* 5. make next of prev_node as new_node */ prev_node.next = new_node; }

python

# This function is in LinkedList class. # Inserts a new node after the given prev_node. This method is # defined inside LinkedList class shown above */ def insertAfter( self , prev_node, new_data): # 1. check if the given prev_node exists if prev_node is None : print "The given previous node must inLinkedList." return# 2. Create new node & # 3. Put in the data new_node = Node(new_data) # 4. Make next of new Node as next of prev_node new_node. next = prev_node. next# 5. make next of prev_node as new_node prev_node. next = new_node

/* Inserts a new node after the given prev_node. */ public void insertAfter(Node prev_node, int new_data) { /* 1. Check if the given Node is null */ if (prev_node == null ) { Console.WriteLine( "The given previous node" + " cannot be null" ); return ; } /* 2 & 3: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 4. Make next of new Node as next of prev_node */ new_node.next = prev_node.next; /* 5. make next of prev_node as new_node */ prev_node.next = new_node; }

insertAfter()的时间复杂度为O(1), 因为它的工作量是恒定的。
在最后添加一个节点：(6个步骤的过程)
新节点始终添加在给定链接列表的最后一个节点之后。例如, 如果给定的链接列表为5-> 10-> 15-> 20-> 25, 并且我们在末尾添加了项目30, 则链接列表将变为5-> 10-> 15-> 20-> 25- > 30。
由于链接列表通常由其头部表示, 因此我们必须遍历该列表直至结束, 然后将最后一个节点的下一个更改为新节点。

文章图片
以下是最后添加节点的6个步骤。
C ++

// Given a reference (pointer to pointer) to the head // of a list and an int, appends a new node at the end void append(Node** head_ref, int new_data) {// 1. allocate node Node* new_node = new Node(); // Used in step 5 Node *last = *head_ref; // 2. Put in the data new_node-> data = https://www.lsbin.com/new_data; // 3. This new node is going to be // the last node, so make next of // it as NULL new_node-> next = NULL; // 4. If the Linked List is empty, // then make the new node as head if (*head_ref == NULL) { *head_ref = new_node; return ; }// 5. Else traverse till the last node while (last-> next != NULL) last = last-> next; // 6. Change the next of last node last-> next = new_node; return ; }// This code is contributed by anmolgautam818

/* Given a reference (pointer to pointer) to the head of a list and an int, appends a new node at the end*/ void append( struct Node** head_ref, int new_data) { /* 1. allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); struct Node *last = *head_ref; /* used in step 5*//* 2. put in the data*/ new_node-> data= https://www.lsbin.com/new_data; /* 3. This new node is going to be the last node, so make next of it as NULL*/ new_node-> next = NULL; /* 4. If the Linked List is empty, then make the new node as head */ if (*head_ref == NULL) { *head_ref = new_node; return ; }/* 5. Else traverse till the last node */ while (last-> next != NULL) last = last-> next; /* 6. Change the next of last node */ last-> next = new_node; return ; }

Java

/* Appends a new node at the end.This method is defined inside LinkedList class shown above */ public void append( int new_data) { /* 1. Allocate the Node & 2. Put in the data 3. Set next as null */ Node new_node = new Node(new_data); /* 4. If the Linked List is empty, then make the new node as head */ if (head == null ) { head = new Node(new_data); return ; }/* 4. This new node is going to be the last node, so make next of it as null */ new_node.next = null ; /* 5. Else traverse till the last node */ Node last = head; while (last.next != null ) last = last.next; /* 6. Change the next of last node */ last.next = new_node; return ; }

python

# This function is defined in Linked List class # Appends a new node at the end.This method is #defined inside LinkedList class shown above */ def append( self , new_data): # 1. Create a new node # 2. Put in the data # 3. Set next as None new_node = Node(new_data) # 4. If the Linked List is empty, then make the #new node as head if self .head is None : self .head = new_node return # 5. Else traverse till the last node last = self .head while (last. next ): last = last. next # 6. Change the next of last node last. next =new_node

/* Appends a new node at the end. This method is defined inside LinkedList class shown above */ public void append( int new_data) { /* 1. Allocate the Node & 2. Put in the data 3. Set next as null */ Node new_node = new Node(new_data); /* 4. If the Linked List is empty, then make the new node as head */ if (head == null ) { head = new Node(new_data); return ; }/* 4. This new node is going to be the last node, so make next of it as null */ new_node.next = null ; /* 5. Else traverse till the last node */ Node last = head; while (last.next != null ) last = last.next; /* 6. Change the next of last node */ last.next = new_node; return ; }

append的时间复杂度为O(n), 其中n是链表中节点的数量。由于从头到尾都有一个循环, 因此该函数可以执行O(n)。
通过保留指向链接列表/尾部的额外指针, 还可以将该方法优化为在O(1)中工作
以下是使用上述所有方法来创建链接列表的完整程序。
C ++

// A complete working C++ program to demonstrate //all insertion methods on Linked List #include < bits/stdc++.h> using namespace std; // A linked list node class Node { public : int data; Node *next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push(Node** head_ref, int new_data) { /* 1. allocate node */ Node* new_node = new Node(); /* 2. put in the data */ new_node-> data = https://www.lsbin.com/new_data; /* 3. Make next of new node as head */ new_node-> next = (*head_ref); /* 4. move the head to point to the new node */ (*head_ref) = new_node; } /* Given a node prev_node, insert a new node after the given prev_node */ void insertAfter(Node* prev_node, int new_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { cout< <"the given previous node cannot be NULL" ; return ; } /* 2. allocate new node */ Node* new_node = new Node(); /* 3. put in the data */ new_node-> data = https://www.lsbin.com/new_data; /* 4. Make next of new node as next of prev_node */ new_node-> next = prev_node-> next; /* 5. move the next of prev_node as new_node */ prev_node-> next = new_node; } /* Given a reference (pointer to pointer) to the head of a list and an int, appends a new node at the end */ void append(Node** head_ref, int new_data) { /* 1. allocate node */ Node* new_node = new Node(); Node *last = *head_ref; /* used in step 5*//* 2. put in the data */ new_node-> data = new_data; /* 3. This new node is going to be the last node, so make next of it as NULL*/ new_node-> next = NULL; /* 4. If the Linked List is empty, then make the new node as head */ if (*head_ref == NULL) { *head_ref = new_node; return ; } /* 5. Else traverse till the last node */ while (last-> next != NULL) last = last-> next; /* 6. Change the next of last node */ last-> next = new_node; return ; } // This function prints contents of // linked list starting from head void printList(Node *node) { while (node != NULL) { cout< <" " < < node-> data; node = node-> next; } } /* Driver code*/ int main() { /* Start with the empty list */ Node* head = NULL; // Insert 6. So linked list becomes 6-> NULL append(& head, 6); // Insert 7 at the beginning. // So linked list becomes 7-> 6-> NULL push(& head, 7); // Insert 1 at the beginning. // So linked list becomes 1-> 7-> 6-> NULL push(& head, 1); // Insert 4 at the end. So // linked list becomes 1-> 7-> 6-> 4-> NULL append(& head, 4); // Insert 8, after 7. So linked // list becomes 1-> 7-> 8-> 6-> 4-> NULL insertAfter(head-> next, 8); cout< < "Created Linked list is: " ; printList(head); return 0; } // This code is contributed by rathbhupendra

// A complete working C program to demonstrate all insertion methods // on Linked List #include < stdio.h> #include < stdlib.h> // A linked list node struct Node { int data; struct Node *next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push( struct Node** head_ref, int new_data) { /* 1. allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* 2. put in the data*/ new_node-> data= https://www.lsbin.com/new_data; /* 3. Make next of new node as head */ new_node-> next = (*head_ref); /* 4. move the head to point to the new node */ (*head_ref)= new_node; }/* Given a node prev_node, insert a new node after the given prev_node */ void insertAfter( struct Node* prev_node, int new_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { printf ("the given previous node cannot be NULL" ); return ; }/* 2. allocate new node */ struct Node* new_node =( struct Node*) malloc ( sizeof ( struct Node)); /* 3. put in the data*/ new_node-> data= https://www.lsbin.com/new_data; /* 4. Make next of new node as next of prev_node */ new_node-> next = prev_node-> next; /* 5. move the next of prev_node as new_node */ prev_node-> next = new_node; }/* Given a reference (pointer to pointer) to the head of a list and an int, appends a new node at the end*/ void append( struct Node** head_ref, int new_data) { /* 1. allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); struct Node *last = *head_ref; /* used in step 5*//* 2. put in the data*/ new_node-> data= new_data; /* 3. This new node is going to be the last node, so make next of it as NULL*/ new_node-> next = NULL; /* 4. If the Linked List is empty, then make the new node as head */ if (*head_ref == NULL) { *head_ref = new_node; return ; }/* 5. Else traverse till the last node */ while (last-> next != NULL) last = last-> next; /* 6. Change the next of last node */ last-> next = new_node; return ; }// This function prints contents of linked list starting from head void printList( struct Node *node) { while (node != NULL) { printf (" %d " , node-> data); node = node-> next; } }/* Driver program to test above functions*/ int main() { /* Start with the empty list */ struct Node* head = NULL; // Insert 6.So linked list becomes 6-> NULL append(& head, 6); // Insert 7 at the beginning. So linked list becomes 7-> 6-> NULL push(& head, 7); // Insert 1 at the beginning. So linked list becomes 1-> 7-> 6-> NULL push(& head, 1); // Insert 4 at the end. So linked list becomes 1-> 7-> 6-> 4-> NULL append(& head, 4); // Insert 8, after 7. So linked list becomes 1-> 7-> 8-> 6-> 4-> NULL insertAfter(head-> next, 8); printf ( "\n Created Linked list is: " ); printList(head); return 0; }

Java

// A complete working Java program to demonstrate all insertion methods // on linked list class LinkedList { Node head; // head of list/* Linked list Node*/ class Node { int data; Node next; Node( int d) {data = https://www.lsbin.com/d; next = null ; } }/* Inserts a new Node at front of the list. */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; }/* Inserts a new node after the given prev_node. */ public void insertAfter(Node prev_node, int new_data) { /* 1. Check if the given Node is null */ if (prev_node == null ) { System.out.println("The given previous node cannot be null" ); return ; }/* 2 & 3: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 4. Make next of new Node as next of prev_node */ new_node.next = prev_node.next; /* 5. make next of prev_node as new_node */ prev_node.next = new_node; }/* Appends a new node at the end.This method is defined inside LinkedList class shown above */ public void append( int new_data) { /* 1. Allocate the Node & 2. Put in the data 3. Set next as null */ Node new_node = new Node(new_data); /* 4. If the Linked List is empty, then make the new node as head */ if (head == null ) { head = new Node(new_data); return ; }/* 4. This new node is going to be the last node, so make next of it as null */ new_node.next = null ; /* 5. Else traverse till the last node */ Node last = head; while (last.next != null ) last = last.next; /* 6. Change the next of last node */ last.next = new_node; return ; }/* This function prints contents of linked list starting from the given node */ public void printList() { Node tnode = head; while (tnode != null ) { System.out.print(tnode.data+ " " ); tnode = tnode.next; } }/* Driver program to test above functions. Ideally this function should be in a separate user class.It is kept here to keep code compact */ public static void main(String[] args) { /* Start with the empty list */ LinkedList llist = new LinkedList(); // Insert 6.So linked list becomes 6-> NUllist llist.append( 6 ); // Insert 7 at the beginning. So linked list becomes // 7-> 6-> NUllist llist.push( 7 ); // Insert 1 at the beginning. So linked list becomes // 1-> 7-> 6-> NUllist llist.push( 1 ); // Insert 4 at the end. So linked list becomes // 1-> 7-> 6-> 4-> NUllist llist.append( 4 ); // Insert 8, after 7. So linked list becomes // 1-> 7-> 8-> 6-> 4-> NUllist llist.insertAfter(llist.head.next, 8 ); System.out.println( "\nCreated Linked list is: " ); llist.printList(); } } // This code is contributed by Rajat Mishra

python

# A complete working Python program to demonstrate all # insertion methods of linked list# Node class class Node:# Function to initialise the node object def __init__( self , data): self .data = https://www.lsbin.com/data# Assign data self . next = None# Initialize next as null# Linked List class contains a Node object class LinkedList:# Function to initialize head def __init__( self ): self .head = None# Functio to insert a new node at the beginning def push( self , new_data):# 1 & 2: Allocate the Node & #Put in the data new_node = Node(new_data)# 3. Make next of new Node as head new_node. next = self .head# 4. Move the head to point to new Node self .head = new_node# This function is in LinkedList class. Inserts a # new node after the given prev_node. This method is # defined inside LinkedList class shown above */ def insertAfter( self , prev_node, new_data):# 1. check if the given prev_node exists if prev_node is None : print"The given previous node must inLinkedList." return#2. create new node & #Put in the data new_node = Node(new_data)# 4. Make next of new Node as next of prev_node new_node. next = prev_node. next# 5. make next of prev_node as new_node prev_node. next = new_node# This function is defined in Linked List class # Appends a new node at the end.This method is # defined inside LinkedList class shown above */ def append( self , new_data):# 1. Create a new node # 2. Put in the data # 3. Set next as None new_node = Node(new_data)# 4. If the Linked List is empty, then make the #new node as head if self .head is None : self .head = new_node return# 5. Else traverse till the last node last = self .head while (last. next ): last = last. next# 6. Change the next of last node last. next =new_node# Utility function to print the linked list def printList( self ): temp = self .head while (temp): print temp.data, temp = temp. next# Code execution starts here if __name__ = = '__main__' :# Start with the empty list llist = LinkedList()# Insert 6.So linked list becomes 6-> None llist.append( 6 )# Insert 7 at the beginning. So linked list becomes 7-> 6-> None llist.push( 7 ); # Insert 1 at the beginning. So linked list becomes 1-> 7-> 6-> None llist.push( 1 ); # Insert 4 at the end. So linked list becomes 1-> 7-> 6-> 4-> None llist.append( 4 )# Insert 8, after 7. So linked list becomes 1 -> 7-> 8-> 6-> 4-> None llist.insertAfter(llist.head. next , 8 )print 'Created linked list is:' , llist.printList()# This code is contributed by Manikantan Narasimhan

// A complete working C# program to demonstrate // all insertion methods on linked list using System; class GFG { public Node head; // head of list/* Linked list Node*/ public class Node { public int data; public Node next; public Node( int d) {data = https://www.lsbin.com/d; next = null ; } }/* Inserts a new Node at front of the list. */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; }/* Inserts a new node after the given prev_node. */ public void insertAfter(Node prev_node, int new_data) { /* 1. Check if the given Node is null */ if (prev_node == null ) { Console.WriteLine("The given previous" + " node cannot be null" ); return ; }/* 2 & 3: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 4. Make next of new Node as next of prev_node */ new_node.next = prev_node.next; /* 5. make next of prev_node as new_node */ prev_node.next = new_node; }/* Appends a new node at the end. This method is defined inside LinkedList class shown above */ public void append( int new_data) { /* 1. Allocate the Node & 2. Put in the data 3. Set next as null */ Node new_node = new Node(new_data); /* 4. If the Linked List is empty, then make the new node as head */ if (head == null ) { head = new Node(new_data); return ; }/* 4. This new node is going to be the last node, so make next of it as null */ new_node.next = null ; /* 5. Else traverse till the last node */ Node last = head; while (last.next != null ) last = last.next; /* 6. Change the next of last node */ last.next = new_node; return ; }/* This function prints contents of linked list starting from the given node */ public void printList() { Node tnode = head; while (tnode != null ) { Console.Write(tnode.data + " " ); tnode = tnode.next; } }// Driver Code public static void Main(String[] args) { /* Start with the empty list */ GFG llist = new GFG(); // Insert 6. So linked list becomes 6-> NUllist llist.append(6); // Insert 7 at the beginning. // So linked list becomes 7-> 6-> NUllist llist.push(7); // Insert 1 at the beginning. // So linked list becomes 1-> 7-> 6-> NUllist llist.push(1); // Insert 4 at the end. So linked list becomes // 1-> 7-> 6-> 4-> NUllist llist.append(4); // Insert 8, after 7. So linked list becomes // 1-> 7-> 8-> 6-> 4-> NUllist llist.insertAfter(llist.head.next, 8); Console.Write( "Created Linked list is: " ); llist.printList(); } }// This code is contributed by Rajput-Ji

输出如下：