# 数据结构：如何实现链表插入节点？详细实现代码

2021年3月19日14:08:14 发表评论 393 次浏览

## C ++

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

## C

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

## Java

``````// Linked List Class
{

/* Node Class */
class Node
{
int data;
Node next;

// Constructor to create a new node
Node( int d) {data = d; next = null ; }
}
}``````

## python

``````# Node class
class Node:

# Function to initialize the node object
def __init__( self , data):
self .data = data  # Assign data
self . next = None  # Initialize next as null

# Function to initialize the Linked List object
def __init__( self ):

## C#

``````/* Linked list Node*/
public class Node
{
public int data;
public Node next;
public Node( int d) {data = d; next = null ; }
}``````

1)

2)

3)

)

## 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. */
{
/* 1. allocate node */
Node* new_node = new Node();

/* 2. put in the data */
new_node->data = new_data;

/* 3. Make next of new node as head */

/* 4. move the head to point to the new node */
}

// This code is contributed by rathbhupendra``````

## 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( 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  = new_data;

/* 3. Make next of new node as head */

/* 4. move the head to point to the 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 */

/* 4. Move the head to point to 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

# 4. Move the head to point to new Node

## C#

``````/* 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 */

/* 4. Move the head to point to new Node */
}``````

push()的时间复杂度为O(1), 因为它要做的工作量是恒定的。

## 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 = 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``````

## C

``````/* 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 = 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``````

## C#

``````/* 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), 因为它的工作量是恒定的。

## C ++

``````// Given a reference (pointer to pointer) to the head
// of a list and an int, appends a new node at the end
{

// 1. allocate node
Node* new_node = new Node();

// 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
{
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``````

## 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( 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 */
{
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
{
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 */
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
if self .head is None :
return

# 5. Else traverse till the last node
while (last. next ):
last = last. next

# 6. Change the next of last node
last. next =  new_node``````

## C#

``````/* 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 */
{
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 */
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)。

## C ++

``````// A complete working C++ program to demonstrate
//  all insertion methods on Linked List
#include <bits/stdc++.h>
using namespace std;

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. */
{
/* 1. allocate node */
Node* new_node = new Node();

/* 2. put in the data */
new_node->data = new_data;

/* 3. Make next of new node as head */

/* 4. move the head to point to the 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 = 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 */
{
/* 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 */
{
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
void printList(Node *node)
{
while (node != NULL)
{
cout<< " " <<node->data;
node = node->next;
}
}

/* Driver code*/
int main()
{

// Insert 6. So linked list becomes 6->NULL

// Insert 7 at the beginning.
// So linked list becomes 7->6->NULL

// Insert 1 at the beginning.
// So linked list becomes 1->7->6->NULL

// Insert 4 at the end. So

// Insert 8, after 7. So linked
// list becomes 1->7->8->6->4->NULL

cout<< "Created Linked list is: " ;

return 0;
}

// This code is contributed by rathbhupendra``````

## C

``````// A complete working C program to demonstrate all insertion methods
#include <stdio.h>
#include <stdlib.h>

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  = new_data;

/* 3. Make next of new node as head */

/* 4. move the head to point to the 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  = 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 */
{
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 ;
}

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

/* Driver program to test above functions*/
int main()
{

// Insert 6.  So linked list becomes 6->NULL

// Insert 7 at the beginning. So linked list becomes 7->6->NULL

// Insert 1 at the beginning. So linked list becomes 1->7->6->NULL

// Insert 4 at the end. So linked list becomes 1->7->6->4->NULL

// Insert 8, after 7. So linked list becomes 1->7->8->6->4->NULL

printf ( "\n Created Linked list is: " );

return 0;
}``````

## Java

``````// A complete working Java program to demonstrate all insertion methods
{

class Node
{
int data;
Node next;
Node( int d) {data = 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 */

/* 4. Move the head to point to 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
{
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 */
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()
{
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)
{

// 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

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 = data  # Assign data
self . next = None  # Initialize next as null

# Linked List class contains a Node object

def __init__( self ):

# 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

# 4. Move the head to point to 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
if self .head is None :
return

# 5. Else traverse till the last node
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 ):
while (temp):
print temp.data, temp = temp. next

# Code execution starts here
if __name__ = = '__main__' :

# 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

print 'Created linked list is:' , llist.printList()

# This code is contributed by Manikantan Narasimhan``````

## C#

``````// A complete working C# program to demonstrate
// all insertion methods on linked list
using System;

class GFG
{

public class Node
{
public int data;
public Node next;
public Node( int d) {data = 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 */

/* 4. Move the head to point to 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 */
{
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 */
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()
{
while (tnode != null )
{
Console.Write(tnode.data + " " );
tnode = tnode.next;
}
}

// Driver Code
public static void Main(String[] args)
{
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

Console.Write( "Created Linked list is: " );
llist.printList();
}
}

// This code is contributed by Rajput-Ji``````

``Created Linked list is:  1  7  8  6  4`` 