Foro de elhacker.net

Saludos tengo unas cuantas dudas de cómo funcionan las Listas Doblemente Ligadas, cuando quiero insertar en alguna posición por ejemplo por la cabeza, como es doblemente ligada ¿tengo que hacer dos operaciones?¿una en cada dirección? algo como insertar por cabeza hacia adelante ó insertar por cabeza hacia atrás??

Aquí está como lo estoy enlazando:

NODO* crear_nodo(int x)
{
    NODO *p;
    p = (NODO*)malloc(sizeof(NODO));
    p->dato = x;
    p->ant = NULL;
    p->sig = NULL;
    return p;
}
 
void insertar_cabeza(NODO **cabeza,int x)
{
    NODO *nuevo;
    nuevo = crear_nodo(x);
    nuevo->sig = *cabeza;
    nuevo->ant = ???;
    *cabeza = nuevo;
}

solo que en el nuevo->ant no se que poner porque el puntero anterior también debería apuntar a cabeza

de antemano gracias

Hola!

En una lista doblemente enlazada cada nodo apunta hacia los vecinos que tiene, en los casos de los extremos, el primer y el último elemento de la lista solo apuntan al vecino que tiene sentido, i.e. el primer elemento apunta al siguiente, y ultimo al anterior, al resto de los campos deberías asignarles el valor NULL, i.e. el valor de "ant" en la cabeza es NULL, y el valor de "sig" en el ultimo elemento es NULL. Esto les de una propiedad en particular a estos elementos, que podes saber cual es el primero y cual es el ultimo con solo mirar sus campos.

Saludos.

Hola en una lista doble, el primer nodo y el ultimo nodo deben apuntar a NULL, por lo tanto tu codigo esta perfecto solo que en donde tienes nuevo->ant =???, aqui debes poner NULL ,saludos

Muchas gracias por sus respuestas :) pero entonces cuando quiero insertar por una posición no tengo que hacer dos operaciones?? por ejemplo si quiero insertar por cabeza tengo que hacer una función para insertar por cabeza hacia adelante y hacia atrás???

saludos

Hola!

¿Que sería insertar por cabeza hacia adelante o hacia atrás? Definí que serían para vos esas operaciones por favor.

Por otro lado, en un TAD (http://es.wikipedia.org/wiki/Tipo_de_dato_abstracto (http://es.wikipedia.org/wiki/Tipo_de_dato_abstracto)) "Lista" (puro) uno debería tener una única función de inserción, que es la que permite meter un elemento a la lista por adelante, comunmente llevan los nombres "append" o "insert_front" o cosas de ese estilo, que creo que es a lo que vos te referís con "insertar por cabeza".
En una lista doblemente enlazada, uno tiene tres operaciones de inserción debido a la facilidad que esta permite, estas operaciones son:

1) insertar por adelante.
2) insertar en la i-esima posición.
3) insertar por detrás.

son las tres funcionalidad básicas que tu TAD debería soportar siendo una Lista Doblemente Enlazada (http://es.wikipedia.org/wiki/Lista_(inform%C3%A1tica)#Lista_Doblemente_Enlazada (http://es.wikipedia.org/wiki/Lista_(inform%C3%A1tica)#Lista_Doblemente_Enlazada)).

Saludos.