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

Опубликовано: 24 Января, 2022

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

 Ввод: 3-> 5-> 8-> 10, данные = 2, позиция = 2
Вывод: 3-> 2-> 5-> 8-> 10

Ввод: 3-> 5-> 8-> 10, data = 11, position = 5
Вывод: 3-> 5-> 8-> 10-> 11

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Чтобы вставить данные в указанную позицию, необходимо следовать приведенному ниже алгоритму:

  • Переместитесь по связному списку вверх до узлов позиции 1.
  • Как только все узлы позиции 1 пройдены, выделите память и данные новому узлу.
  • Направьте следующий указатель нового узла на следующий из текущего узла.
  • Направьте следующий указатель текущего узла на новый узел.

Below is the implementation of the above algorithm.
 

C++

// C++ program for insertion in a single linked
// list at a specified position
#include <bits/stdc++.h>
using namespace std;
 
// A linked list Node
struct Node {
    int data;
    struct Node* next;
};
 
// Size of linked list
int size = 0;
 
// function to create and return a Node
Node* getNode(int data)
{
    // allocating space
    Node* newNode = new Node();
 
    // inserting the required data
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
 
// function to insert a Node at required position
void insertPos(Node** current, int pos, int data)
{
    // This condition to check whether the
    // position given is valid or not.
    if (pos < 1 || pos > size + 1)
        cout << "Invalid position!" << endl;
    else {
 
        // Keep looping until the pos is zero
        while (pos--) {
 
            if (pos == 0) {
 
                // adding Node at required position
                Node* temp = getNode(data);
 
                // Making the new Node to point to
                // the old Node at the same position
                temp->next = *current;
 
                // Changing the pointer of the Node previous
                // to the old Node to point to the new Node
                *current = temp;
            }
            else
              // Assign double pointer variable to point to the
              // pointer pointing to the address of next Node
              current = &(*current)->next;
        }
        size++;
    }
}
 
// This function prints contents
// of the linked list
void printList(struct Node* head)
{
    while (head != NULL) {
        cout << " " << head->data;
        head = head->next;
    }
    cout << endl;
}
 
// Driver Code
int main()
{
    // Creating the list 3->5->8->10
    Node* head = NULL;
    head = getNode(3);
    head->next = getNode(5);
    head->next->next = getNode(8);
    head->next->next->next = getNode(10);
 
    size = 4;
 
    cout << "Linked list before insertion: ";
    printList(head);
 
    int data = 12, pos = 3;
    insertPos(&head, pos, data);
    cout << "Linked list after insertion of 12 at position 3: ";
    printList(head);
 
    // front of the linked list
    data = 1, pos = 1;
    insertPos(&head, pos, data);
    cout << "Linked list after insertion of 1 at position 1: ";
    printList(head);
 
    // insetion at end of the linked list
    data = 15, pos = 7;
    insertPos(&head, pos, data);
    cout << "Linked list after insertion of 15 at position 7: ";
    printList(head);
 
    return 0;
}

Java

// Java program for insertion in a single linked
// list at a specified position
 
class GFG {
    // A linked list Node
    static class Node {
        public int data;
        public Node nextNode;
 
        // inserting the required data
        public Node(int data) {
            this.data = data;
 
        }
    }
 
    // function to create and return a Node
    static Node GetNode(int data) {
        return new Node(data);
    }
 
    // function to insert a Node at required position
    static Node InsertPos(Node headNode, int position, int data) {
        Node head = headNode;
        if (position < 1)
            System.out.print("Invalid position");
 
        // if position is 1 then new node is
        // set infornt of head node
        // head node is changing.
        if (position == 1) {
            Node newNode = new Node(data);
            newNode.nextNode = headNode;
            head = newNode;
        } else {
            while (position-- != 0) {
                if (position == 1) {
                    // adding Node at required position
                    Node newNode = GetNode(data);
 
                    // Making the new Node to point to
                    // the old Node at the same position
                    newNode.nextNode = headNode.nextNode;
 
                    // Replacing current with new Node
                    // to the old Node to point to the new Node
                    headNode.nextNode = newNode;
                    break;
                }
                headNode = headNode.nextNode;
            }
            if (position != 1)
                System.out.print("Position out of range");
        }
        return head;
    }
 
    static void PrintList(Node node) {
        while (node != null) {
            System.out.print(node.data);
            node = node.nextNode;
            if (node != null)
                System.out.print(",");
        }
        System.out.println();
    }
 
    // Driver code
    public static void main(String[] args) {
        Node head = GetNode(3);
        head.nextNode = GetNode(5);
        head.nextNode.nextNode = GetNode(8);
        head.nextNode.nextNode.nextNode = GetNode(10);
 
        System.out.print("Linked list before insertion: ");
        PrintList(head);
 
        int data = 12, pos = 3;
        head = InsertPos(head, pos, data);
        System.out.print("Linked list after" + " insertion of 12 at position 3: ");
        PrintList(head);
 
        // front of the linked list
        data = 1;
        pos = 1;
        head = InsertPos(head, pos, data);
        System.out.print("Linked list after" + "insertion of 1 at position 1: ");
        PrintList(head);
 
        // insetion at end of the linked list
        data = 15;
        pos = 7;
        head = InsertPos(head, pos, data);
        System.out.print("Linked list after" + " insertion of 15 at position 7: ");
        PrintList(head);
    }
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for insertion in a single linked
# list at a specified position
  
# A linked list Node
class Node: 
    def __init__(self, data):   
        self.data = data
        self.nextNode = None
  
# function to create and return a Node
def getNode(data):
 
    # allocating space
    newNode = Node(data)
    return newNode;
 
# function to insert a Node at required position
def insertPos(headNode, position, data):
    head = headNode
     
    # This condition to check whether the
    # position given is valid or not.
    if (position < 1):       
        print("Invalid position!")
     
    if position == 1:
        newNode = Node(data)
        newNode.nextNode = headNode
        head = newNode
             
    else:
       
        # Keep looping until the position is zero
        while (position != 0):          
            position -= 1
  
            if (position == 1):
  
               # adding Node at required position
               newNode = getNode(data)
 
               # Making the new Node to point to
               # the old Node at the same position
               newNode.nextNode = headNode.nextNode
 
               # Replacing headNode with new Node
               # to the old Node to point to the new Node
               headNode.nextNode = newNode
               break
             
            headNode = headNode.nextNode
            if headNode == None:
                break           
        if position != 1:
              print("position out of range")       
    return head
      
# This function prints contents
# of the linked list
def printList(head):
    while (head != None):      
        print(" " + str(head.data), end = "")
        head = head.nextNode;   
    print()
      
# Driver Code
if __name__=="__main__":
     
    # Creating the list 3.5.8.10
    head = getNode(3);
    head.nextNode = getNode(5);
    head.nextNode.nextNode = getNode(8);
    head.nextNode.nextNode.nextNode = getNode(10);
    print("Linked list before insertion: ", end="")
    printList(head);
    data = 12
    position = 3;
    head = insertPos(head, position, data);
    print("Linked list after insertion of 12 at position 3: ", end = "")
    printList(head);
  
    # front of the linked list
    data = 1
    position = 1;
    head = insertPos(head, position, data);
    print("Linked list after insertion of 1 at position 1: ", end = "")
    printList(head);
  
    # insetion at end of the linked list
    data = 15
    position = 7;
    head = insertPos(head, position, data);
    print("Linked list after insertion of 15 at position 7: ", end="")
    printList(head);
 
# This code iscontributed by rutvik_56

C#

// C# program for insertion in a single linked
// list at a specified position
using System;
 
namespace InsertIntoLinkedList
{
    class Program
    {
        // A linked list Node
        private class Node
        {
            public int data;
            public Node nextNode;
 
            // inserting the required data
            public Node(int data) => this.data = data;
        }
 
        // function to create and return a Node
        static Node GetNode(int data) => new Node(data);
 
        // function to insert a Node at required position
        static Node InsertPos(Node headNode,
                            int position, int data)
        {
            var head = headNode;
            if (position < 1)
                Console.WriteLine("Invalid position");
 
            //if position is 1 then new node is
            // set infornt of head node
            //head node is changing.
            if (position == 1)
            {
                var newNode = new Node(data);
                newNode.nextNode = headNode;
                head = newNode;
            }
            else
            {
                while (position-- != 0)
                {
                    if (position == 1)
                    {
                        // adding Node at required position
                        Node newNode = GetNode(data);
 
                        // Making the new Node to point to
                        // the old Node at the same position
                        newNode.nextNode = headNode.nextNode;
 
           &n
Структуры данных

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

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022