Estructura de Datos : Lista Enlazada Simple

Definiciones

En una lista enlazada simple los sucesivos items de una lista pueden ser puestos en cualquier lugar de la memoria. En una lista enlazada simple cada elemento almacena la direccíón del siguiente. Esto contrasta con las listas sequenciales, cuyos items están contiguos en memoria.

Una cadena ( chain ) es una lista enlazada simple en la que su ultimo nodo tiene un campo de enlace en cero.

El la literatura inglesa esta estructura de datos se conoce como Singly Linked List.

Representaciones

Representación Vectorial ( Vectorial Representation )

           ( BAT, CAT, EAT, FAT, HAT, JAT, LAT, MAT, OAT, PAT, RAT, SAT, TAT, VAT,WAT )

Representación Secuencial ( Sequential Representation )

 Lista          +----------+    Agregar        +----------+    Sacar          +----------+
 Inicial    1   |   BAT    |    GAT        1   |   BAT    |    LAT        1   |   BAT    |
                +----------+                   +----------+                   +----------+
            2   |   CAT    |               2   |   CAT    |               2   |   CAT    |
                +----------+                   +----------+                   +----------+
            3   |   EAT    |               3   |   EAT    |               3   |   EAT    |
                +----------+                   +----------+                   +----------+
            4   |   FAT    |               4   |   FAT    |               4   |   FAT    |
                +----------+                   +----------+                   +----------+
            5   |   HAT    | ..........    5   |   GAT    |               5   |   GAT    |
                +----------+          .        +----------+                   +----------+
            6   |   JAT    | ........ ...> 6   |   HAT    |               6   |   HAT    |
                +----------+        .          +----------+                   +----------+
            7   |   LAT    | ...... .....> 7   |   JAT    |               7   |   JAT    |
                +----------+      .            +----------+                   +----------+
            8   |   MAT    | .... .......> 8   |   LAT    |    .........> 8   |   MAT    |
                +----------+    .              +----------+    .              +----------+
            9   |   OAT    |    .........> 9   |   MAT    | .... .......> 9   |   OAT    |
                +----------+                   +----------+      .            +----------+
           10   |   PAT    |       .      10   |   OAT    | ...... .....>10   |   PAT    |
                +----------+       .           +----------+        .          +----------+
           11   |   RAT    |       .      11   |   PAT    | ........     11   |   RAT    |
                +----------+       .           +----------+                   +----------+
                |   ...    |       .           |   ...    |       .           |   ...    |
                |   ...    |       .           |   ...    |       .           |   ...    |
                |   ...    |       .           |   ...    |       .           |   ...    |
                |   ...    |       .           |   ...    |       .           |   ...    |
                |   ...    |       .           |   ...    |       .           |   ...    |

Los requerimientos de memoria son mínimos. Observar que las inserciones y eliminaciones son muy costosas. Los nodos están en secuencia en memoria. No se requiere una variable de comienzo de lista. Cambio tiempo por espacio si la lista es dinámica.

Representación Enlazada ( Linked Representation )

                                        DATA            LINK
                                    +----------+    +----------+
                                1   |   HAT    |    |    15    |
                                    +----------+    +----------+
                                2   |          |    |          |
                         ...........+----------+....+----------+...........
                         .      3   |   CAT    |    |     4    |          . Concepto de Nodo
                         ...........+----------+....+----------+...........
                                4   |   EAT    |    |     9    |
                                    +----------+    +----------+
                                5   |          |    |          |
                                    +----------+    +----------+
                                6   |          |    |          |
                                    +----------+    +----------+
                                7   |   WAT    |    |     0 ...|..........> El final
                                    +----------+    +----------+
      El comienzo ..........>   8   |   BAT    |    |     3    |                                        +---+
                                    +----------+    +----------+                                      L | 8 | Variable de comienzo de lista
                                9   |   FAT    |    |     1    |                                        +---+
                                    +----------+    +----------+
                               10   |          |    |          |
                                    +----------+    +----------+
                               11   |   VAT    |    |     7    |
                                    +----------+    +----------+
                                    |   ...    |    |   ...    |
                                    |   ...    |    |   ...    |
                                    |   ...    |    |   ...    |
                                    |   ...    |    |   ...    |
                                    |   ...    |    |   ...    |

Los requerimientos de memoria son mayores debido al campo de enlace. Observar que las inserciones y eliminaciones no son muy costosas. Los nodos no están en secuencia en memoria. Se requiere una variable de comienzo de lista. Cambio espacio por tiempo si la lista es dinámica.

Representación Grafica ( Graphic Representation )

     +---+
   L |   |
     +---+
       .
       .           +---------+    +---------+    +---------+                   +---------+
       ...........>| BAT | *.|...>| CAT | *.|...>| EAT | *.|...> ......... ...>| WAT | 0 |
                   +---------+    +---------+    +---------+                   +---------+

Observar que se trata de una representación ficticia. No existe más halla de la representación a fines didácticos. Un gráfico vale mil palabras.

Representación Conjunto ( Pool Representation )

Pool de listas

L(i) = Origen de la lista i, para 1 =< i =< n

Condiciones iniciales

L(i) = 0, para 1 =< i =< n

Condiciones de borde

L(i) = 0, si y solo si la lista está vacia

     +---+         +---------+    +---------+    +---------+                   +---------+
  L1 |   |........>|     | *.|...>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |
     +---+         +---------+    +---------+    +---------+                   +---------+
     +---+         +---------+                   +---------+
  L2 |   |........>|     | *.|...> ......... ...>|     | 0 |
     +---+         +---------+                   +---------+
     +---+
  L3 | 0 |
     +---+
     +---+         +---------+    +---------+                   +---------+
  L4 |   |........>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |
     +---+         +---------+    +---------+                   +---------+
       .
       .
       .
       .
       .
     +---+         +---------+    +---------+    +---------+    +---------+                   +---------+
  Ln |   |........>|     | *.|...>|     | *.|...>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |
     +---+         +---------+    +---------+    +---------+    +---------+                   +---------+

L1, L2, L3, L4, ... y Ln es un conjunto de variables de comienzo de lista. Las estructuras de datos Arreglo o Vector son las adecuadas para almacenarlas.

Nodos

Un nodo es una colección de datos, DATA1, DATA2, ..., DATAn y un conjunto de enlaces, LINK1, LINK2, ..., LINKm. Los datos y los enlaces son llamados, en general, items. Cada item en un nodo es también llamado un campo. Un campo contiene un item de datos o un item de enlace.

        2   |          |    |          |
 ...........+----------+....+----------+...........
 .      3   |   CAT    |    |     4    |          . Concepto de Nodo      DATA(3) = CAT      LINK(3) = 4
 ...........+----------+....+----------+...........
        4   |   EAT    |    |     9    |


 ..................................................
 .          +----------+    +----------+          .
 .          |   DATA   |    |   LINK   |          . Concepto de Nodo
 .          +----------+    +----------+          .
 ..................................................


 ..................................................................................................................
 .          +----------+    +----------+    +----------+                    +----------+    +----------+          .
 .          |  DATA 1  |    |  DATA 2  |    |  DATA 3  |       ......       |  DATA n  |    |   LINK   |          . Concepto de Nodo
 .          +----------+    +----------+    +----------+                    +----------+    +----------+          .
 ..................................................................................................................

Funciones

Inserciones ( Inserts )

     +---+
   L |   |                                                         X
     +---+                                                         |
       .                                                           V
       .           +---------+    +---------+    +---------+    +---------+                   +---------+               +---------+
       ...........>| BAT | *.|...>| CAT | *.|...>| EAT | *.|...>| FAT | *.|..xxxxxxxxxxxxxxx.>| HAT | *.|...> ..... ...>| WAT | 0 |
                   +---------+    +---------+    +---------+    +---------+ .               . +---------+               +---------+
                                                                            .               .
                                                                            .  +---------+  .
                                                                            ..>| GAT | *.|... ( nodo libre solicitado )
                                                                               +---------+
                                                                                  A
                                                                                  |
                                                                                  Y

Tomar un nodo libre sin uso y dejar en la variable Y su dirección
Poner los datos a ingresar en DATA(Y)
Navegar la lista hasta el nodo previo a la inserción y registrar la dirección del nodo previo en la variable X
Poner en el enlace del nodo Y, la dirección a la que apuntaba el nodo previo X
Poner en el enlace del nodo X, la direccion del nuevo nodo Y

El siguiente procedimiento inserta un nuevo elemento en la lista L, luego del nodo X. L y X son variables de entrada.

procedure INSERT(L,X)
- call GETNODE(Y)
- DATA(Y) <---- 'OAT'
- if L = 0
  - then
    - L <---- Y
    - LINK(Y) <---- 0
  - else
    - LINK(Y) <---- LINK(X)
    - LINK(X) <---- Y
end INSERT

Observar que si se desea mantener la lista ordenada, previamente deberia determinarse X, el nodo previo, según el contenido a agregar, que en este caso es 'OAT'. Si 'OAT' existe en la lista debe anunciarse el evento.

Ejercicio : Elaborar un procedimiento que agrega a la lista L, el contenido dado en la variable C, siguiendo el órden alfabético. La función a crear es AGREGAR(L,C).

Eliminaciones ( Deletes )

     +---+
   L |   |                                                         X             Y
     +---+                                                         |             |
       .                                                           V             V
       .           +---------+    +---------+    +---------+    +---------+    xxxxxxxxxxx    +---------+                   +---------+
       ...........>| BAT | *.|...>| CAT | *.|...>| EAT | *.|...>| FAT | *.|..xxx GAT x xxxxx.>| HAT | *.|...> ......... ...>| WAT | 0 |
                   +---------+    +---------+    +---------+    +---------+ .  xxxxxxxxxxx  . +---------+                   +---------+
                                                                            .               .
                                                                            .................

Hallar la dirección del nodo previo al nodo que se desea eliminar, salvarla en la variable X.
Hallar la dirección del nodo que se desea eliminar, salvarla en la variable Y.
Poner en el enlace de X el enlace de Y
Devolver el nodo eliminado Y

El siguiente procedimiento elimina un elemento de la lista L, el nodo Y, el que está precedido por el nodo X. Si el nodo que se desea eliminar es el primer nodo de la lista, X debe ser 0. X, Y y L son variables de entrada.

procedure DELETE(X,Y,L)
- if X = 0
  - then
    - L <---- LINK(L)
  - else
    - LINK(X) <---- LINK(Y)
- call RETNODE(Y)
end DELETE

Ejercicio : Elaborar un procedimiento que elimina de la lista L, el contenido dado en la variable C. La funcion a crear es ELIMINAR(L,C).

Travesía ( Traversal )

Ejercicio : Elaborar un procedimiento para atravesar la lista L, desde su comienzo hasta el final, imprimiendo el contenido de cada nodo. La funcion a crear es NAVEGAR(L).

Borrados ( Erases )

El borrado de una lista completa, puede hacerse, eliminando todos los nodos, uno a uno, o eliminandos todos a la vez. El siguinete procedimiento realiza el borrado siguiendo el segundo método. L es una variable de entrada.

procedure ERASE(L)

if L = 0
- then
  - return
- else
  - p <---- L
  - while LINK(p) no es igual a 0 do
  - p <---- LINK(p)
  - end
LINK(p) <---- AV
AV <---- L

end ERASE

Observar que este algoritmo depende del largo de la lista. Es del tipo O(n).

   +---+         +---------+    +---------+                   +---------+          +---+         +---------+    +---------+    +---------+                   +---------+
 L |   |........>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |       AV |   |........>|     | *.|...>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |
   +---+         +---------+    +---------+                   +---------+          +---+         +---------+    +---------+    +---------+                   +---------+

     .................................................................................
     .                                                                               V
   +---+         +---------+    +---------+                   +---------+          +---+         +---------+    +---------+    +---------+                   +---------+
 L | * |........>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |       AV |   |........>|     | *.|...>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |
   +---+         +---------+    +---------+                   +---------+          +---+         +---------+    +---------+    +---------+                   +---------+
                                                                      .                             A
                                                                      ...............................

   +---+         +---------+    +---------+    +---------+    +---------+    +---------+    +---------+                   +---------+
AV |   |........>|     | *.|...>|     | *.|...>|     | *.|...>|     | *.|...>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |
   +---+         +---------+    +---------+    +---------+    +---------+    +---------+    +---------+                   +---------+

Longitud ( Length )

procedure LENGTH(L)

i <---- 0
if L = 0
- then
- else
  - ptr <---- L
  - repeat
    - i <---- i +1
    - prt <---- LINK(ptr)
  - until prt = 0
return(i)

end LENGTH

Una clasificación de Estructuras de Datos

Pilas

Pilas Secuenciales
Pilas Enlazadas

Colas

Colas Secuenciales
Colas Enlazadas

Listas

Listas Secuenciales
Listas Enlazadas
- Listas Enlazadas Simples
  - Listas Enlazadas Simples Encabezadas
  - Listas Enlazadas Simples Circulares
    - Listas Enlazadas Simples Circulares Encabezadas
- Listas Enlazadas Dobles
- Listas Enlazadas Generalizadas