Вставить узел после заданного узла в связанном списке

Опубликовано: 27 Февраля, 2023

Как и массивы, связанный список представляет собой линейную структуру данных. В отличие от массивов элементы связанного списка не хранятся в непрерывном месте; элементы связаны с помощью указателей. Они включают ряд соединенных узлов. Здесь каждый узел хранит данные и адрес следующего узла.

Чтобы узнать больше о связном списке, обратитесь к статье «Введение в связанный список».

При наличии связанного списка задача состоит в том, чтобы вставить новый узел после заданного узла связанного списка.

Пример:

List = 1->2->4->5, Insert a node with value 3 after the node with value 2.
Output list will be: 1->2->3->4->5

Рассмотрим следующие представления связанного списка.

C++




// A linked list node
class Node {
public:
    int data;
    Node* next;
};

C



// 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 = d;
            next = null;
        }
    }
}
Python3



# 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
  
# Linked List class
  
  
class LinkedList:
  
    # Function to initialize the Linked List object
    def __init__(self):
        self.head = None
C#



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



<script>
// Linked List Class
    var head; // head of list
  
    /* Node Class */
    class Node {
  
        // Constructor to create a new node
        constructor(d) {
            this.data = d;
            this.next = null;
        }
    }
// This code is contributed by todaysgaurav 
</script>
Подход: выполните следующие шаги для вставки узла после заданного узла:
  • Во-первых, проверьте, является ли данный предыдущий узел NULL или нет.
  •  Затем выделите новый узел (скажем, temp ) и
  •  Назначьте данные для temp .
  •  А затем сделайте следующий временный узел следующим из предыдущего узла.
  •  Наконец, переместите следующий из предыдущих узлов, чтобы он указывал на temp .
Следуйте изображению ниже для лучшего понимания.
Ниже приведена реализация подхода.
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;
}
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;
}
Python3



# 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;
}
Javascript



<script>
  
/* This function is in LinkedList class. 
Inserts a new node after the given prev_node. This method is 
defined inside LinkedList class shown above */
function insertAfter(prev_node, new_data) 
{ 
  
    /* 1. Check if the given Node is null */
    if (prev_node == null) 
    { 
        document.write("The given previous node cannot be null"); 
        return; 
    } 
  
    /* 2. Allocate the Node & 
    3. Put in the data*/
    var 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; 
}
  
// This code is contributed by aashish1995
  
</script>
Временная сложность: O(1)
 Вспомогательное пространство: O(1)

            

                            

                    
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ