Listas Simples y Dobles

LISTAS SIMPES Y LISTAS DOBLES

Para entender cómo funcionan las listas simples y las listas dobles debemos de tener en claro los siguientes conceptos, a partir de esto nos quedara más claro el funcionamiento.

Listas: son estructuras de datos en las cuales los datos almacenados se encuentran ordenados de manera continuas una detrás del otro. Las listas son almacenadas en la memoria principalde una computadora, en posiciones sucesivas de memoria.
Nodo: dentro de una estructura de datos se dice de un espacio en el cual se contiene un dato de interés y un puntero para poder referirse a otro nodo.
Puntero: un puntero se define como una variable en la cual el valor es la dirección de memoria o posición de otra variable.

INFO
SIG
PUNTERO
VALOR
NODO

LISTAS SIMPLEMENTE ENLAZADASLas listas enlazadas o encadenadas son aquellas que contienen un conjunto de elementos en los que cada elemento contiene la posición de memoria del elemento que le sigue.
Cada elemento de una lista contiene dos campos, uno en el cual se encuentra el valor del elemento y el segundo en el cual se encuentra el enlace, el cual contiene la posición de de memoria del siguiente elemento.
Lasoperaciones que se pueden realizar en una lista son:
* Recorrido de la lista
* Inserción de un elemento dentro de la lista
* Borrado de un elemento
* Búsqueda de un elemento

INFO
SIG
INFO
SIG
INFO
NULL

CREACIÓN DE UNA LISTA ENLAZADA

Algoritmos:

1. Crea una lista, agregando cada nuevo nodo al inicio de la misma

P y Q= variables de tipo puntero.
P = apuntará alinicio de la lista

1. CREA (P) //Crea el primer nodo de la lista
2. Leer P->INFO
3. Hacer P->SIG=NULL
4. Repetir
CREA (Q)
Leer Q->INFO
Hacer Q->SIG=P y P = Q

5. Hasta que ya no haya información

2.- Crea una lista, agregando cada nuevo nodo al final de la misma.

P y Q = variables de tipo puntero.
P= apuntará al inicio de la lista

1. CREA (P) {Crea elprimer nodo de la lista}
2. Leer P->INFO
3. Hacer P->SIG=NIL y T=P
4. Repetir
CREA (Q)
Leer Q->INFORMACIÓN
Hacer Q->SIG=NIL, T->SIG=Q y T=Q
5. Hasta (que ya no haya información)



*INSERCIÓN DE UN ELEMENTO
Para insertar un nodo dentro de una lista se tienen 3 casos:

1.- Insertar un nodo al principio de la lista
Algoritmo:

Q= variable de tipoapuntador
P= apunta al primer nodo de la lista
DATO= información del nodo nuevo

1. CREA (Q)
2. Hacer Q->INFO =DATO, Q->SIG=P y P=Q

P
P

DATO

Q
NULL

2.- insertar un nodo al final de la lista:

P =el apuntador al primer nodo de la lista
DATO = información que se almacenará en el nuevo nodo
Q y T = variables de tipo puntero

1. Hacer T= P
2. Repetir mientras T ->SIG=! NULL
//Recorre la lista hasta llegar al último elemento
Hacer T=T->SIG
3. //Fin del ciclo del paso 2
4. CREA (Q)
5. Hacer Q->INFO =DATO, Q->SIG =NULL y T->SIG =Q

NULL
DATO

NULL
P

Q
T

3.- insertar un nodo antes o después que otro
Los algoritmos son los siguientes:

INSERTAR ANTES

REF= referencia.
P= apuntador al primer nodo de la lista
DATO =información que se almacenará en el nuevo nodo
Q, X y T= son variables de tipo puntero, BAND es una variable de tipo booleano}

1. Hacer Q= P y BAND= VERDADERO
2. Repetir mientras (Q->INFO =! REF) y (BAND = VERDADERO)

2.1 Si Q -> SIG =! NULL
Entonces
Hacer T= Q y Q= Q-> LIGA
Si no
Hacer BAND = FALSO
2.2 Fin del condicional del paso 2.1
3. Fin del ciclo delpaso 2
4. Si BAND = VERDADERO entonces
CREA(X)
Hacer X->INFO = DATO
4.1 Si P = Q //Es el primer nodo}
Entonces
Hacer X ->SIG = P y P = X
Si no
Hacer T ->SIG =X y X->SIG = Q
4.2 Fin del condicional del paso 4.1
5. Fin del condicional del paso 4

REF

NULL
P

X
T

Q
DATOS

INSERTAR DESPUES

REF= referencia
P es el apuntador al...