Dada una lista enlazada, una posición y un elemento, la tarea es escribir un programa para insertar ese elemento en una lista enlazada en una posición dada.
Ejemplos:
Input: 3->5->8->10, data = 2, position = 2 Output: 3->2->5->8->10 Input: 3->5->8->10, data = 11, position = 5 Output: 3->5->8->10->11
Enfoque: para insertar un dato dado en una posición específica, se debe seguir el siguiente algoritmo:
- Atraviese la lista Vinculada hasta los Nodes de posición 1 .
- Una vez que se recorren todos los Nodes de la posición 1 , asigne memoria y los datos proporcionados al nuevo Node.
- Apunte el siguiente puntero del nuevo Node al siguiente del Node actual.
- Apunte el siguiente puntero del Node actual al nuevo Node.
A continuación se muestra la implementación del algoritmo anterior.
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);
// insertion 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);
// insertion 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);
# insertion 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;
// 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)
Console.WriteLine("Position out of range");
}
return head;
}
static void PrintList(Node node)
{
while (node != null)
{
Console.Write(node.data);
node = node.nextNode;
if(node != null)
Console.Write(",");
}
Console.WriteLine();
}
// Driver code
static void Main(string[] args)
{
var head = GetNode(3);
head.nextNode = GetNode(5);
head.nextNode.nextNode = GetNode(8);
head.nextNode.nextNode.nextNode = GetNode(10);
Console.WriteLine("Linked list before insertion: ");
PrintList(head);
int data = 12, pos = 3;
head = InsertPos(head, pos, data);
Console.WriteLine("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);
Console.WriteLine("Linked list after" +
"insertion of 1 at position 1: ");
PrintList(head);
// insertion at end of the linked list
data = 15; pos = 7;
head = InsertPos(head, pos, data);
Console.WriteLine("Linked list after" +
" insertion of 15 at position 7: ");
PrintList(head);
}
}
}
// This code is contributed by dhirucoool
Javascript
<script>
// javascript program for insertion in a single linked
// list at a specified position // A linked list Node
class Node {
// inserting the required data
constructor(val) {
this.data = val;
this.nextNode = null;
}
}
// function to create and return a Node
function GetNode(data) {
return new Node(data);
}
// function to insert a Node at required position
function InsertPos( headNode , position , data) {
head = headNode;
if (position < 1)
document.write("Invalid position");
// if position is 1 then new node is
// set infront of head node
// head node is changing.
if (position == 1) {
newNode = new Node(data);
newNode.nextNode = headNode;
head = newNode;
}
else
{
while (position-- != 0)
{
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 current with new Node
// to the old Node to point to the new Node
headNode.nextNode = newNode;
break;
}
headNode = headNode.nextNode;
}
if (position != 1)
document.write("Position out of range");
}
return head;
}
function PrintList( node) {
while (node != null) {
document.write(node.data);
node = node.nextNode;
if (node != null)
document.write(",");
}
document.write("<br/>");
}
// Driver code
head = GetNode(3);
head.nextNode = GetNode(5);
head.nextNode.nextNode = GetNode(8);
head.nextNode.nextNode.nextNode = GetNode(10);
document.write("Linked list before insertion: ");
PrintList(head);
var data = 12, pos = 3;
head = InsertPos(head, pos, data);
document.write("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);
document.write("Linked list after" + "insertion of 1 at position 1: ");
PrintList(head);
// insertion at end of the linked list
data = 15;
pos = 7;
head = InsertPos(head, pos, data);
document.write("Linked list after" + " insertion of 15 at position 7: ");
PrintList(head);
// This code is contributed by gauravrajput1.
</script>
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por Prasoon_Mishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA