Lista enlazada individualmente en estructuras de datos
sarah chen
¿Qué es una lista enlazada individualmente?
La lista enlazada individualmente es una estructura de datos lineal y unidireccional, donde los datos se guardan en los nodos y cada nodo se conecta mediante un enlace a su siguiente nodo. Cada nodo contiene un campo de datos y un enlace al siguiente nodo. Las listas enlazadas individualmente se pueden recorrer en una sola dirección, mientras que las listas doblemente enlazadas se pueden recorrer en ambas direcciones.
Aquí hay una estructura de nodos de una lista enlazada individualmente:
¿Por qué utilizar una lista vinculada en lugar de una matriz?
Hay varios casos en los que es mejor utilizar la lista enlazada en lugar de la Formación. Aquí hay algunos escenarios:
- Número desconocido de elementos: Cuando no sepa cuántos elementos necesita almacenar durante el tiempo de ejecución del programa, puede utilizar la Lista vinculada. La memoria se asigna dinámicamente a medida que agrega elementos a las listas vinculadas.
- Acceso aleatorio: En un escenario en el que no necesita utilizar el acceso aleatorio desde los elementos, puede utilizar la lista vinculada.
- Inserción en el medio: La inserción en el medio de una matriz es una tarea compleja, ya que es necesario colocar otros elementos a la derecha. Sin embargo, una lista enlazada permite agregar un elemento en cualquier posición que se desee.
Operaciones de lista enlazada individualmente
La lista enlazada simple es útil para asignar memoria de forma dinámica. Proporciona todas las operaciones básicas de la lista enlazada, es decir, inserción, eliminación, búsqueda, actualización, fusión de dos listas enlazadas, recorrido, etc.
Aquí discutiremos la siguiente operación de la lista enlazada:
- Insertando en la cabeza
- Insertando en la cola
- Insertar después de un nodo
- Insertar antes de un nodo
- Eliminar el nodo principal
- Eliminar el nodo de cola
- Buscar y eliminar un nodo
- Atravesando la lista enlazada
A continuación se muestra un ejemplo de una lista vinculada con cuatro nodos.
Inserción al principio de una lista enlazada individualmente
Se trata de una operación sencilla. Generalmente, se la conoce como inserción de una lista enlazada simple. Debe crear un nuevo nodo y colocarlo al principio de la lista enlazada.
Para realizar esta operación, debemos cumplir dos condiciones importantes. Son:
- Si la lista está vacía, entonces el nodo recién creado será el nodo principal y el siguiente nodo principal será "NULL".
- Si la lista no está vacía, el nuevo nodo será el nodo principal y el siguiente apuntará al nodo principal anterior.
Aquí está el pseudocódigo para insertar un nodo al principio de una lista vinculada:
function insertAtHead( head, value ): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
Inserción al final de una lista enlazada individualmente
Insertar un nodo al final de una lista vinculada tiene algunas similitudes con insertar en el encabezado. Todo lo que necesita hacer es atravesar hasta el nodo final o el nodo de cola. Luego apunte el "siguiente" nodo del nodo final al nodo recién creado. Si el nodo principal es nulo, el nuevo nodo será el nodo principal.
Aquí están los pasos:
Paso 1) Recorra hasta que el "siguiente" nodo del nodo actual se vuelva nulo.
Paso 2) Cree un nuevo nodo con el valor especificado.
Paso 3) Asigne el nuevo nodo como el siguiente nodo del nodo de cola.
El pseudocódigo para insertar un nodo al final de una lista individual:
function insertAtEnd( head, value ): newNode = Node(value) if head is NULL: head = newNode return head while head.next is not NULL: then head = head.next head.next = newNode newNode.next = NULL
Inserción después de un nodo en una lista enlazada individualmente
Insertar después de un nodo tiene dos partes: buscar el nodo y adjuntarlo después del nodo buscado. Necesitamos atravesar todos los nodos. Para cada nodo, debemos hacer coincidir el elemento de búsqueda. Si hay una coincidencia, agregaremos el nuevo nodo después del nodo buscado.
Aquí están los pasos:
Paso 1) Recorra el siguiente nodo hasta que el valor del nodo actual sea igual al elemento de búsqueda.
Paso 2) El siguiente puntero del nuevo nodo será el siguiente puntero del nodo actual.
Paso 3) El siguiente nodo del nodo actual será el nuevo nodo.
Aquí está el pseudocódigo para insertar un nodo tras otro:
function insertAfter( head, value, searchItem ): newNode = Node(value) while head.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
Inserción antes de un nodo en una lista enlazada individualmente
Esta función es muy similar a la inserción después de un nodo. Debemos crear un nuevo nodo y recorrer la lista vinculada hasta que el nodo actual coincida con el nodo de búsqueda. Después de eso, agregaremos el nuevo nodo como el nodo anterior del nodo actual.
Aquí están los pasos:
Paso 1) Recorra hasta que el valor del siguiente nodo sea igual al elemento de búsqueda.
Paso 2) Cree un nuevo nodo y asigne el "siguiente" del nodo con el siguiente al siguiente nodo del nodo actual.
Paso 3) Asigne el nuevo nodo como el siguiente nodo del nodo actual.
Aquí está el pseudocódigo:
function insertBefore( head, value, searchItem ): newNode = Node(value) while head.next.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
Eliminar el encabezado de la lista enlazada individualmente
En cada función de la lista enlazada, el puntero principal se proporciona como parámetro. Es necesario eliminar el nodo principal y hacer que el siguiente nodo del nodo principal sea el nuevo puntero principal de la lista enlazada. También es necesario liberar la memoria del nodo eliminado. De lo contrario, la memoria se marcará como ocupada cuando otro programa intente acceder a ella.
Estos son los pasos para eliminar el encabezado de la lista enlazada individualmente:
Paso 1) Asigne el siguiente nodo del nodo principal como el nuevo principal.
Paso 2) Libere la memoria asignada por el nodo principal anterior.
Paso 3) Devuelve el nuevo nodo principal.
El pseudocódigo para eliminar el nodo principal:
function deleteHead( head ): temp = head head = head.next free( temp ) return head
Eliminar la cola de la lista enlazada individualmente
Eliminar el nodo de cola es más familiar que eliminar el nodo principal. La diferencia es que debemos llegar al final de la lista vinculada y eliminarla. En la lista enlazada individualmente, el nodo cuyo siguiente nodo es "NULL" es el nodo de cola.
Estos son los pasos para eliminar el nodo final de la lista vinculada:
Paso 1) Atraviesa antes del nodo de cola. Guarde el nodo actual.
Paso 2) Libera la memoria del siguiente nodo del nodo actual.
Paso 3) Establezca el siguiente nodo del nodo actual como NULL.
Aquí está el pseudocódigo para eliminar el nodo de cola:
function deleteTail( head ): while head.next.next is not NULL: head = head.next free( head.next ) head.next = NULL
Buscar y eliminar un nodo de una lista enlazada individualmente
Esta función tiene dos tareas, buscar y eliminar. Necesitamos buscar hasta el final de las listas enlazadas individualmente. Si encontramos algún nodo similar, lo eliminaremos. Después de eso, debemos fusionar o vincular los nodos izquierdo y derecho del nodo eliminado. Estos son los pasos para hacer esto:
Paso 1) Recorre hasta el final de la lista enlazada. Compruebe si el nodo actual es igual al nodo de búsqueda o no.
Paso 2) Si algún nodo coincide, almacene el puntero del nodo al nodo actual.
Paso 3) El “siguiente” del nodo anterior será el siguiente nodo del nodo actual.
Paso 4) Eliminar y liberar la memoria del nodo actual.
Pseudocódigo para buscar y eliminar un nodo de una lista enlazada individualmente:
function searchAndDelete( head, searchItem ): while head.next.next is not NULL and head.next.value is not equals searchItem : head = head.next head.next = head.next.next delete(head.next)
Recorrer una lista enlazada individualmente
La lista enlazada individualmente solo tiene la funcionalidad de atravesar de principio a fin. No hay puntos de puntero al nodo anterior; es por eso que no podemos recorrer la lista enlazada individualmente en orden inverso. Atravesaremos cada nodo e imprimiremos el valor del nodo actual hasta que obtengamos nulo.
Aquí están los pasos:
Paso 1) Recorre cada nodo hasta que obtengamos nulo como el siguiente nodo.
Paso 2) Imprime el valor del nodo actual.
Pseudocódigo para recorrer una lista enlazada individualmente:
function traverse( head ): while head.next is not NULL: print the value of the head head = head.next
Ejemplo de lista enlazada individualmente en C++
#include<iostream>
using namespace std;
struct Node{
int data;
struct Node *next;
};
void insertAtHead(Node* &head, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
if(head!=NULL){
newNode->next = head;
}
head = newNode;
cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
if(head==NULL){
insertAtHead(head,value);
}
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *temp = head;
while(temp->next!=NULL){
temp = temp->next;
}
temp->next = newNode;
cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
Node *temp = new Node();
if( (*headPtr)->data == searchItem ){
temp = *headPtr;
*headPtr = (*headPtr)->next;
free(temp);
}else{
Node *currentNode = *headPtr;
while(currentNode->next != NULL){
if(currentNode->next->data == searchItem){
temp = currentNode->next;
currentNode->next = currentNode->next->next;
free(temp);
}else{
currentNode = currentNode->next;
}
}
}
cout<<"Deleted Node\t"<<searchItem<<endl;
return;
}
void insertAfter(Node * &headPtr, int searchItem, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *head = headPtr;
while(head->next!=NULL && head->data!=searchItem){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node * &headPtr, int searchItem, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *head = headPtr;
while(head->next!=NULL && head->next->data!=searchItem){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){
Node* tempNode = new Node();
tempNode = headPointer;
cout<<"Traversal from head:\t";
while(tempNode !=NULL){
cout<<tempNode->data;
if(tempNode->next)
cout<<" --> ";
tempNode = tempNode ->next;
}
cout<<endl;
}
int main(){
Node *head = NULL;
insertAtHead(head,5);
insertAtHead(head,6);
insertAtHead(head,7);
insertEnd(head,9);
traverse(head);
searchAndDelete(&head,6);
traverse(head);
insertAfter(head,7,10);
insertBefore(head,9,11);
traverse(head);
}
Salida:
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Traversal from head: 7 → 6 → 5 → 9 Deleted Node 6 Traversal from head: 7 → 5 → 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversal from head: 7 → 10 → 5 → 11 → 9
Ejemplo de lista enlazada individualmente en Python Programa
class Node:
def __init__(self,data = None, next = None):
self.data = data
self.next = next
class SinglyLinkedList:
def __init__(self):
self.head = None
def insertAtHead(self, value):
newNode = Node(data=value)
if self.head is not None:
newNode.next = self.head
self.head = newNode
print(f'Added {newNode.data} at the front.')
return
def insertAtEnd(self,value):
if self.head is None:
self.insertAtHead(value)
newNode = Node(value)
temp = self.head
while temp.next is not None:
temp = temp.next
temp.next = newNode
print(f'Added {newNode.data} at the end.')
def searchAndDelete(self,searchItem):
temp = Node()
if self.head is searchItem:
temp = self.head
self.head = self.head.next
else:
currentNode = self.head
while currentNode.next is not None:
if currentNode.next.data is searchItem:
temp = currentNode.next
currentNode.next = currentNode.next.next
else:
currentNode = currentNode.next
print(f'Deleted node\t{searchItem}')
return
def insertAfter(self,searchItem,value):
newNode = Node(data=value)
temp = self.head
while temp.next is not None and temp.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
print(f'Inserted {value} after node\t{searchItem}')
return
def insertbefore(self,searchItem,value):
newNode = Node(data=value)
temp = self.head
while temp.next is not None and temp.next.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
print(f'Inserted {value} before node\t{searchItem}')
return
def traverse(self):
temp = self.head
print("Traversing from head:\t",end="")
while temp:
print("{}\t".format(temp.data),end="")
temp = temp.next
print()
SinglyLinkedList = SinglyLinkedList()
SinglyLinkedList.insertAtHead(5)
SinglyLinkedList.insertAtHead(6)
SinglyLinkedList.insertAtHead(7)
SinglyLinkedList.insertAtEnd(9)
SinglyLinkedList.traverse()
SinglyLinkedList.searchAndDelete(6)
SinglyLinkedList.traverse()
SinglyLinkedList.insertAfter(7,10)
SinglyLinkedList.insertbefore(9, 11)
SinglyLinkedList.traverse()
Salida:
Added 5 at the front. Added 6 at the front. Added 7 at the front. Added 9 at the end. Traversing from head: 7 6 5 9 Deleted node 6 Traversing from head: 7 5 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversing from head: 7 10 5 11 9
Complejidad de una lista enlazada simple
Existen dos tipos de complejidad: complejidad temporal y complejidad espacial. La complejidad temporal del peor de los casos y la complejidad temporal del caso promedio son las mismas para la lista enlazada simple.
La complejidad temporal para el mejor caso:
- La inserción en la cabeza se puede realizar en O(1). Como no necesitamos atravesar el interior de la lista vinculada.
- La operación de búsqueda y eliminación se puede realizar en O(1) si el elemento de búsqueda está presente en el nodo principal.
La complejidad temporal para el caso promedio:
- La inserción dentro de una lista enlazada tomará O(n) si hay "n" elementos presentes en la lista enlazada individualmente.
- Buscar y eliminar también pueden tomar O(n), ya que el elemento de búsqueda puede estar presente en el nodo de cola. En ese caso, debes recorrer toda la lista.
Complejidad espacial de una lista enlazada simple
La lista enlazada simple asigna memoria de forma dinámica. Si queremos almacenar n elementos, asignará n unidades de memoria. Por lo tanto, la complejidad espacial es O(n).
