Linked lists · Listas enlazadas
Nodes joined by pointers
- A linked list is a chain of small structs called nodes, scattered around the heap.
- Each node holds a value and a pointer to the next node. Follow the pointers to walk the list.
- Unlike an array, a list can grow one node at a time without moving the others.
Nodos unidos por punteros
- Una lista enlazada es una cadena de pequeñas estructuras llamadas nodos, dispersos en el heap.
- Cada nodo contiene un valor y un puntero al siguiente nodo. Siga los punteros para recorrer la lista.
- A diferencia de un array, una lista puede crecer un nodo a la vez sin mover los demás.
A self-referential struct
- A node is a struct that contains a pointer to its own type:
struct Node { int data; struct Node *next; };—datais the value,nextpoints to the following node.- This is given for you as
Nodein each starter. The last node'snextisNULL.
Estructura autorreferencial
- Un nodo es una estructura que contiene un puntero a su propio tipo:
struct Node { int data; struct Node *next; };—dataes el valor,nextapunta al siguiente nodo.- Esto se le proporciona como
Nodeen cada plantilla inicial. Elnextdel último nodo esNULL.
head and the NULL end
- A single pointer, the head, points to the first node. From there you reach the rest.
- The very last node points to
NULL, which marks the end of the list. - An empty list is just
head == NULL— there are no nodes at all.
head y el final NULL
- Un único puntero, el head (cabeza), apunta al primer nodo. Desde allí se acciona al resto.
- El último nodo apunta a
NULL, lo cual marca el final de la lista. - Una lista vacía es simplemente
head == NULL— no hay ningún nodo.
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
Adding a node at the front
- To add to the front, make a new node, point its
nextat the old head, and return the new node as the new head. - This is fast — it does not touch any other node.
- Because the head changes, the function returns the new head, and the caller saves it.
Añadir un nodo al principio
- Para añadir al principio, cree un nuevo nodo, apunte su
nextal head anterior y devuelva el nuevo nodo como el nuevo head. - Esto es rápido — no toca ningún otro nodo.
- Dado que el head cambia, la función devuelve el nuevo head, y el llamador lo guarda.
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - Free every node; the last node points to
NULL.
Errores comunes
- Nunca pierda el puntero
head, o toda la lista quedará inaccesible. - Libere todos los nodos; el último nodo apunta a
NULL.
Now you try
- Walk a list with a
curpointer andcur = cur->next, stopping atNULL. - New nodes come from
malloc(sizeof(Node)); the checker frees the list. Do not write amain.
Ahora usted intenta
- Recorra una lista con un puntero
curycur = cur->next, deteniéndose enNULL. - Los nuevos nodos provienen de
malloc(sizeof(Node)); el verificador libera la lista. No escriba unmain.
Nodes and pointers · Nodos y punteros
Each node points to the next; insert/delete by re-linking. · Cada nodo apunta al siguiente; insertar/borrar mediante reencadenamiento.
Complete int length(const Node *head) so it counts the nodes in the list (0 for an empty list). Walk with ->next until NULL. The Node type is given. Do not · no write a main. · Complete int length(const Node *head) para que cuente los nodos en la lista (0 para una lista vacía). Recorra con ->next hasta NULL. El tipo Node está dado. No escriba un main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Complete int sum_list(const Node *head) so it returns the total of every node's data (0 for an empty list). The Node type is given. Do not · no write a main. · Complete int sum_list(const Node *head) para que devuelva la suma de data de cada nodo (0 para una lista vacía). El tipo Node está dado. No escriba un main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Complete Node *push_front(Node *head, int value) so it makes a new node (with malloc), points its next at the old head, and returns it as the new head. The checker frees the list. Do not · no write a main. · Completa Node *push_front(Node *head, int value) para que cree un nuevo nodo (con malloc), apunte su next al viejo head, y lo devuelva como el nuevo head. El verificador libera la lista. No escribas un main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.