Estructuras de datos explicadas con ejemplos: lista vinculada

Programación

Al igual que una guirnalda está hecha con flores, una lista enlazada está formada por nodos. Llamamos a cada flor de esta guirnalda en particular a ser un nodo. Y cada uno de los nodos apunta al siguiente nodo de esta lista y tiene datos (aquí es el tipo de flor).

Tipos

Lista individualmente vinculada

Las listas enlazadas individualmente contienen nodos que tienen un datacampo y un nextcampo, que apunta al siguiente nodo de la secuencia. Las operaciones que se pueden realizar en listas vinculadas individualmente son inserción, eliminación y recorrido.

 head | | +-----+--+ +-----+--+ +-----+------+ | 1 |o-----> | 2 |o-----> | 3 | NULL | +-----+--+ +-----+--+ +-----+------+

Implementación interna de CPython, los marcos y las variables evaluadas se mantienen en una pila.

Para esto, necesitamos iterar solo hacia adelante aur obtener la cabeza, por lo tanto, se usa una lista vinculada individualmente.

Lista doblemente vinculada

Las listas doblemente enlazadas contienen un nodo que tiene un datacampo, un nextcampo y otro campo de enlace que prevapunta al nodo anterior en la secuencia.

 head | | +------+-----+--+ +--+-----+--+ +-----+------+ | | |o------> | |o------> | | | | NULL | 1 | | 2 | | 3 | NULL | | | | <------o| | <------o| | | +------+-----+--+ +--+-----+--+ +-----+------+

La caché del navegador que le permite presionar el botón ATRÁS y ADELANTE. Aquí necesitamos mantener una lista doblemente enlazada, con URLsun campo de datos, para permitir el acceso en ambas direcciones. Para ir a la URL anterior usaremos prevfield y para ir a la página siguiente usaremos nextfield.

Lista enlazada circular

Las listas enlazadas circulares es una lista enlazada individualmente en la que el último nodo, el nextcampo apunta al primer nodo de la secuencia.

 head | | +-----+--+ +-----+--+ +-----+--+ —> | 1 |o-----> | 2 |o-----> | 3 |o----| +-----+--+ +-----+--+ +-----+--+

Problema de tiempo compartido resuelto por el sistema operativo.

En un entorno de tiempo compartido, el sistema operativo debe mantener una lista de usuarios presentes y debe permitir que cada usuario use una pequeña porción del tiempo de la CPU, un usuario a la vez. El sistema operativo elegirá un usuario, le permitirá usar una pequeña cantidad de tiempo de CPU y luego pasará al siguiente usuario.

Para esta aplicación, no debería haber punteros NULL a menos que no haya absolutamente nadie solicitando tiempo de CPU, es decir, la lista está vacía.

Operaciones básicas

Inserción

Para agregar un nuevo elemento a la lista.

Inserción al principio:

  • Crea un nuevo nodo con los datos dados.
  • Apunta los nuevos nodos nexta los viejos head.
  • Señale headeste nuevo nodo.

Inserción en el medio / final.

Inserción después del nodo X.

  • Crea un nuevo nodo con los datos dados.
  • Punto nuevo nodo es nextde edad de X next.
  • Apunta X nexta este nuevo nodo.

Complejidad del tiempo: O (1)

Supresión

Para eliminar un elemento existente de la lista.

Eliminación al principio

  • Obtenga el nodo señalado headcomo Temp.
  • Apunta heada Temp's next.
  • Memoria libre utilizada por el nodo Temp.

Eliminación en el medio / final.

Eliminación después del nodo X.

  • Obtenga el nodo señalado Xcomo Temp.
  • Punto X nexta Temp next.
  • Memoria libre utilizada por el nodo Temp.

Complejidad del tiempo: O (1)

Atravesar

Viajar por la lista.

El recorrido

  • Obtenga el nodo señalado headcomo Actual.
  • Compruebe si Current no es nulo y muéstrelo.
  • Apunte la corriente a la actual nexty vaya al paso anterior.

Complejidad de tiempo: O (n) // Aquí n es el tamaño de la lista de enlaces

Implementación

Implementación de C ++ de lista enlazada individualmente

// Header files #include  struct node { int data; struct node *next; }; // Head pointer always points to first element of the linked list struct node *head = NULL;

Imprimir datos en cada nodo

// Display the list void printList() { struct node *ptr = head; // Start from the beginning while(ptr != NULL) { std::cout

Insertion at the beginning

// Insert link at the beginning void insertFirst(int data) { // Create a new node struct node *new_node = new struct node; new_node->data = data; // Point it to old head new_node->next = head; // Point head to new node head = new_node; std::cout << "Inserted successfully" << std::endl; }

Deletion at the beginning

// Delete first item void deleteFirst() { // Save reference to head struct node *temp = head; // Point head to head's next head = head->next; // Free memory used by temp temp = NULL: delete temp; std::cout << "Deleted successfully" << std::endl; }

Size

// Find no. of nodes in link list void size() { int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) { length++; } std::cout << "Size of Linked List is " << length << std::endl; }

Searching

// Find node with given data void find(int data){ // Start from the head struct node* current = head; // If list is empty if(head == NULL) { std::cout << "List is empty" next == NULL){ std::cout << "Not Found"

Deletion after a node

// Delete a node with given data void del(int data){ // Start from the first node struct node* current = head; struct node* previous = NULL; // If list is empty if(head == NULL){ std::cout << "List is empty" next == NULL){ std::cout << "Element not found" 
       
        next; } else { // Skip the current node previous->next = current->next; } // Free space used by deleted node current = NULL; delete current; std::cout << "Deleted succesfully" << std::endl; }

Python Implementation of Singly Linked List

class Node(object): # Constructor def __init__(self, data=None, next=None): self.data = data self.next = next # Function to get data def get_data(self): return self.data # Function to get next node def get_next(self): return self.next # Function to set next field def set_next(self, new_next): self.next = new_next class LinkedList(object): def __init__(self, head=None): self.head = head

Insertion

 # Function to insert data def insert(self, data): # new_node is a object of class Node new_node = Node(data) new_node.set_next(self.head) self.head = new_node print("Node with data " + str(data) + " is created succesfully")

Size

 # Function to get size def size(self): current = self.head count = 0 while current: count += 1 current = current.get_next() print("Size of link list is " + str(count))

Searching

 # Function to search a data def search(self, data): current = self.head found = False while current and found is False: if current.get_data() == data: found = True else: current = current.get_next() if current is None: print("Node with data " + str(data) + " is not present") else: print("Node with data " + str(data) + " is found")

Deletion after a node

 # Function to delete a node with data def delete(self, data): current = self.head previous = None found = False while current and found is False: if current.get_data() == data: found = True else: previous = current current = current.get_next() if current is None: print("Node with data " + str(data) + " is not in list") elif previous is None: self.head = current.get_next() print("Node with data " + str(data) + " is deleted successfully") else: previous.set_next(current.get_next()) print("Node with data " + str(data) + " is deleted successfully")

Advantages

  1. Linked lists are a dynamic data structure, which can grow and shrink, allocating and deallocating memory while the program is running.
  2. Insertion and deletion of node are easily implemented in a linked list at any position.

Disadvantages

  1. They use more memory than arrays because of the memory used by their pointers (next and prev).
  2. Random access is not possible in linked list. We have to access nodes sequentially.
  3. It’s more complex than array. If a language supports array bound check automatically, Arrays would serve you better.

Note

We have to use free() in C and delete in C++ to free the space used by deleted node, whereas, in Python and Java free space is collected automatically by garbage collector.