Requisito previo:
Lista vinculada Estructura de datos
Pila vs Heap Asignación de memoria
La lista enlazada es una estructura de datos lineal, en la que los elementos no se almacenan en ubicaciones de memoria contiguas. Los elementos de una lista enlazada se enlazan mediante punteros . Se implementa en la memoria del montón en lugar de la memoria de la pila . Este artículo analiza la razón detrás de esto.
Pila vs Memoria Heap
La memoria de la computadora se divide en segmentos de memoria de pila y pila. El segmento de memoria de pila es relativamente pequeño, por lo que se usa principalmente para operaciones como recursividad o declaraciones de salto de control como la declaración goto. Debido al pequeño tamaño del segmento de la pila, no se usa para niveles de recursividad profundos, ya que puede generar un error de desbordamiento de la pila.
Por otro lado, una lista enlazada tiene la gran ventaja de expandirse dinámicamente cuando sea necesario sin preocuparse por el consumo de memoria. Esta es la razón por la que se prefiere el montón para almacenar objetos de lista vinculados.
¿Por qué la lista enlazada no se almacena en la memoria de pila?
La pregunta de por qué no se puede hacer una lista enlazada con la memoria de la pila se debe a las reglas de alcance y la gestión automática de la memoria en la pila. La idea básica de una lista enlazada es enlazar Nodes en función de su dirección de memoria. Si cada Node se crea en la pila, esos Nodes se eliminarán después de que queden fuera del alcance, por lo que incluso si el usuario mantiene los punteros a su dirección de memoria, no es seguro asumir que no serán sobrescritos por otra cosa.
La lista enlazada también se puede implementar en la memoria de pila . A continuación se muestra la implementación en C++ de la creación de una lista enlazada en la memoria de pila:
C++
// C++ program to implement
// linked list in stack
#include <iostream>
using namespace std;
// Structure of the linked list
struct Node {
int data;
struct Node* next;
// Constructor
Node(int x)
{
data = x;
next = NULL;
}
}* head = NULL;
// Function to print the linked list
void printLinkedList(Node* head)
{
struct Node* temp = head;
// Traversing linked list
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
}
// Driver code
int main()
{
// Creation of linked list in stack
struct Node first = Node(1);
struct Node second = Node(2);
struct Node third = Node(3);
struct Node fourth = Node(4);
head = &first;
// 1 -> 2 -> 3 -> 4
first.next = &second;
second.next = &third;
third.next = &fourth;
fourth.next = NULL;
// Printing the elements of
// a linked list
printLinkedList(head);
return 0;
}
Java
// Java program to implement
// linked list in stack
import java.util.*;
class GFG{
// Structure of the linked list
static class Node {
int data;
Node next;
// Constructor
Node(int x)
{
data = x;
next = null;
}
};
static Node head = null;
// Function to print the linked list
static void printLinkedList(Node head)
{
Node temp = head;
// Traversing linked list
while (temp!=null) {
System.out.print(temp.data+ " ");
temp = temp.next;
}
}
// Driver code
public static void main(String[] args)
{
// Creation of linked list in stack
Node first = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
head = first;
// 1.2.3.4
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = null;
// Printing the elements of
// a linked list
printLinkedList(head);
}
}
// This code contributed by shikhasingrajput
C#
// C# program to implement
// linked list in stack
using System;
using System.Collections.Generic;
public class GFG{
// Structure of the linked list
class Node {
public int data;
public Node next;
// Constructor
public Node(int x)
{
data = x;
next = null;
}
};
static Node head = null;
// Function to print the linked list
static void printList(Node head)
{
Node temp = head;
// Traversing linked list
while (temp!=null) {
Console.Write(temp.data+ " ");
temp = temp.next;
}
}
// Driver code
public static void Main(String[] args)
{
// Creation of linked list in stack
Node first = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
head = first;
// 1.2.3.4
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = null;
// Printing the elements of
// a linked list
printList(head);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// linked list in stack
// Structure of the linked list
class Node {
// Constructor
constructor(x) {
this.data = x;
this.next = null;
}
}
// Function to print the linked list
function printLinkedList(head) {
let temp = head;
// Traversing linked list
while (temp) {
document.write(temp.data + " ");
temp = temp.next;
}
}
// Driver code
// Creation of linked list in stack
let first = new Node(1);
let second = new Node(2);
let third = new Node(3);
let fourth = new Node(4);
head = first;
// 1 -> 2 -> 3 -> 4
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = null;
// Printing the elements of
// a linked list
printLinkedList(head);
// This code is contributed by gfgking.
</script>
Producción:
1 2 3 4
Condición cuando la implementación de la lista vinculada en la pila no funcionará:
El código anterior no funcionará si escribimos la lógica de la creación de una lista enlazada en una función separada y la lógica de imprimir los elementos de la lista enlazada en una función separada. A continuación se muestra su implementación en C++ del concepto anterior:
C++
// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
// Structure of the linked list
struct Node {
int data;
struct Node* next;
Node(int x)
{
data = x;
next = NULL;
}
}* head = NULL;
// Function to return the head pointer
// of the created linked list
Node* CreateLinkedList()
{
struct Node first = Node(1);
struct Node second = Node(2);
struct Node third = Node(3);
struct Node fourth = Node(4);
head = &first;
// 1->2->3->4
first.next = &second;
second.next = &third;
third.next = &fourth;
fourth.next = NULL;
return head;
}
// Function to print the linked list
void printLinkedList(Node* head)
{
struct Node* temp = head;
// Traversing linked list
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
}
// Driver Code
int main()
{
struct Node* head = CreateLinkedList();
printLinkedList(head);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Structure of the linked list
static class Node {
int data;
Node next;
Node(int x)
{
data = x;
next = null;
}
}
static Node head = null;
// Function to return the head pointer
// of the created linked list
static Node CreateLinkedList()
{
Node first = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
head = first;
// 1.2.3.4
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = null;
return head;
}
// Function to print the linked list
static void printLinkedList(Node head)
{
Node temp = head;
// Traversing linked list
while (temp!=null) {
System.out.print(temp.data+ " ");
temp = temp.next;
}
}
// Driver Code
public static void main(String[] args)
{
Node head = CreateLinkedList();
printLinkedList(head);
}
}
// This code is contributed by 29AjayKumar
C#
// C# program to implement
// the above approach
using System;
public class GFG{
// Structure of the linked list
class Node {
public int data;
public Node next;
public Node(int x)
{
data = x;
next = null;
}
}
static Node head = null;
// Function to return the head pointer
// of the created linked list
static Node CreateList()
{
Node first = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
head = first;
// 1.2.3.4
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = null;
return head;
}
// Function to print the linked list
static void printList(Node head)
{
Node temp = head;
// Traversing linked list
while (temp != null) {
Console.Write(temp.data + " ");
temp = temp.next;
}
}
// Driver Code
public static void Main(String[] args)
{
Node head = CreateList();
printList(head);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// javascript program to implement
// the above approach // Structure of the linked list
class Node
{
constructor( x) {
this.data = x;
this.next = null;
}
}
var head = null;
// Function to return the head pointer
// of the created linked list
function CreateLinkedList() {
var first = new Node(1);
var second = new Node(2);
var third = new Node(3);
var fourth = new Node(4);
head = first;
// 1.2.3.4
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = null;
return head;
}
// Function to print the linked list
function printLinkedList( head) {
var temp = head;
// Traversing linked list
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
}
// Driver Code
var head = CreateLinkedList();
printLinkedList(head);
// This code contributed by shikhasingrajput
</script>
Explicación:
El código anterior da el veredicto como FALLA DE SEGMENTACIÓN . La razón detrás de esto es que durante la creación de la lista enlazada en la memoria de la pila, todos los objetos creados por una función desaparecerán a medida que se abre el marco de la pila cada vez que la función finaliza o regresa. Consulte este artículo para conocer la razón detrás de la aparición del marco de pila cada vez que finaliza la función.
¿Por qué la lista vinculada se almacena en la memoria del montón?
En una lista enlazada, cuando es necesario almacenar más datos, podemos asignar la memoria en tiempo de ejecución usando malloc o una nueva función en C/C++. Por lo tanto, la asignación de memoria dinámica reserva el tamaño del área del montón, por lo tanto, una lista vinculada se almacena en la memoria del montón.
Si es necesario almacenar listas vinculadas en el área de la pila, implemente listas vinculadas sin usar malloc o una nueva función.
A continuación se muestra el programa C++ para mostrar cómo implementar una lista vinculada en la memoria del montón sin generar un error de falla de segmentación:
C++
// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
// Structure of the linked list
struct Node {
int data;
struct Node* next;
};
struct Node* head = NULL;
// Function to create nodes of
// the linked list
void CreateLinkedList(int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
// Function to print the linked list
void printLinkedList()
{
struct Node* temp;
temp = head;
// Traversing linked list
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
// Driver Code
int main()
{
CreateLinkedList(1);
CreateLinkedList(2);
CreateLinkedList(3);
CreateLinkedList(4);
printLinkedList();
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
public class GFG{
// Structure of the linked list
static class Node {
int data;
Node next;
};
static Node head = null;
// Function to create nodes of
// the linked list
static void CreateLinkedList(int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head;
head = new_node;
}
// Function to print the linked list
static void printLinkedList()
{
Node temp;
temp = head;
// Traversing linked list
while (temp != null) {
System.out.print(temp.data+ " ");
temp = temp.next;
}
}
// Driver Code
public static void main(String[] args)
{
CreateLinkedList(1);
CreateLinkedList(2);
CreateLinkedList(3);
CreateLinkedList(4);
printLinkedList();
}
}
// This code is contributed by 29AjayKumar
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Structure of the linked list
public class Node {
public int data;
public Node next;
};
static Node head = null;
// Function to create nodes of
// the linked list
static void CreateList(int new_data) {
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head;
head = new_node;
}
// Function to print the linked list
static void printList() {
Node temp;
temp = head;
// Traversing linked list
while (temp != null) {
Console.Write(temp.data + " ");
temp = temp.next;
}
}
// Driver Code
public static void Main(String[] args) {
CreateList(1);
CreateList(2);
CreateList(3);
CreateList(4);
printList();
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program to implement
// the above approach
// Structure of the linked list
class Node {
constructor(){
this.data = 0;
this.next = null;
}
}
var head = null;
// Function to create nodes of
// the linked list
function CreateLinkedList(new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = head;
head = new_node;
}
// Function to print the linked list
function printLinkedList()
{
var temp;
temp = head;
// Traversing linked list
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
}
// Driver Code
CreateLinkedList(1);
CreateLinkedList(2);
CreateLinkedList(3);
CreateLinkedList(4);
printLinkedList();
// This code is contributed by umadevi9616
</script>
Producción:
4 3 2 1
Lista vinculada en Stack vs Heap Memory
| No. S. | Lista vinculada en la memoria de pila | Lista vinculada en la memoria del montón |
| 1 | La lista vinculada en la pila obtendrá acceso a una memoria relativamente pequeña que no se puede expandir dinámicamente. | La lista vinculada en el montón obtendrá acceso a la memoria dinámicamente expandible. |
| 2 | Cada Node creado en la lista vinculada y almacenado en la pila se vinculará y eliminará después de que quede fuera del alcance. | Es necesario liberar la memoria para que se elimine el Node. |
| 3 | Si es necesario almacenar una lista vinculada en el área de la pila, implemente una lista vinculada sin usar malloc o una nueva función. | Si es necesario almacenar la lista vinculada en el montón, implemente la lista vinculada utilizando malloc o la nueva función. |
| 4 | No se puede acceder a los Nodes de la lista vinculada creados en la pila una vez que finaliza el alcance de la función. | Se puede acceder a los Nodes de la lista vinculada creados y almacenados en la memoria del montón una vez que finaliza el alcance de la función. |