21 min(s) de Lectura

Estructuras de Datos: Linked Lists

Implementacion de la estructura de datos abstracta Linked List, junto con sus operaciones, implementaciones recursivas e iterativas, teniendo en cuenta las complejidades de tiempo y espacio.

Linked List ATTACH

Una linked list es una coleccion de nodos, donde cada uno de estos nodos contiene algun tipo de informacion, y un pointer hacia el siguiente nodo. La podemos definir graficamente de la siguiente manera:

Al primer nodo le llamamos head (cabeza), y al ultimo, el que no apunta a ningun otro nodose llama tail (cola).

Las linked lists son definidas en el heap.

Linked List vs Array

A diferencia de los array, la memoria en un linked list no es contigua, es decir, un elemento no esta proximo al anterior, sino que cada una esta en su propia direccion de memoria, y se mantiene la continuidad de la lista por medio de enlaces (pointers).

Definiendo la Estructura

Necesitamos definir dos estructuras: la de los nodos, y la de la lista en general.

Nodo

La estructura del nodo, va a tener dos elementos: un entero que va a ser el que almacene los datos, y un pointer al proximo nodo.

struct nodo
{
  int dato;
  struct nodo *next;
};

La estructura del nodo hace referencia a si misma para el pointer de next.

Y podemos usar esa estructura de la siguiente manera:

struct nodo *a = calloc(1, sizeof(*a));
c->dato = 10;

struct nodo *b = calloc(1, sizeof(*b));
b->dato = 20;
c->next = b;

Asi estamos creando una lista con dos nodos: a y b, y el proximo elemento de a es b.

Mostrando la Linked List ATTACH

Supongamos que tenemos la linked list:

a->dato = 8;
a->next = b;

b->dato = 10;
b->bext = c;

c->dato = 12;
c->next = d;

d->dato = 14;
d->next = e;

e->dato = 16;
e->next = NULL;

Primero, necesitamos recorrer la linked list. Una forma en que podemos hacer esto es la siguiente:

struct node *actual = a;
while (actual)
  {
    /* realizar operaciones */
    actual = actual->next;
  }

Como no sabemos exactamente cuantos nodos hay, usamos un while loop.

Ahora, para imprimir la linked list, unicamente tenemos que recorrerla e imprimir actual->dato:

void
linked_list_imprimir (struct nodo *primero)
{
  if (!primero)
    return;

  struct nodo *n = primero;
  while (n)
    {
      printf ("%d\n", n->dato);
      n = n->next;
    }
}

Mostrando una Linked List de Forma Recursiva

La manera en que podemos implementar la misma funcion de mostrar una linked list, pero de forma recursiva es la siguiente: vamos a tener una funcion que acepta un struct nodo *, y la primera instruccion que ejecuta es la de revisar que nodo != NULL, y dado el caso que esta sea cierta, se imprime el contenido nodo->dato y llamamos mostrar_recursiva(nodo->next):

void
linked_list_mostrar_recursiva (struct nodo *nodo)
{
  if (!nodo)
    return;

  printf ("%d\n", nodo->dato);
  mostrar_recursiva (nodo->next);
}

Tanto con la implementacion recursiva como con la iterativa la complejidad de tiempo de ambas es de \(O(n)\), ya que el numero de repeticiones depende del numero de elementos. Por eso, es que siempre que una operacion traverse una lista de elementos, su complejidad de tiempo va a ser \(O(n)\).

Como ya sabemos, la complejidad de espacio de las funciones recursivas cuando se traversa una lista es \(O(n)\), por lo que la complejidad de espacio de la funcion recursiva es \(O(n)\) y el tamano del estack sera \(n + 1\).

Contando los Nodos de una Linked List

Para esto vamos a necesitar traversar la linked list hasta llegar al ultimo elemento, y agregar 1 a la cantidad de nodos que hemos contado:

int
linked_list_contar (struct nodo *nodo)
{
  if (!nodo)
    return;

  int cantidad = 0;
  struct nodo *actual = nodo;
  while (actual)
    {
      cantidad++;
      actual = actual->next;
    }

  return cantidad;
}

Como por esta funcion estamos pasando por cada uno de los nodos de la linked list, decimos que la complejidad de tiempo es \(O(n)\), y la complejidad de espacio es \(O(1)\) ya que aunque tengamos 300 elementos, tendremos las mismas tres variables: cantidad, actual y nodo.

Esta funcion la podemos implementar de forma recursiva de la siguiente manera:

int
linked_list_contar_recursiva (struct nodo *nodo)
{
  if (!nodo)
    return 0;
  return linked_list_contar_recursiva (nodo->next) + 1;
}

Buscando en una Linked List

Nosotros no podemos hacer una busqueda binaria en una linked list, ya que no hay manera directa de ir a la mitad de ella, siempre tenemos que traversar desde el primer nodo, que toma \(O(n)\) de tiempo. Como no podemos llegar a la mitad de una linked list con una complejidad de tiempo constante, la busqueda binaria no queda bien con las Linked Lists.

Una funcion sencilla para buscar seria la siguiente:

struct nodo *
linked_list_buscar1 (int valor, struct nodo *nodo)
{
  if (!nodo)
    return NULL;

  struct nodo *actual = nodo;
  while (actual)
    {
      if (actual->dato == valor)
        return actual;

      actual = nodo->next;
    }

  return NULL;
}

Y la misma funcion de forma recursiva seria:

struct nodo *
linked_list_buscar_recursiva (int valor, struct nodo *nodo)
{
  if (!nodo)
    return NULL;

  if (nodo->dato == valor)
    return nodo;
  return linked_list_buscar_recursiva (valor, nodo->next);
}

Mejorando la Busqueda

Como ya lo vimos con los Arrays, podemos mejorar la busqueda para que la proxima vez que se busque se haga en menos tiempo utilizando:

Transposicion (mover un elemento a posicion - 1)
Move to head (hacerlo el primer elemento)

Para hacer el move to head necesitamos modificar 3 nodos:

El primero de la linked list.
El nodo que estaremos moviendo.
Y el nodo anterior al que estamos moviendo, ya que debe apuntar a otro nodo.

Para hacerlo, en lugar de tener un solo pointer actual sino que tambien vamos a tener uno anterior que va a apuntar al nodo anterior a actual:

struct nodo *
linked_list_buscar2 (int valor, struct nodo **nodo)
{
  if (!nodo)
    return NULL;

  struct nodo *actual = *nodo;
  struct nodo *anterior = NULL;

  while (actual)
    {
      if (actual->dato == valor)
        {
          anterior->next = actual->next;
          actual->next = *nodo;
          *nodo = actual;
        }

      anterior = actual;
      actual = actual->next;
    }

  return NULL;
}

Insertando en una Linked List

Para insertar en una linked list tenemos dos posibilidades:

Insertar antes del primer nodo (volviendolo el head.)
Insertar en una posicion indicada.

Dado el caso que fuera la primer situacion, que vamos a volver el nuevo nodo el head, tendriamos que seguir los siguientes pasos:

Se crea un nuevo nodo con el valor especificado como dato.
Este nuevo nuevo nodo->next debe ser la direccion del primer nodo.
Modificamos la direccion del primer nodo haciendola el nuevo nodo.

Como siempre van a ser los mismos tres pasos en esta situacion, decimos que la complejidad de tiempo para insertar un nodo en la primer posicion es de \(O(0)\).

Si, en cambio, quisieramos agregar un nodo en una posicion x necesitaremos:

Crear un nuevo nodo con el valor especificado como dato.
Tomamos un pointer p que se va a desplazar por posicion - 1 veces (ya que tomamos el cero como volverlo el head de la linked list.)
El nodo->next del nuevo nodo, debe apuntar al siguiente nodo de la posicion indicada.
El nodo anterior a la posicion indicada debe apuntar como next al nuevo nodo.

La complejidad de tiempo de esta situacion es \(O(n)\), con una complejidad de tiempo minima de \(O(1)\).

Implementacion

Lo anteriormente descrito puede implementarse como:

void
linked_list_insertar (int pos, int valor, struct nodo **primero)
{
  if (!primero)
    return;

  struct nodo *nuevo = NULL, *p = *primero;
  if (pos == 0)
    {
      nuevo = calloc (1, sizeof (*nuevo));
      nuevo->dato = valor;
      nuevo->next = p;
      *primero = nuevo;

      return;
    }

  for (int i = 0; i < pos - 1 && p; i++)
    p = p->next;

  if (!p)
    return;

  nuevo = calloc (1, sizeof (*nuevo));
  nuevo->dato = x;
  nuevo->next = p->next;
  p->next = nuevo;
}

Insertando en una Linked List Ordenada

Para insertar un elemento de forma ordenada en una linked list que ya esta ordenada, tomariamos un pointer p, pasamos por cada uno de los elementos para ver si p->dato < valor. Si esa condicion no se cumple, quiere decir que este nuevo nodo debe ir en el nodo anterior a p:

void
linked_list_insertar_ordenada (int valor, struct nodo **primero)
{
  struct nodo *actual = *primero, *anterior = NULL;

  struct nodo *nuevo = calloc (1, sizeof (*nuevo));
  nuevo->dato = valor;
  nuevo->next = NULL;

  if (!primero)
    {
      *primero = nuevo;
      return;
    }

  while (actual && actual->dato < x)
    {
      anterior = actual;
      actual = actual->next;
    }

  if (actual == *primero)
    {
      nuevo->next = *primero;
      *primero = nuevo;
      return;
    }

  nuevo->next = anterior->next;
  anterior->next = nuevo;
}

La complejidad de tiempo de esta funcion es: minimo \(O(1)\) y en promedio \(O(n)\).

Eliminando de una Linked List

Al momento de eliminar tenemos que tomar en cuenta dos posibles escenarios:

Cuando vamos a eliminar el primer nodo.
Cuando vamos a eliminar un nodo en una ubicacion especifica.

Cuando vamos a eliminar el primer nodo, necesitaremos mover el pointer del primer nodo, al siguiente nodo. IMPORTANTE: al hacer esto aunque el nodo queda inutilizable porque ya no podra ser accedido en la linked list, sigue existiendo en el heap, por lo que es muy importante liberar ese espacio en memoria.

Para eliminar el primer nodo necesitaremos otro pointer p que apunta al primer nodo, haremos que el primer nodo apunte a primero->next y liberamos p. La complejidad de tiempo de este caso es de \(O(1)\).

Para eliminar de una posicion, unicamente tenemos que traversar la linked list hasta esa posicion, hacemos que (posicion - 1)->next = posicion->next y liberamos la memoria del nodo en posicion. La complejidad de tiempo de este caso es de minimo \(O(1)\) y maximo \(O(n)\).

Implementacion

int
linked_list_eliminar (int pos, struct nodo **primero)
{
  if (!primero)
    return -1;

  struct nodo *actual = *primero, *anterior = NULL;
  int x = 0;
  if (pos == 1)
    {
      x = *primero->dato;
      actual = *primero;
      *primero = *primero->next;
      free (actual);

      return x;
    }

  for (int i = 0; i < pos - 1 && actual; i++)
    {
      anterior = actual;
      actual = actual->next;
    }

  if (!actual)
    return -1;

  anterior->next = actual->next;
  x = actual->dato;
  free (actual);

  return x;
}

Checar si una Linked List esta Ordenada

Para revisar si una linked list esta ordenada o no (en orden ascendiente, el menor primero) vamos a necesitar dos pointers: uno para el nodo actual, y otro para el nodo anterior. Utilizando estos dos pointers, por cada nodo vamos a revisar si actual->dato > ~anterior->dato si esa condicion se cumple hasta llegar al final de lista, significa que la lista esta ordenada.

_Bool
linked_list_esta_ordenada (struct nodo *primero)
{
  if (!primero || !primmero->next)
    return 0;

  struct nodo *anterior = primero;
  struct nodo *actual = primero->next;
  while (actual)
    {
      if (actual->dato < anterior->dato)
        return 0;

      anterior = actual;
      actual = actual->next;
    }

  return 1;
}

La complejidad de tiempo minima es \(O(1)\) y la complejidad de tiempo maxima es \(O(n)\).

Remover Duplicados de una Linked List Ordenada

Para remover duplicados de una Linked List ordenada, vamos a necesitar dos pointers actual y anterior y vamos a estar revisando si si el dato de ambos nodos es igual. Dado el caso que lo sea vamos a poner el next de anterior a actual->next, vamos a hacerle free a actual y hacer actual = anterior->next:

void
linked_list_remover_duplicados (struct nodo *primero)
{
  if (!primero)
    return;

  struct nodo *actual = primero;
  struct nodo *anterior = NULL;

  while (actual)
    {
      if (actual->dato == anterior->Dato)
        {
          anterior->next = actual->next;
          free (actual);
          actual = anterior->next;
          continue;
        }

      anterior = actual;
      actual = actual->next;
    }
}

Invirtiendo Linked List

Para invertir una linked list podemos hacerlo de dos maneras:

Invirtiendo los elementos.
Invirtiendo los enlaces.

Invirtiendo los Elementos

Invertir los elementos, es hacer que ultimo->dato = primero->dato y asi suscesivamente, estaremos cambiando el valor de dato.

Una de las maneras en que podemos implementar esta manera, es creando un array de la misma longitud que elementos en la linked list, e iterar la lista e ir agregando nodo->dato a este array. Al lllegar al final de la lista, iteramos de nuevo desde el inicio, y le asignaremos el valor a los nodos de forma decresciente como valores en el array:

void
linked_list_invertir1 (struct nodo *primero)
{
  if (!primero)
    return;

  int *array = calloc(array_list_contar (primero), sizeof (int));
  if (!array)
    return;

  struct nodo *actual = primero;
  int i = 0;
  while (actual)
    {
      array[i++] = actual->dato;
      actual = actual->next;
    }

  actual = primero;
  i--;

  while (actual)
    {
      actual->dato = array[i--];
      actual = actual->next;
    }
}

La complejidad de tiempo es \(O(n)\).

Invirtiendo los Enlaces ATTACH

Al invertir los enlaces, no se estaria cambiando el valor de dato sino que la direccion del ultimo nodo seria la del primero, la del penultimo la del segundo, y asi suscesivamente.

Para revertir los enlaces de una llinked list vamos a necesitar 3 pointers: p, q y r. Vamos a revertir la linked list cambiando 3 nodos a la vez, y estos se van a estar siguiendo, uno despues del otro:

Haciendolo de esa manera.

Despues, vamos a hacer que el nodo q->next = r.

En el primer paso q->next va a ser puesto como NULL:

Quedando asi en el segundo paso:

Y asi suscesivamente:

void
linked_list_invertir2 (struct nodo **primero)
{
  if (!primero)
    return;

  struct nodo *p = *primero;
  struct nodo *q = NULL;
  struct nodo *r = NULL;

  while (p)
    {
      r = q;
      q = p;
      p = p->next;

      q->next = r;
    }

  *primero = q;
}

Siguiendo esos pasos la linked list queda invertida:

Generalmente se prefiere invertir los enlaces antes que el contenido de los nodos, porque no sabemos cual sera el contenido de estos, aunque en estos ejemplos sean enteros, pueden ser estructuras enteras, o clases en C++.

Invirtiendo de Forma Recursiva

Para implementar esta funcion de forma recursiva, vamos a necesitar dos pointers: p y q, y q va a ser el anterior a p para asi poder hacer la inversion (que se hara en return time).

void
linked_list_invertir_recursiva(struct nodo *q, struct nodo **p)
{
  if (*p)
    {
      linked_list_invertir_recursiva (*p, &(*p)->next);
      (*p)->next = q;
    }
  else
    {
      *p = q;
    }
}

Concatenando 2 Linked Lists

Concatenar 2 linked lists significa unirlas. Para hacerlo, unicamente tenemos que traversar la linked list hasta el final, y el ultimo nodo next va a apuntar al primer nodo de la segunda linked list:

void
linked_list_concatenar (struct nodo *a, struct nodo *b)
{
  if (!a || !b)
    return;

  struct nodo *p = a;
  while (p)
    p = p->next;
  p->next = b;
}

La complejidad de tiempo es \(O(n)\).

Uniendo 2 Linked Lists

Ahora, vamos a unir 2 linked lists ordenadas para que hagan una sola linked list ordenada.

Para hacer esto vamos a usar 2 pointers, y vamos a estar comparando cada uno de los nodos para ver cual es el mayor, y vamos a estar cambiando los next con la ayuda de estos dos pointers:

struct nodo *
linked_list_unir_ordenada (struct nodo *a, struct nodo *b)
{
  if (!a || !b)
    return NULL;

  /* paso 1: inicializar los pointers */
  struct nodo *ultimo = NULL;
  struct nodo *lista = NULL;

  /* hacer la primer comparacion */
  if (a->dato > b->dato)
    {
      lista = ultimo = a;
      a = a->next;
      ultimo->next = NULL;
    }
  else
    {
      lista = ultimo = b;
      b = b->next;
      ultimo->next = NULL;
    }

  /* comparar cada uno de los elementos */
  while (a && b)
    {
      if (a->dato < b->dato)
        {
          ultimo->next = a;
          ultimo = a;
          a = a->next;
          ultimo->next = NULL;
        }
      else
        {
          ultimo->next = b;
          ultimo = b;
          b = b->next;
          ultimo->next = NULL;
        }
    }

  /* si quedan elementos en una de las linked lists, agregarlos al ultimo
   * nodo */
  if (a)
    ultimo->next = a;
  else if (b)
    ultimo->next = b;

  return lista;
}

Revisar si una Linked List tiene Bucles

Un bucle en una linked list, es cuando el ultimo elemento next apunta a otro elemento dentro de la linked list (no tiene que ser el primero), haciendo que esta no sea linear.

Para revisar si una linked list tiene un bucle, podemos utilizar dos pointers p y q. Vamos a travesar la linked list y p se va a mover un nodo a la vez, y q se va a mover dos nodos a la vez, dado el caso que llegase a haber un bucle, en algun punto estos dos pointers van a ser el mismo nodo:

_Bool
linked_list_bucle (struct nodo *n)
{
  if (!n)
    return 0;

  struct nodo *p, *q;
  p = q = n;

  do {
    p = p->next;
    q = q->next;
    q = q ? q->next : NULL;
  } while (p && q && p != q);

  if (p == q)
    return 1;
  return 0;
}

Linked List Circular ATTACH

Una linked list circular es cuando el ultimo elemento de la linked list, apunta al primer elemento de la lista.

En estas listas no llamamos ningun elemento primero o ultimo, sino que usamos los terminos head y tail

Si en una linked list circular hay un solo elemento, este debe apuntar a si mismo.

Podemos tener dos representaciones de una linked list circular:

Imprimiendo una Linked List Circular

Para imprimir una linked list circular vamos a traversar todos los elementos, tal como hicimos con la linked list linear, solo que ahora la condicion para salir del bucle es revisar que p no sea igual a head:

void
linked_list_circular_imprimir (struct nodo *n)
{
  if (!n)
    return;

  struct nodo *p = n;
  do {
    printf ("%d\n", p->dato);
    p = p->next;
  } while (p != n);
}

Para implementar esta misma funcion de forma recursiva vamos a necesitar una variable que llamaremos flag y la utilizaremos en la condicion recursiva.

void
linked_list_circular_imprimir_recursiva (struct nodo *n, struct nodo *head)
{
  static int flag = 0;
  if (n != head || flag == 0)
    {
      flag = 1;
      printf ("%d\n", n->dato);
      linked_list_circular_imprimir_recursiva (n->next, head);
    }
  flag = 0;
}

Esta nos va a servir para poder hacer llamada recursiva la primera vez que p = head, pero evitar que se repita la segunda vez que esta condicion se cumple.

Creando una Linked List Circular a partir de un Array

Para crear una linked list circular a partir de un array podemos hacer una funcion similar a la siguiente:

struct nodo *
linked_list_circular_crear (int *a, int n)
{
  if (!a)
    return NULL;

  struct nodo *head = NULL, *t = NULL, *last = NULL;
  head = calloc (1, sizeof (*head));
  head->data = a[0];
  head->next = head;
  last = head;

  for (int i = 1; i < n; i++)
    {
      t = calloc (1, sizeof (*t));
      t->data = a[i];
      t->next = last->next;
      last->next = t;
      last = t;
    }
}

Asi, el primer nodo que agreguemos despues de crear head su next va a estar apuntando a head y gracias a last todos los nodos que se vayan agregando tambien van a tener el next de head si son el ultimo nodo.

Insertando en una Linked List Circular

Para insertar en una linked list circular, tendremos en cuenta dos situaciones:

Insertar antes de head.
Insertar en una posicion dada.

Insertar antes de head: para insertar un nodo antes de head, necesitaremos crear un nuevo nodo, poner su next que sea head y traversar la lista hasta llegar al ultimo nodo (sabremos que hemos llegado cuando nodo->next = head) y hacer que el next del ultimo nodo sea el nuevo nodo que hemos creado.

Insertar en una posicion dada: para insertar en una posicion n (empezando a contar desde 1, ya que la posicion 0 sera para hacerlo el head) lo que haremos sera iterar n-1 veces en la linked list para obtener un pointer al nodo anterior, y hacer que el nuevo nodo next sea nodo_anterior->next y que el next del nodo anterior sea el nuevo nodo.

Esta situacion toma \(O(1)\) complejidad de tiempo minima, y \(O(n)\) complejidad de tiempo maxima.

struct nodo *
linked_list_circular_insertar (int dato, int pos, struct nodo *l)
{
  if (!l || pos < 0)
    return NULL;

  struct nodo *n = calloc (1, sizeof (*n));
  n->dato = dato;

  if (pos == 0)
    {
      n->next = l;

      struct nodo *p = l;
      while (p->next != l)
        p = p->next;

      p->next = t;
      /* opcional: cambiar head, aunque no es necesario */

      return n;
    }

  struct nodo *p = l;
  for (i = 0; i < pos - 1 && p; i++)
    p = p->next;

  n->next = p->next;
  p->next = n;

  return n;
}

Eliminando un Nodo de una Linked List Circular

Para eliminar un nodo de una linked list circular debemos tomar en cuenta dos situaciones:

Si vamos a eliminar el head.
Si vamos a eliminar un nodo de una posicion dada.

Eliminar head: para eliminar head vamos a necesitar un pointer p que apunte al ultimo elemento de la lista, vamos a hacer que su next sea head->next, y eliminamos head.

Eliminar un nodo en una posicion dada: para eliminar un nodo de una posicion x vamos a necesitar dos pointers: uno que apunte al nodo posicion - 2 y otro que apunte al nodo posicion - 1, los vamos a llamar p y q respectivamente. Una vez tengamos estos dos pointers, vamos a asignar p->next = q->next y ahora si podemos eliminar el nodo q.

int
linked_list_circular_eliminar (int pos, struct nodo **head)
{
  if (!head || pos < 0)
    return -1;

  if (pos == 1)
    {
      struct nodo *p = *head;
      while (p->next != *head)
        p = p->next;

      int x = *(head)->data;
      if (p == *head)
        {
          free (*(head));
          *head = NULL;

          return x;
        }

      p->next = *(head)->next;
      free (*(head));
      *head = p->next;

      return x;
    }

  struct nodo *p = *head;
  for (int i = 0; i < pos - 2 && p; i++)
    p = p->next;

  struct nodo *q = p->next;
  p->next = q->next;
  int x = q->data;
  free (q);

  return x;
}

Linked List Doble

Una Linked List Simple los nodos van a tener un pointer al siguiente nodo, en una linked list doble tambien van a tener un pointer al nodo anterior:

struct nodo_doble
{
  int dato;
  struct nodo_doble *prev;
  struct nodo_doble *next;
};

Podemos definir una funcion para crear una linked list doble a partir de un array de la siguiente manera:

struct nodo_doble *
linked_list_doble_crear (int *a, int n)
{
  if (!a)
    return NULL;

  struct nodo_doble *lista = NULL;
  struct nodo_doble *t = NULL, *ultimo = NULL;

  lista = calloc (1, sizeof (*lista));
  lista->dato = a[0];
  lista->prev=lista->next=NULL;
  ultimo = lista;

  for (int i = 1; i < n; i++)
    {
      t = calloc (1, sizeof (*t));
      t->dato = a[i];
      t->next = ultimo->next;
      t->prev = ultimo;
      ultimo->next = t;
      ultimo = t;
    }
}

Y para mostrar una linked list, lo haremos de la misma forma en que lo hicimos con una linked list simple:

void
linked_list_doble_imprimir (struct nodo_doble *n)
{
  if (!n)
    return;

  while (n)
    {
      printf ("%d\n", n->dato);
      n = n->next;
    }
}

De igual forma, para obtener la longitud seria exactamente lo mismo:

int
linked_list_doble_longitud (struct nodo_doble *n)
{
  if (!n)
    return -1;

  int l = 0;

  while (n)
    {
      l++;
      n = n->next;
    }

  return l;
}

Insertando en una Linked List Doble

Para insertar un elemento en una linked list doble tenemos dos escenarios:

Vamos a insertar antes del primer nodo.
Vamos a insertar en una posicion dada.

Antes del primer nodo: Para insertar un nuevo nodo antes del primer nodo, necesitaremos crear un nuevo nodo, modificar el prev del primer nodo, y el next del nodo creado. La complejidad de tiempo de este escenario es \(O(1)\).

En una posicion dada: Para insertar un nuevo nodo en una posicion dada, necesitaremos crear un nuevo nodo, traversar la linked list hasta pos - 1, y poner modificar los enlaces para que el prev del nuevo nodo sea pos - 1 el next sea p->next y modificar el prev de p->next para que sea el nuevo nodo.

struct nodo_doble *
linked_list_doble_insertar (int dato, int pos, struct nodo_doble **l)
{
  if (!l || pos < 0)
    return NULL;

  struct nodo_doble *t = calloc (1, sizeof (*t));
  t->dato = dato;

  struct nodo_doble *p = *l;

  if (pos == 0)
    {
      p->prev = t;
      t->next = p;
      *l = t;

      return t;
    }

  for (int i = 1; i < pos - 1 && p; i++)
    p = p->next;

  t->next = p->next;
  t->prev = p;
  if (p->next)
    p->next->prev = t;
  p->next = t;

  return t;
}

Eliminando un Nodo en una Linked List Doble

Como cuando eliminamos de una llinked list simple, hay dos situaciones que debemos manejar:

Eliminar el primer nodo.
Eliminar de un indice dado.

Eliminar el primer nodo: Lo primero que debemos hacer es obtener un pointer del primer elemento de la lista p, mover el pointer del primer elemento a p->next y dado el caso de que p->next != NULL, pondremos head->prev = NULL, obtendremos el valor de p y liberamos la memoria.

Eliminar en una posicion dada: para eliminar un nodo en un indice dado, traversaremos la lista hasta llegar a pos y modificamos los nodos prev y next (si existe.)

int
linked_list_doble_eliminar (int pos, struct nodo_doble **head)
{
  if (!head || pos < 0)
    return -1;

  struct nodo_doble *p = *head;
  if (pos == 1)
    {
      *head = *head->next;
      int x = p->data;
      free (p);

      if (*head)
        *(head)->prev = NULL;

      return x;
    }

  for (int i = 0; i < pos - 1 && p; i++)
    p = p->next;

  p->prev->next = p->next;
  if (p->next)
    p->next->prev = p->prev;

  int x = p->data;
  free (p);

  return x;
}

Invertir una Linked List Doble

Para invertir una linked list, vamos a estar intercambiando los pointers prev y next de los nodos, y cambiar el valor de head:

void
linked_list_doble_invertir (struct nodo_doble **head)
{
  if (!head)
    return;

  struct nodo_doble *p = *head;
  struct nodo_doble *temp = NULL;
  while (p)
    {
      temp = p->next;
      p->next = p->prev;
      p->prev = temp;
      p = p->prev;

      if (!p->next)
        *(head) = p;
    }
}

Linked List Ciircular Doble

Las operaciones con una linked list circular doble es la misma que las de una linked list circular simple, unicamente tendremos que tener en cuenta los enlaces prev.

Para obtener el ultimo nodo de una linked list circular doble, solo debemos hacer head->prev.