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

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

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

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

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

Пример:

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



# 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
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 */
    new_node.next = head;
 
    /* 4. Move the head to point to new Node */
    head = new_node;
}
Javascript



<script>
 
/* This function is in LinkedList class. Inserts a
   new Node at front of the list. This method is
   defined inside LinkedList class shown above */
    
 function push(new_data)
{
    /* 1 & 2: Allocate the Node &
              Put in the data*/
    var 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;
}
 
// This code contributed by Rajput-Ji
 
</script>
Временная сложность: O(1)
 Вспомогательное пространство: O(1)

            

                            

                    
                                    

                        

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