11.1: Introducción

Última actualización
Guardar como PDF

Page ID: 82441

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Una lista enlazada es una forma alternativa de recopilar una serie de instancias de un tipo de datos determinado. En comparación con las matrices, las listas enlazadas ofrecen las ventajas de no requerir memoria contigua para la colección y una manera fácil de reordenar la colección simplemente intercambiando punteros. Como veremos más adelante, las listas enlazadas también son muy flexibles a la hora de agregar o eliminar elementos a la colección. En el lado negativo, las listas enlazadas requieren algo más de memoria que las matrices (ya que se debe incluir espacio para punteros), y las matrices ofrecen un acceso rápido consistente a cualquier miembro de la matriz (las listas enlazadas requieren que la lista sea “caminada” para llegar a un miembro dado). Para crear una lista enlazada, se incluye un puntero al tipo de estructura en la definición de la estructura. Una vez que se crean las instancias del tipo de estructura, se encadenan mediante la colocación de las direcciones apropiadas en el campo de puntero.

A continuación se muestra un ejemplo gráfico con cuatro instancias de alguna estructura:

Imagina que cada estructura tiene un tamaño de 100 bytes. Además, supongamos que A se encuentra en la dirección de memoria 1000 (que abarca de 1000 a 1099), B está a ubicada en la dirección 2000, C en 3000 y D en 4000. Cada estructura contiene un puntero a la siguiente de la lista. A contiene un puntero a la dirección de B, B a C, y así sucesivamente. Por ejemplo, el valor del puntero de A es 2000 (la dirección de memoria de B), mientras que el valor del puntero de C es 4000 (la dirección de D).

Tenga en cuenta que &A es la parte superior de la lista, y que el último elemento significa que no quedan elementos al tener su puntero establecido en 0. Además, estos cuatro elementos podrían vincularse de cualquier manera simplemente cambiando los valores del puntero. Finalmente, los ítems A, B, C y D pueden residir en cualquier parte del mapa de memoria; no es necesario que sean contiguos. Por el contrario, si tuviéramos que hacer una matriz a partir de estas estructuras, tendrían que ser empaquetadas en la memoria en secuencia para ser indexadas correctamente. Es decir, si A se ubicara en la dirección 1000, B tendría que estar en 1100, C en 1200 y D en 1300, ya que cada uno tiene 100 bytes de tamaño ¹. Si quisieras reorganizar las estructuras (por ejemplo, para ordenarlas), agregar otras nuevas o eliminar las existentes, esto requeriría bastante trabajo con una matriz. Estas tareas son mucho más fáciles con una lista enlazada porque las estructuras mismas no son manipuladas, solo los punteros asociados.

La indexación de matrices funciona simplemente multiplicando el valor del índice por el tamaño del elemento en matriz, y luego usando este valor como un desplazamiento de la dirección inicial. Así, en este ejemplo, el ítem [2] (es decir, C) se encuentra multiplicando el índice de 2 por el tamaño de 100 bytes para lograr un desplazamiento de 200 desde la ubicación inicial de la dirección 1000, o 1200. Recuerde, el ítem [0] es A, mientras que el ítem [1] es B y el ítem [2] es C.