Lista enlazada individualmente en estructuras de datos

¿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:

Estructura de un nodo en una lista enlazada
Estructura de un nodo en una lista enlazada

¿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 medio de una matriz es una complex tarea. Porque necesitas empujar otros elementos hacia la derecha. Sin embargo, una Lista vinculada le permite agregar un elemento a cualquier posición que desee.

Operaciones de lista enlazada individualmente

La lista enlazada individualmente es buena para asignar memoria dinámicamente. Proporciona todo lo básico operaciones de la lista enlazada, es decir, inserción, eliminación, searching, actualización, fusión de dos listas enlazadas, recorrido, etc.

Aquí discutiremos lo siguiente.wing 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.

Ejemplo de una lista enlazada individualmente
Ejemplo de una lista enlazada individualmente

Inserción al principio de una lista enlazada individualmente

Este es un simple operación. Generalmente, se conoce como enviar una lista enlazada individualmente. Debe crear un nuevo nodo y colocarlo al principio de la lista vinculada.

Para realizar esto operación, debemos seguir dos condiciones importantes. Ellos son

  1. Si la lista está vacía, entonces el nodo recién creado será el nodo principal y el siguiente nodo principal será "NULL".
  2. 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 en la cabeza
Insertando en la cabeza

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
Insertando en la cola
Insertando en la cola

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
Insertar un nodo después de un nodo en una lista enlazada individualmente
Insertar un nodo después de un nodo en la lista enlazada individualmente

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
Insertar un nodo antes de un nodo en una lista enlazada individualmente
Insertar un nodo antes de un nodo en la lista enlazada individualmente

Eliminar el encabezado de la lista enlazada individualmente

En cada función de la lista vinculada, el puntero principal se proporciona como parámetro. Debe eliminar el nodo principal y convertir el siguiente nodo del nodo principal en el nuevo encabezado de la lista vinculada. También necesitamos liberar la memoria del nodo eliminado. Otrowise, 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 el encabezado de una lista vinculada
Eliminar el encabezado de una lista vinculada

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
Eliminar la cola de la lista enlazada individualmente
Eliminar la cola de la lista enlazada individualmente

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)
Buscar y eliminar un nodo de la lista enlazada individualmente
Buscar y eliminar un nodo de la lista enlazada individualmente

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 un programa Python

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

¿Cómoplexidad de la lista enlazada individualmente

Hay dos tipos de complexciudad: tiempo complexciudad y espacio complexidad. El peor y promedio de los casos.plexLa calidad es la misma para la lista enlazada individualmente.

el tiempo complexidad para el mejor de los casos:

  • La inserción en la cabeza se puede realizar en O(1). Como no necesitamos atravesar el interior de la lista vinculada.
  • Buscar y eliminar operaLa operación se puede realizar en O(1) si el elemento de búsqueda está presente en el nodo principal.

el tiempo complexidad 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.

Espacio Complexidad de la lista enlazada individualmente

La lista enlazada individualmente asigna memoria dinámicamente. Si queremos almacenar n elementos, asignará n unidades de memoria. Entonces, la comunicación espacialplexLa ciudad es O(n).