Listas enlazadas#

Objetivos

Objetivo 1…
Objetivo 2…

1. Introduccion#

Una lista enlazada (Linked list) es una estructura de datos dinamica que consiste en una secuencia de registros donde cada elemento contiene un link al proximo registro de la secuencia. Las listas enlazadas pueden ser Listas simplemente enlazadas, Listas doblemente enlazadas o listas circulares. En este caso solo nos limitaremos a las listas simplemente enlazadas.

2. Lista enlazada simple#

Como se dijo previamente, una lista enlazada es una secuencia de datos conectadas a traves de links. A continuación vamos a describir las principales estructuras asociadas a la lista enlazada y las funciones involucradas en este.

../_images/CH_02-S07-LL_fig4.png — Fig. 89 Lista enlazada simple#

Simulaciones

La pagina Data Structure Visualizations (link) recopila una gran cantidad de animaciones sobre estructuras de datos.

2.1. Estructuras asociadas a una lista enlazada simple#

2.1.1. Nodo (`node`)#

Un nodo (node) es la estructura fundamental que compone a una lista. La siguiente figura muestra la representación de un nodo:

../_images/CH_02-S07-LL_fig1.png — Fig. 90 Estructura de un nodo (`node`)#

A continuación, se muestra la definición de esta estructura de datos en C:

typedef struct _node {
    int item;
    struct _node* next;
}node;

Como se puede observar, en el fragmento de código anterior hay dos miembros:

item: Miembro del nodo en el que se almacena el contenido (payload) del nodo. En este caso, el contenido es un dato tipo int pero en general, el item puede ser cualquier tipo de dato generico.
next: Este es el link que apunta al proximo nodo de la lista. Al ser este un apuntador, lo que se almacena es la dirección del proximo nodo.

En la siguiente figura se muestra la lista enlazada de la primera figura, observe que en la parte asociada al link lo que se almacena es la dirección del próximo nodo de la lista.

../_images/CH_02-S07-LL_fig5.png — Fig. 91 Lista enlazada simple#

Como se puede ver en la figura anterior; el primer nodo de la lista es referenciado mediante una variable externa conocido como head, mientras el fin de la lista es indicado mediante un NULL (sentinela), al cual apunta el link del ultimo nodo de la lista.

Note

El head es un apuntador a un dato tipo node cuyo proposito es indicar el inicio de la lista y por ende, no hace propiamente parte del contenido de la lista.

2.1.2. Lista#

Como se menciono previamente, el heap es una referencia externa externa que permite indicar el inicio de la lista y por ende, no hace propiamente parte del contenido de esta. La siguiente figura muestra este caso:

../_images/CH_02-S07-LL_fig5a.png — Fig. 92 Referencia `head`#

Sin embargo, podemos usar un envoltorio (wraper) con el fin de asociar la referencia heap como miembro de un nuevo tipo de dato list que define la lista enlazada.

../_images/CH_02-S07-LL_fig2.png — Fig. 93 Estructura tipo `list`#

Para hacer esto definimos mediante la estructura list con la referncia heap como su miembro tal y como se muestra en el siguiente código:

typedef struct _list {
    node *head;
} list;

Luego, usando esta estructura de datos, podemos definir las funciones necesarias para su manipulación.

2.2. Funciones de la lists#

Las operaciones basicas asociadas sobre una lista enlazada se muestran a continuacion:

Operación	Descripción
`list* List_new(void)`	Crea e inicializa una nueva lista
`void List_init(list *L)`	Iniclizaliza una lista vacia haciendo que el apuntador `head` se inicialice en `NULL`
`int List_empty(list *L)`	Determina si la lista esta vacia
`int List_length(list *L)`	Obtiene la longitud de la lista
`node* List_lookup(list *L, int item)`	Obtiene un puntero al nodo de la lista cuyo valor es `item`
`void List_insert_at_begin(list *L, int item)`	Inserta un nodo cuyo valor es `item` al principio de la lista
`void List_insert_at_end(list *L, int item)`	Inserta un nodo cuyo valor es `item` al final de la lista
`int List_delete_at_begin(list *L)`	Elimina el nodo que se encuentra al principio de la lista
`int List_delete_at_end(list *L)`	Elimina el nodo que se encuentra al final de la lista
`int List_delete_item(list *L, int item)`	Elimina el nodo cuyo valor es `item`
`node* List_search(list *L, int item)`	Elimina el nodo que se encuentra al final de la lista
`void List_print(list *L, int opt)`	Imprime el contenido de la lista enlazada
`void List_clean(list *L)`	Vacia una lista enlazada

A continuación se muestra la implementación en C de cada una de las funciones anteriormente descritas.

List_new: En esta función permite crear nueva lista en el heap, inicializando su miembro head y retornando un apuntador a esta.

list* List_new(void) {
  list *L = malloc(sizeof(L));
  assert(L != NULL);
  L->head = NULL;
  return L;
}

List_init: Inicializa el nodo head de una lista.

void List_init(list *L) {
  L->head = NULL;
}

List_empty: Determina si una lista L esta vacia retornando 1 si en efecto lo esta o 0 en caso contrario.
```
int List_empty(list *L) {
  assert(L != NULL);
  return (L->head == NULL);
}
```

List_length: Determina la longitud (numero de nodos que tiene la lista) de una lista L.

int List_length(list *L) {
  node *current = L->head;
  int count = 0;
  while (current != NULL) {
    count++;
    current = current->next;
  }
  return count;
}

List_insert_at_begin: Inserta un nodo cuyo valor es item al principio de la lista.

void List_insert_at_begin(list *L, int item) {
  node *new = malloc(sizeof(node));
  assert(new != NULL);
  assert(L != NULL);
  new->item = item;
  if (L->head != NULL) {
    // El resto de los elementos
    new->next = L->head;
    L->head = new;
  }
  else {
    // Primer elemento
    new->next = NULL;
    L->head = new;
  }
}

List_insert_at_end: Inserta un nodo con valor item al final de la lista.

void List_insert_at_end(list *L, int item) {
  node *new = malloc(sizeof(node));
  assert(new != NULL);
  assert(L != NULL);
  new->item = item;
  if (L->head == NULL) {
    new->next = L->head;
    L->head = new;
  }
  else {
    node *current = L->head;
    while (current->next != NULL) {
      current = current->next;
    }
    new->next = NULL;
    current->next = new;
  }    
}

List_delete_at_begin: Elimina el primer nodo de la lista devolviendo 0 si la operación es correcta o -1 en caso contrario

int List_delete_at_begin(list *L) {    
  if (L->head == NULL) {
    printf("ERROR: Empty List\n");
    return -1;
  }
  else {
    node *current = L->head;
    L->head = current->next;
    free(current);
    return 0;
  }
}

List_delete_at_end: Elimina el ultimo nodo de la lista devolviendo 0 si la operación es correcta o -1 en caso contrario

int List_delete_at_end(list *L) {
  if (L->head == NULL) {
    printf("ERROR: Empty List\n");
    return -1;
  }
  else if(L->head->next == NULL) {
    free(L->head);
    L->head = NULL;
  }
  else {
    node *current = L->head;
    node *prev;
    while(current->next != NULL) {            
      prev = current;
      current = current->next;
    } 
    prev->next = NULL;
    free(current);       
    return 0;
  }
}

List_seach: Devuelve un puntero al nodo de la lista L cuyo valor es item. En caso de que el valor no se encuentre en la lista el valor devuelto es NULL.

node* List_search(list *L, int item) {
  node *current = L->head;
  while (current) {
    if (current->item == item) {
      return current; // success
    }
    current = current->next;
  }
  return NULL; // failure
}

List_delete_item: Elimina el nodo de la lista cuyo valor es item. El valor retornado es 0 si la operacion es correcta o -1 si hay fallas.

int List_delete_item(list *L, int item) {
  assert(L != NULL);
  if (L->head == NULL) {
    printf("ERROR: Empty List\n");
    return -1;
  }
  node *current = L->head;
  node *prev;
  while(current->next != NULL) {
    if(current->item == item) {
      if(current == L->head) {
        // First node
        L->head = current->next;
        free(current);                
      }
      else {
        prev->next = current->next;
        free(current);
      }
      return 0;
    }            
    prev = current;
    current = current->next;
  }
  if(current->item == item) {
    // Last node
    prev->next = NULL;
    free(current);
    return 0;        
  }
  printf("ERROR: Value not found\n");
  return -1;
}

List_print: Imprime el contenido de la lista enlazada dependiendo de la opción (opt) elegida:

Impresión de la lista mostrando solo datos: Si opc = 1 se imprimen los datos de cada uno de los nodos de la lista enlazada.
Impresión mostrando direcciones y datos: Si opc = 2 se imprimen componentes (dato y apuntador al siguiente nodo) de cada uno de los nodos de la lista enlazada.

void List_print(list *L, int opt) {
  node *current = L->head;
  if (current == NULL) {
      printf("Empty list.\n");
  } 
  else {
      switch (opt)
      {
      case 1:
          while (current) {
              printf("[%d] --> ", current->item);
              current = current->next;
          } 
          printf("[X]\n");
          break;
      case 2:
          for(; current->next != NULL; current = current->next) {
              printf("[%d|%p] --> ", current->item, current->next);
          }
          printf("[%d|%p]\n", current->item, current->next);
          break;
      default:
          printf("Invalid option.\n");            
      }
  } 
}

3. Uso de la estructura `list`#

El siguiente código muestra el esqueleto de un programa en el cual se va a hacer uso de Listas enlazadas:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/*
Definicion de las estructuras de datos
*/

// Estructura nodo (node)
typedef struct _node {
  int item;
  struct _node* next;
}node;

// Estructura lista (list)
typedef struct _list {
  node *head;
} list;

/*
Declaración de las funciones asociadas a la pila
*/
list* List_new(void);
void List_init(list *);
int List_empty(list *);
void List_insert_at_begin(list *, int);
void List_insert_at_end(list *, int);
void List_print(list *, int);
int List_length(list *);
int List_delete_at_begin(list *);
int List_delete_at_end(list *);
node* List_lookup(list *, int);
int List_delete_item(list *L, int item);
void List_clean(list *L);

/*
Funcion principal
*/
int main() {
  // Codigo de la aplicacion
  ...  
  return 0;
}

/*
Definicion de las funciones asociadas a la lista enlazada
*/
list* List_new(void) {
  list *L = malloc(sizeof(L));
  assert(L != NULL);
  L->head = NULL;
  return L;
}

void List_init(list *L) {
    L->head = NULL;
}

int List_empty(list *L) {
  assert(L != NULL);
  return (L->head == NULL);
}

void List_insert_at_begin(list *L, int item) {
  node *new = malloc(sizeof(node));
  assert(new != NULL);
  assert(L != NULL);
  new->item = item;
  if (L->head != NULL) {
    // El resto de los elementos
    new->next = L->head;
    L->head = new;
  }
  else {
    // Primer elemento
    new->next = NULL;
    L->head = new;
  }
}

void List_insert_at_end(list *L, int item) {
  node *new = malloc(sizeof(node));
  assert(new != NULL);
  assert(L != NULL);
  new->item = item;
  if (L->head == NULL) {
    new->next = L->head;
    L->head = new;
  }
  else {
    node *current = L->head;
    while (current->next != NULL) {
      current = current->next;
    }
    new->next = NULL;
    current->next = new;
  }    
}

int List_length(list *L) {
  node *current = L->head;
  int count = 0;
  while (current != NULL) {
    count++;
    current = current->next;
  }
  return count;
}


void List_print(list *L, int opt) {
  node *current = L->head;
  if (current == NULL) {
    printf("Empty list.\n");
  } 
  else {
    switch (opt)  {
      case 1:
        while (current) {
          printf("[%d] -> ", current->item);
          current = current->next;
        } 
        printf("[X]\n");
        break;
      case 2:
        for (; current->next != NULL; current = current->next) {
          printf("[%d|%p] -> ", current->item, current->next);
        }
        printf("[%d|%p]\n", current->item, current->next);
        break;
      default:
        printf("Invalid option.\n");            
      }
    } 
}

int List_delete_at_begin(list *L) {    
  if (L->head == NULL) {
    printf("ERROR: Empty List\n");
    return -1;
  }
  else {
    node *current = L->head;
    L->head = current->next;
    free(current);
    return 0;
  }
}

int List_delete_at_end(list *L) {
  if (L->head == NULL) {
    printf("ERROR: Empty List\n");
    return -1;
  }
  else if(L->head->next == NULL) {
    free(L->head);
    L->head = NULL;
  }
  else {
    node *current = L->head;
    node *prev;
    while(current->next != NULL) {            
      prev = current;
      current = current->next;
    } 
    prev->next = NULL;
    free(current);       
    return 0;
  }
}

node* List_lookup(list *L, int item) {
  assert(L != NULL);
  node *current = L->head;
  while (current) {
    if (current->item == item) {
      return current; // success
    }
    current = current->next;
  }
  return NULL; // failure
}

int List_delete_item(list *L, int item) {
  assert(L != NULL);
  if (L->head == NULL) {
    printf("ERROR: Empty List\n");
    return -1;
  }
  node *current = L->head;
  node *prev;
  while(current->next != NULL) {
    if(current->item == item) {
      if(current == L->head) {
        // First node
        L->head = current->next;
        free(current);                
      }
      else {
        prev->next = current->next;
        free(current);
      }
      return 0;
    }            
    prev = current;
    current = current->next;
  }
  if(current->item == item) {
    // Last node
    prev->next = NULL;
    free(current);
    return 0;        
  }
  printf("ERROR: Value not found\n");
  return -1;
}

void List_clean(list *L) {
  int len = List_length(L);
  for(int i = 0; i < len; i++) {
    List_delete_at_begin(L);
  }
}

3.1. Ejemplos#

Codigo 1: Mediante código implemente la siguiente lista enlazada:

Fig. 94 Lista enlazada asociada al ejemplo.#

El siguiente fragmento de código (simulacion) hace uso de las funciones definidas anteriormente para:
- Crear una nueva lista enlazada en el heap (L) mediante la función List_new.
- Agregar los nodos de la lista (45, 65, 34 y 36) respectivamente. Esto se hace usando las funciones List_insert_at_begin y List_insert_at_end.
- Imprimir la lista enlazada de las dos formas (Normal y detallada).
```
...
int main() {
  list *L = List_new();
  List_insert_at_begin(L, 65);
  List_insert_at_begin(L, 45);
  List_insert_at_end(L, 34);
  List_insert_at_end(L, 36);
  List_print(L,1);
  List_print(L,2);
  return 0;
}
...
```
El resultado del código anterior, se muestra a continuación:

Fig. 95 Lista enlazada resultante.#

El resultado en pantalla se muestra en la siguiente figura:

El resultado del código anterior, se muestra a continuación:

Fig. 96 Resultado en pantalla.#
Codigo 2: El codigo que se muestra a continuación hace lo mismo que el código anterior (codigo 1), pero a diferencia de este ultimo, inicializa la lista, definiendo previamente una variable local (L) tipo list en el stack:

Fig. 97 Lista enlazada del ejemplo.#

La implementación realizada en el siguiente fragmento de código (simulación) hace lo siguiente:
- Crear una nueva lista enlazada L (variable local) en el stack.
- Mediante la función List_init inicializa la lista L.
- Agregar los nodos de la lista (45, 65, 34 y 36) respectivamente. Esto se hace usando las funciones List_insert_at_begin y List_insert_at_end.
- Imprimir la lista enlazada de las dos formas (Normal y detallada).
```
int main() {
  list L; 
  List_init(&L);
  List_insert_at_begin(&L, 65);
  List_insert_at_begin(&L, 45);
  List_insert_at_end(&L, 34);
  List_insert_at_end(&L, 36);
  List_print(&L,1);
  List_print(&L,2);
  return 0;
}
```
La lista resultante al ejecutar el elemento anterior se muestra a continuación, notese que en este caso, a diferencia del código 1, la lista se encuentra en el stack y no en el heap:

Fig. 98 Lista resultante.#

Finalmente, la salida en pantalla se muestra a continuación:

Fig. 99 Salida en pantalla resultante.#

Código 3: El siguiente crea una lista enlazada con los elementos 1, 2 y 3 y realiza las siguientes tareas:

Imprime la lista de las dos formas.
Imprime la longitud de la lista.
Busca un elemento que se encuentra e imprime su valor.
Busca un elemento que no se encuentra y muestra un mensaje que indica esto.

A continuación, se muestra el fragmento de código de la función main asociado al ejemplo:

int main() {
  list *L = (list *)malloc(sizeof(list)); 
  List_init(L);
  List_insert_at_end(L, 1);
  List_insert_at_end(L, 2);
  List_insert_at_end(L, 3);
  List_insert_at_end(L, 4);
  List_insert_at_end(L, 5);
  printf("Lista inicial: ");
  List_print(L,1);
  List_delete_at_begin(L);
  printf("Lista al borrar el primer elemento (1): ");
  List_print(L,1);
  List_delete_at_end(L);
  printf("Lista al borrar ultimo elemento elemento (5): ");
  List_print(L,1);
  printf("Lista al borrar el elemento de la mitad (3): ");
  List_delete_item(L, 3);
  List_print(L,1);
  List_clean(L);
  printf("Lista al ser limpiada: ");
  List_print(L,1);
  free(L);
  return 0;
}

La salida del código anterior se muestra a continuación:

Lista inicial:
[1] -> [2] -> [3] -> [X]
[1|0x7fffc5cf52c0] -> [2|0x7fffc5cf52a0] -> [3|(nil)]

Tamaño de la lista: 3
Nodo con valor 3 encontrado
Nodo con valor 5 no encontrado

Codigo 4: A partir de la lista enlazada cuyos elementos son: 1, 2, 3, 4 y 5 pruebe las funciones para eliminar datos en el siguiente orden:

Eliminar el primer elemento (1).
Eliminar el último elemento (5).
Eliminar el elemento de la mitad de la lista (3).
Eliminar los elementos restantes (2 y 4) limpiando la lista.

El código se encuentra a continuación:

...
int main() {
  list *L = (list *)malloc(sizeof(list)); 
  List_init(L);
  List_insert_at_end(L, 1);
  List_insert_at_end(L, 2);
  List_insert_at_end(L, 3);
  List_insert_at_end(L, 4);
  List_insert_at_end(L, 5);
  printf("Lista inicial: ");
  List_print(L,1);
  List_delete_at_begin(L);
  printf("Lista al borrar el primer elemento (1): ");
  List_print(L,1);
  List_delete_at_end(L);
  printf("Lista al borrar ultimo elemento elemento (5): ");
  List_print(L,1);
  printf("Lista al borrar el elemento de la mitad (3): ");
  List_delete_item(L, 3);
  List_print(L,1);
  List_clean(L);
  printf("Lista al ser limpiada: ");
  List_print(L,1);
  free(L);
  return 0;
}
...

La salida del código anterior se muestra a continuación:

Lista inicial: [1] -> [2] -> [3] -> [4] -> [5] -> [X]
Lista al borrar el primer elemento (1): [2] -> [3] -> [4] -> [5] -> [X]
Lista al borrar ultimo elemento elemento (5): [2] -> [3] -> [4] -> [X]
Lista al borrar el elemento de la mitad (3): [2] -> [4] -> [X]
Lista al ser limpiada: Empty list.

4. Construcción de una pila (`stack`) a partir de una lista enlazada#

Como se vió previamente (link), una de los problemas de crear pilas mediante el uso de arrays radica en el hecho de que el manejo de memoria no es tan eficiente. Una alternativa mas eficiente, consiste en crear una pila a partir de una lista enlazada mediante la cual, el manejo de memoria se hace bajo demanda (mediante la reserva y liberación en tiempo de ejecución) de manera mas eficiente. La siguiente figura muestra la implementación de una pila con elementos 1, 2 y 3 (analizada previamente (link)) mediante listas enlazadas:

../_images/CH_02-S07-LL_fig8.png — Fig. 100 Implementación de una pila mediante listas enlazadar#

Note

Para facilitar la comprensión de la implementación de una lista enlazada mediante pilas se recomienda que expore la simulación Stack Linked List Implementation (link)

4.1. Implementación#

La implementación de una pila (stack) a partir de una lista enlazada se muestra a continuación.

4.1.1. Nodo (`node`)#

Para demostrar que el contenido de un nodo puede ser de cualquier tipo, vamos a definir en la miembro data una cadena de caracteres (y no un entero como en el ejemplo anterior) tal y como se muestra en la siguiente figura:

../_images/CH_02-S07-LL_fig9.png — Fig. 101 Estructura del nodo#

A continuación se muestra la implementación en C de la estructura nodo (node):

struct _node {
    char *data;
    struct _node* next;
};

typedef struct _node node;

Los miembros son los mismos, el payload (data) y el apuntador al nodo siguiente (next):

../_images/CH_02-S07-LL_fig10.png — Fig. 102 Estructura del nodo (pythontutor)#

4.1.2. Pila (`stack`)#

La otra estructura involucrada es la pila (stack) cuya forma se muestra a continuación:

../_images/CH_02-S07-LL_fig11.png — Fig. 103 Estructura pila (`stack`)#

La implementación en c de esta estructura se muestra a continución:

typedef struct _stack {
    node *top;
} stack;

En este caso, el miembro top es un apuntador al nodo que se encuentra en el tope de la pila (stack).

../_images/CH_02-S07-LL_fig12.png — Fig. 104 Estructura pila (`stack`) en pythontutor.#

4.1.3. Funciones de la pila#

Las operaciones basicas asociadas sobre una pila se muestran a continuacion:

Operación	Descripción
`void Stack_init(stack *s)`	Inicializa la pila (`stack`).
`int Stack_push(stack s, char data)`	Pone un dato en la pila.
`char* Stack_pop(stack *s)`	Retira un dato de la pila.
`char* Stack_peek(stack *s)`	Obtiene el elemento cima de la pila.
`void Stack_print(stack *s)`	Muestra la pila

Pueden definirse otras operaciones para determinar si la pila esta vacia o para vaciarla, sin embargo, en nuestro caso no se realizo su implementación.

A continuación se muestra la definición de cada una de las funciones descritas en la tabla anterior:

Stack_init: Inicializa la pila colocando el miembro top a NULL.
```
void Stack_init(stack *s) {
  s->top = NULL;
}
```

Stack_push: Inserta un dato (data) en la pila. Si la operación es correcta devuelve 0, si la operación falla devuelve 0.

int Stack_push(stack *s, char *data) {
  node *new = malloc(sizeof(node));
  if (new == NULL) {
    perror("malloc");
    return -1;
  }
  else {
    new->data = (char *)malloc((strlen(data) + 1)*sizeof(char));
    strcpy(new->data, data);
    if (s->top != NULL) {
      new->next = s->top;
    }
    else {
      new->next = NULL;
    }
    s->top = new;
    return 0;
  }
}

Stack_pop: Saca el dato que se encuentra en el tope de la pila y actualiza el miembro top para que apunte al proximo elemento. So el resultado es verdadero retorna el dato del nodo eliminado (una cadena de caracteres) para el caso.

char* Stack_pop(stack *s) {    
  node *popped;
  char *data;
  if (s->top == NULL) {
    printf("Empty Stack\n");
    return NULL;
  }
  else {        
    popped = s->top;        
    s->top = s->top->next;
    data = strdup(popped->data);
    free(popped->data);
    free(popped);
    return data;
  }
}

Stack_peek: Retorna el contenido del nodo que se encuentra en el cima de la pila o NULL en caso de que esta se encuentre vacia.

char* Stack_peek(stack *s) {
  if(s->top != NULL) {
    return s->top->data;     
  }
  else {
    printf("Empty Stack\n");
    return NULL; 
  }
} 

Stack_print: Imprime el stack.

void Stack_print(stack *s) {
  node *current = s->top;
  if (current == NULL) {
    printf("Empty Stack.\n");
  } 
  else { 
    while (current) {
      printf("| %10s |\n", current->data);
      current = current->next;
    } 
    printf("--------------\n");
  } 
}

4.2. Ejemplos#

Codigo 1: El código mostrado a continuación realiza las siguientes tareas:

Crear una pila (stack) vacia.

Fig. 105 Estado inicial de la pila#
Agregar los nombres de los 3 hijos de la familia Simpson (Bart, Lisa y Maggie).

Fig. 106 Estado de la pila despues de agregar tres elementos#
Imprimir la pila.
Imprimir la cadena de caracteres perteneciente al elemento que se encuentra en la cima de la pila.
Sacar un elemento de la pila imprimiendo la cadena (data) asociado a este elemento.
Vaciar la pila.

Fig. 107 Estado final de de la pila#

A continuación se muestra el código asociado al problema:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

struct _node {
  char *data;
  struct _node* next;
};

typedef struct _node node;

typedef struct _stack {
  node *top;
} stack;

void Stack_init(stack *s);
int Stack_push(stack *s, char *data);
char* Stack_pop(stack *s);
char* Stack_peek(stack *s);
void Stack_print(stack *s);

int main() {
  stack s;
  Stack_init(&s);
  char *the_simpson[] = {
    "Bart",
    "Lisa",
    "Maggie"
  }; 
  printf("Agregando elementos a la pila:\n");
  Stack_push(&s, the_simpson[0]);
  Stack_push(&s, the_simpson[1]);
  Stack_push(&s, the_simpson[2]);
  Stack_print(&s);
  char *child = NULL;

  printf("\nElemento Top: %s\n",Stack_peek(&s));
  printf("Vaciando la pila:\n");
  child = Stack_pop(&s);
  printf("Elemento sacado -> %s\n",child);
  child = Stack_pop(&s);
  printf("Elemento sacado -> %s\n",child);
  child = Stack_pop(&s);
  printf("Elemento sacado -> %s\n",child);

  if(child != NULL) {
    free(child);
    child = NULL;
  }
  return 0;
}

void Stack_init(stack *s) {
  s->top = NULL;
}

int Stack_push(stack *s, char *data) {
  node *new = malloc(sizeof(node));
  if (new == NULL) {
    perror("malloc");
    return -1;
  }
  else {
    new->data = (char *)malloc((strlen(data) + 1)*sizeof(char));
    strcpy(new->data, data);
    if (s->top != NULL) {
      new->next = s->top;
    }
    else {
      new->next = NULL;
    }
    s->top = new;
    return 0;
  }
}

char* Stack_pop(stack *s) {    
  node *popped;
  char *data;
  if (s->top == NULL) {
    printf("Empty Stack\n");
    return NULL;
  }
  else {        
    popped = s->top;        
    s->top = s->top->next;
    data = strdup(popped->data);
    free(popped->data);
    free(popped);
    return data;
  }
}

char* Stack_peek(stack *s) {
  if(s->top != NULL) {
    return s->top->data;     
  }
  else {
    printf("Empty Stack\n");
    return NULL; 
  }
} 

void Stack_print(stack *s) {
  node *current = s->top;
  if (current == NULL) {
    printf("Empty Stack.\n");
  } 
  else { 
    while (current) {
      printf("| %10s |\n", current->data);
      current = current->next;
    } 
    printf("--------------\n");
  } 
}

La salida resultante del código anterior se muestra a continuación:

../_images/CH_02-S07-LL_fig15.png — Fig. 108 Salida en pantalla.#

La simulación se encuentra en el siguiente link

4. Enlaces#

https://ranger.uta.edu/~alex/courses/3318/
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
http://cslibrary.stanford.edu/
https://web.stanford.edu/dept/cs_edu/resources/textbook/
https://web.stanford.edu/class/cs106x/handouts.html
https://web.stanford.edu/class/cs107/
https://web.stanford.edu/class/archive/cs/cs107/cs107.1248/calendar
https://web.stanford.edu/class/cs106x/res/reader/CS106BX-Reader.pdf
http://cslibrary.stanford.edu/
https://www.cs.swarthmore.edu/~newhall/cs45/s14/#schedule
https://www.cs.swarthmore.edu/~newhall/unixlinks.html#lang
https://publications.gbdirect.co.uk/c_book/
https://www.cs.swarthmore.edu/~newhall/unixlinks.html#Clang
https://www.cs.swarthmore.edu/~newhall/unixhelp/os_stats.php
https://www.cs.swarthmore.edu/~newhall/cs35/
https://www.cs.swarthmore.edu/~newhall/unixhelp/C_linkedlists.pdf
https://www.cs.princeton.edu/courses/archive/spring20/cos217/
https://www.cs.princeton.edu/courses/archive/spring20/cos217/precepts/09voidptrs/symtablelist.pdf
https://www.cs.princeton.edu/courses/archive/spring20/cos217/lectures/01_Intro.pdf
https://august.princeton.edu/
https://www.cs.princeton.edu/courses/archive/fall07/cos217/lectures/
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/pages/lectures-and-assignments/data-structures-debugging/
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/pages/lectures-and-assignments/data-structures-debugging/
https://ocw.mit.edu/courses/6-033-computer-system-engineering-spring-2018/
https://ocw.mit.edu/courses/6-828-operating-system-engineering-fall-2012/
https://ocw.mit.edu/courses/6-087-practical-programming-in-c-january-iap-2010/
https://ocw.mit.edu/courses/6-087-practical-programming-in-c-january-iap-2010/pages/lecture-notes/
https://ocw.mit.edu/courses/1-00-introduction-to-computers-and-engineering-problem-solving-spring-2012/
https://ocw.mit.edu/courses/6-0002-introduction-to-computational-thinking-and-data-science-fall-2016/
https://ocw.mit.edu/courses/6-100l-introduction-to-cs-and-programming-using-python-fall-2022/
https://ocw.mit.edu/collections/introductory-programming/
https://cs61c.org/su24/
https://www.cs.princeton.edu/courses/archive/spr24/cos126/schedule/
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/schedule.html
https://bytesoftheday.wordpress.com/2014/07/04/q14/
https://www.cs.princeton.edu/courses/archive/spring20/cos217/
https://embeddedwala.com/Blogs/embedded-c/memory-layout-of-c-program
https://www.cs.mtsu.edu/~cs2170/C++labs/lab18/OSmemlayout.pdf
https://d1b10bmlvqabco.cloudfront.net/attach/j6fe5friemd22w/hzd1madqsie3ts/j7kw6i4tmqf8/61C_Note_1_Memory.pdf
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/bba9056d5290198d563edc47dfcff0e9_MIT6_S096_IAP13_lec3.pdf
https://cs61c.org/su24/
http://wla.berkeley.edu/~cs61c/fa17/
https://www.cs.princeton.edu/courses/archive/fall07/cos217/index.html
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/lectures/21-cmem/writeup/pdf/main.pdf
https://cs.gmu.edu/~zduric/cs262/Slides/teoX.pdf
https://d1b10bmlvqabco.cloudfront.net/attach/j6fe5friemd22w/hzd1madqsie3ts/j7kw6i4tmqf8/61C_Note_1_Memory.pdf
https://www.cs.princeton.edu/courses/archive/fall07/cos217/
https://www.cs.mtsu.edu/~cs2170/C++labs/lab18/OSmemlayout.pdf
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/lectures/21-cmem/writeup/pdf/main.pdf
https://www.cs.princeton.edu/courses/archive/spr24/cos126/schedule/
https://github.com/vishwa27yvs/Intro-to-Computer-Science-COS-126
https://www.berthon.eu/wiki/foss:wikishelf:linux:memory
http://resources.infosecinstitute.com/system-address-map-initialization-in-x86x64-architecture-part-1-pci-based-systems/#gref
https://fypandroid.wordpress.com/2011/01/17/anatomy-of-a-program-in-memory/
https://www.securitysift.com/windows-exploit-development-part-1-basics/
https://www.ibm.com/developerworks/library/j-nativememory-linux/
https://gabrieletolomei.wordpress.com/miscellanea/operating-systems/in-memory-layout/
http://www.cs.utexas.edu/users/fussell/cs310h/lectures/Lecture_17-310h.pdf
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-087-practical-programming-in-c-january-iap-2010/lecture-notes/
https://stackoverflow.com/questions/2128728/allocate-matrix-in-c
https://www.geeksforgeeks.org/dynamically-allocate-2d-array-c/
https://www.programiz.com/c-programming/c-dynamic-memory-allocation
https://www.cs.swarthmore.edu/~newhall/unixhelp/C_arrays.html
https://engineering.purdue.edu/ece264/

Introducción al lenguaje C

Listas enlazadas

Contents

Listas enlazadas#

1. Introduccion#

2. Lista enlazada simple#

2.1. Estructuras asociadas a una lista enlazada simple#

2.1.1. Nodo (`node`)#

2.1.2. Lista#

2.2. Funciones de la lists#

3. Uso de la estructura `list`#

3.1. Ejemplos#

4. Construcción de una pila (`stack`) a partir de una lista enlazada#

4.1. Implementación#

4.1.1. Nodo (`node`)#

4.1.2. Pila (`stack`)#

4.1.3. Funciones de la pila#

4.2. Ejemplos#

4. Enlaces#

Introducción al lenguaje C

Listas enlazadas

Contents

Listas enlazadas#

1. Introduccion#

2. Lista enlazada simple#

2.1. Estructuras asociadas a una lista enlazada simple#

2.1.1. Nodo (node)#

2.1.2. Lista#

2.2. Funciones de la lists#

3. Uso de la estructura list#

3.1. Ejemplos#

4. Construcción de una pila (stack) a partir de una lista enlazada#

4.1. Implementación#

4.1.1. Nodo (node)#

4.1.2. Pila (stack)#

4.1.3. Funciones de la pila#

4.2. Ejemplos#

4. Enlaces#

2.1.1. Nodo (`node`)#

3. Uso de la estructura `list`#

4. Construcción de una pila (`stack`) a partir de una lista enlazada#

4.1.1. Nodo (`node`)#

4.1.2. Pila (`stack`)#