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

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

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

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

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

Пример:

List = 1->2->3->4, Insert a node with value 5 at the end.
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>
Подход: Ниже приведен подход к добавлению нового узла в конец связанного списка:
  • Выделите память для нового узла (скажем, temp ) и создайте указатель (скажем, last ), который указывает на начало связанного списка.
  •  Установите данные для ввода в temp .
  •  temp будет последним узлом. Следовательно, следующий указатель temp будет указывать на null .
  •  Если связанный список пуст, сделайте temp главой .
  •  Переходим по последнему указателю, пока не достигнем конечного узла связанного списка.
  •  Теперь укажите следующий узел на temp .
Следуйте изображению ниже для лучшего понимания:
Ниже приведена реализация подхода:
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 = 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;
}
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 */
    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;
}
Python3



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



<script>
  
/* Appends a new node at the end.  This method is 
   defined inside LinkedList class shown above */
 function append(new_data)
{
    /* 1. Allocate the Node &
       2. Put in the data
       3. Set next as null */
    var 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 */
    var last = head; 

                    
                                    

                        

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