b'\n_START_ARTICLE_\nLista enlazada\n_START_PARAGRAPH_\nEn ciencias de la computaci\xc3\xb3n, una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento._NEWLINE_Una lista enlazada es un tipo de dato autorreferenciado porque contienen un puntero o enlace (en ingl\xc3\xa9s link, del mismo significado) a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminaci\xc3\xb3n de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto est\xc3\xa1 previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: listas enlazadas simples, listas doblemente enlazadas, listas enlazadas circulares y listas enlazadas doblemente circulares._NEWLINE_Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp, Scheme y Haskell tienen estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.\n_START_SECTION_\nHistoria\n_START_PARAGRAPH_\nLas listas enlazadas fueron desarrolladas en 1955-56 por Cliff Shaw y Herbert Simon en RAND Corporation, como la principal estructura de datos para su Lenguaje de Procesamiento de la Informaci\xc3\xb3n (IPL). IPL fue usado por los autores para desarrollar varios programas relacionados con la inteligencia artificial, incluida la M\xc3\xa1quina de la Teor\xc3\xada General, el Solucionador de Problemas Generales, y un programa inform\xc3\xa1tico de ajedrez. Se public\xc3\xb3 en IRE Transactions on Information Theory en 1956, y en distintas conferencias entre 1957-1959, incluida Proceedings of the Western Joint Computer en 1957 y 1958, y en Information Processing (Procendentes de la primera conferencia internacional del procesamiento de la informaci\xc3\xb3n de la Unesco) en 1959. El diagrama cl\xc3\xa1sico actual, que consiste en bloques que representan nodos de la lista con flechas apuntando a los sucesivos nodos de la lista, apareci\xc3\xb3 en Programming the Logic Theory Machine, de Newell y Shaw. Newell y Simon fueron reconocidos por el ACM Turing Award en 1975 por \xe2\x80\x9chacer contribuciones b\xc3\xa1sicas a la inteligencia artificial, a la psicolog\xc3\xada del conocimiento humano y al procesamiento de las listas\xe2\x80\x9d._NEWLINE_El problema de los traductores del procesamiento natural del lenguaje condujo a Victor Yngve del Instituto Tecnol\xc3\xb3gico de Massachusetts (MIT) a usar listas enlazadas como estructura de datos en su COMIT, lenguaje de programaci\xc3\xb3n para computadoras, que investig\xc3\xb3 en el campo de la Ling\xc3\xbc\xc3\xadstica computacional. Un informe de este lenguaje, titulado \xe2\x80\x9cA programming language for mechanical translation\xe2\x80\x9d apareci\xc3\xb3 en Mechanical Translation en 1958. _NEWLINE_LISP, el principal procesador de listas, fue creado en 1958. Una de las principales estructuras de datos de LISP es la lista enlazada._NEWLINE_En torno a los 60, la utilidad de las listas enlazadas y los lenguajes que utilizaban estas estructuras como su principal representaci\xc3\xb3n de datos estaba bien establecida. Bert Green, del Lincoln Laboratory del MIT, public\xc3\xb3 un estudio titulado Computer languages for symbol manipulation en IRE Transaction on Human Factors in Electronics en marzo de 1961 que resum\xc3\xada las ventajas de las listas enlazadas. Un posterior art\xc3\xadculo, A Comparison of list-processing computer languages de Bobrow y Raphael, aparec\xc3\xada en Communications of the ACM en abril de 1964._NEWLINE_Muchos sistemas operativos desarrollados por la empresa Technical Systems Consultants (originalmente de West Lafayette Indiana y despu\xc3\xa9s de Raleigh, Carolina del Norte) usaron listas enlazadas simples como estructuras de ficheros. Un directorio de entrada apuntaba al primer sector de un fichero y daba como resultado porciones de la localizaci\xc3\xb3n del fichero mediante punteros. Los sistemas que utilizaban esta t\xc3\xa9cnica inclu\xc3\xadan Flex (para el Motorola 6800 CPU), mini-Flex (la misma CPU) y Flex9 (para el Motorola 6809 CPU). Una variante desarrollada por TSC se comercializ\xc3\xb3 a Smoke Signal Broadcasting en California, usando listas doblemente enlazadas del mismo modo._NEWLINE_El sistema operativo TSS, desarrollado por IBM para las m\xc3\xa1quinas System 360/370, usaba una lista doblemente enlazada para su cat\xc3\xa1logo de ficheros de sistema. La estructura de directorios era similar a Unix, donde un directorio pod\xc3\xada contener ficheros u otros directorios que se pod\xc3\xadan extender a cualquier profundidad. Una utilidad fue creada para arreglar problemas del sistema despu\xc3\xa9s de un fallo desde las porciones modificadas del cat\xc3\xa1logo de ficheros que estaban a veces en memoria cuando ocurr\xc3\xada el fallo. Los problemas eran detectados por comparaci\xc3\xb3n de los enlaces posterior y anterior por consistencia. Si el siguiente de ellos era corrupto y el anterior enlace del nodo infectado era encontrado, el enlace posterior era asignado al nodo marcado con el enlace anterior.\n_START_SECTION_\nListas simples enlazadas\n_START_PARAGRAPH_\nEs una lista enlazada de nodos, donde cada nodo tiene un \xc3\xbanico campo de enlace. Una variable de referencia contiene una referencia al primer nodo, cada nodo (excepto el \xc3\xbaltimo) enlaza con el nodo siguiente, y el enlace del \xc3\xbaltimo nodo contiene NULL para indicar el final de la lista. Aunque normalmente a la variable de referencia se la suele llamar top, se le podr\xc3\xada llamar como se desee.\n_START_SECTION_\nListas doblemente enlazadas\n_START_PARAGRAPH_\nUn tipo de lista enlazada m\xc3\xa1s sofisticado es la lista doblemente enlazada o lista enlazadas de dos v\xc3\xadas. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el \xc3\xbaltimo nodo._NEWLINE_En alg\xc3\xban lenguaje de muy bajo nivel, XOR-Linking ofrece una v\xc3\xada para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque esta t\xc3\xa9cnica no se suele utilizar.\n_START_SECTION_\nListas enlazadas circulares\n_START_PARAGRAPH_\nEn una lista enlazada circular, el primer y el \xc3\xbaltimo nodo est\xc3\xa1n unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier direcci\xc3\xb3n hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el m\xc3\xa1s usado para dirigir buffers para \xe2\x80\x9cingerir\xe2\x80\x9d datos, y para visitar todos los nodos de una lista a partir de uno dado.\n_START_SECTION_\nListas enlazadas simples circulares\n_START_PARAGRAPH_\nCada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del \xc3\xbaltimo apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados despu\xc3\xa9s de uno que ya tengamos referenciado. Por esta raz\xc3\xb3n, es usual quedarse con una referencia solamente al \xc3\xbaltimo elemento en una lista enlazada circular simple, esto nos permite r\xc3\xa1pidas inserciones al principio, y tambi\xc3\xa9n permite accesos al primer nodo desde el puntero del \xc3\xbaltimo nodo.\xe2\x80\x8b\n_START_SECTION_\nListas enlazadas doblemente circulares\n_START_PARAGRAPH_\nEn una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al \xc3\xbaltimo y el enlace siguiente del \xc3\xbaltimo nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a alg\xc3\xban nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que est\xc3\xa1 en la cabeza o al nodo cola, y as\xc3\xad mantener el orden tan bien como en una lista doblemente enlazada.\n_START_SECTION_\nNodos centinelas\n_START_PARAGRAPH_\nA veces las listas enlazadas tienen un nodo centinela (tambi\xc3\xa9n llamado falso nodo o nodo ficticio) al principio o al final de la lista, el cual no es usado para guardar datos. Su prop\xc3\xb3sito es simplificar o agilizar algunas operaciones, asegurando que cualquier nodo tiene otro anterior o posterior, y que toda la lista (incluso alguna que no contenga datos) siempre tenga un \xe2\x80\x9cprimer y \xc3\xbaltimo\xe2\x80\x9d nodo.\n_START_SECTION_\nAplicaciones de las listas enlazadas\n_START_PARAGRAPH_\nLas listas enlazadas son usadas como m\xc3\xb3dulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones._NEWLINE_El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta practica tiene su origen en el lenguaje de programaci\xc3\xb3n Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la \xc3\xbanica), y ahora es una caracter\xc3\xadstica com\xc3\xban en el estilo de programaci\xc3\xb3n funcional._NEWLINE_A veces, las listas enlazadas son usadas para implementar vectores asociativos, y estas en el contexto de las llamadas listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay mejores formas de implementar \xc3\xa9stas estructuras, por ejemplo con \xc3\xa1rboles binarios de b\xc3\xbasqueda equilibrados. Sin embargo, a veces una lista enlazada es din\xc3\xa1micamente creada fuera de un subconjunto propio de nodos semejante a un \xc3\xa1rbol, y son usadas m\xc3\xa1s eficientemente para recorrer \xc3\xa9sta serie de datos.\n_START_SECTION_\nVentajas\n_START_PARAGRAPH_\nComo muchas opciones en programaci\xc3\xb3n y desarrollo, no existe un \xc3\xbanico m\xc3\xa9todo correcto para resolver un problema. Una estructura de lista enlazada puede trabajar bien en un caso pero causar problemas en otros. He aqu\xc3\xad una lista con algunas de las ventajas m\xc3\xa1s comunes que implican las estructuras de tipo lista. En general, teniendo una colecci\xc3\xb3n din\xc3\xa1mica donde los elementos est\xc3\xa1n siendo a\xc3\xb1adidos y eliminados frecuentemente e importa la localizaci\xc3\xb3n de los nuevos elementos introducidos se incrementa el beneficio de las listas enlazadas.\n_START_SECTION_\nDoblemente enlazadas vs. simplemente enlazadas\n_START_PARAGRAPH_\nLas listas doblemente enlazadas requieren m\xc3\xa1s espacio por nodo y sus operaciones b\xc3\xa1sicas resultan m\xc3\xa1s costosas pero ofrecen una mayor facilidad para manipular ya que permiten el acceso secuencial a lista en ambas direcciones. En particular, uno puede insertar o borrar un nodo en un n\xc3\xbamero fijo de operaciones dando \xc3\xbanicamente la direcci\xc3\xb3n de dicho nodo (Las listas simples requieren la direcci\xc3\xb3n del nodo anterior para insertar o suprimir correctamente). Algunos algoritmos requieren el acceso en ambas direcciones.\n_START_SECTION_\nCirculares enlazadas vs. lineales enlazadas\n_START_PARAGRAPH_\nLas listas circulares son m\xc3\xa1s \xc3\xbatiles para describir estructuras circulares y tienen la ventaja de poder recorrer la lista desde cualquier punto. Tambi\xc3\xa9n permiten el acceso r\xc3\xa1pido al primer y \xc3\xbaltimo elemento por medio de un puntero simple.\n_START_SECTION_\nNodos centinelas (header nodes)\n_START_PARAGRAPH_\nLa b\xc3\xbasqueda com\xc3\xban y los algoritmos de ordenaci\xc3\xb3n son menos complicados si se usan los llamados Nodos Centinelas o Nodos Ficticios, donde cada elemento apunta a otro elemento y nunca a nulo. El Nodo Centinela o Puntero Cabeza contiene, como otro, un puntero siguiente que apunta al que se considera como primer elemento de la lista. Tambi\xc3\xa9n contiene un puntero previo que hace lo mismo con el \xc3\xbaltimo elemento. _NEWLINE_El Nodo Centinela es definido como otro nodo en una lista doblemente enlazada, la asignaci\xc3\xb3n del puntero frente no es necesaria y los puntero anterior y siguiente estar\xc3\xa1n apuntando a s\xc3\xad mismo en ese momento._NEWLINE_Si los punteros anterior y siguiente apuntan al Nodo Centinela la lista se considera vac\xc3\xada. En otro caso, si a la lista se le a\xc3\xb1aden elementos ambos puntero apuntar\xc3\xa1n a otros nodos._NEWLINE_Estos Nodos Centinelas simplifican muchos las operaciones pero hay que asegurarse de que los punteros anterior y siguiente existen en cada momento. _NEWLINE_Como ventaja eliminan la necesidad de guardar la referencia al puntero del principio de la lista y la posibilidad de asignaciones accidentales. Por el contrario, usan demasiado almacenamiento extra y resultan complicados en algunas operaciones.\n_START_SECTION_\nLenguajes soportados\n_START_PARAGRAPH_\nMuchos lenguajes de programaci\xc3\xb3n tales como Lisp y Scheme tienen listas enlazadas simples ya construidas. En muchos lenguajes de programaci\xc3\xb3n, estas listas est\xc3\xa1n construidas por nodos, cada uno llamado cons o celda cons. Las celdas cons tienen dos campos: el car, una referencia del dato al nodo, y el cdr, una referencia al siguiente nodo. Aunque las celdas cons pueden ser usadas para construir otras estructuras de datos, este es su principal objetivo._NEWLINE_En lenguajes que soportan tipos abstractos de datos o plantillas, las listas enlazadas ADTs o plantillas est\xc3\xa1n disponibles para construir listas enlazadas. En otros lenguajes, las listas enlazadas son t\xc3\xadpicamente construidas usando referencias junto con el tipo de dato record. _NEWLINE_En la secci\xc3\xb3n de implementaciones hay un ejemplo completo en C y en Maude\n_START_SECTION_\nAlmacenamiento interno y externo\n_START_PARAGRAPH_\nCuando se construye una lista enlazada, nos enfrentamos a la elecci\xc3\xb3n de si almacenar los datos de la lista directamente en los nodos enlazados de la lista, llamado almacenamiento interno, o simplemente almacenar una referencia al dato, llamado almacenamiento externo. El almacenamiento interno tiene la ventaja de hacer accesos a los datos m\xc3\xa1s eficientes, requiriendo menos almacenamiento global, teniendo mejor referencia de localidad, y simplifica la gesti\xc3\xb3n de memoria para la lista (los datos son alojados y desalojados al mismo tiempo que los nodos de la lista)._NEWLINE_El almacenamiento externo, por otro lado, tiene la ventaja de ser m\xc3\xa1s gen\xc3\xa9rico, en la misma estructura de datos y c\xc3\xb3digo m\xc3\xa1quina puede ser usado para una lista enlazada, no importa cual sea su tama\xc3\xb1o o los datos. Esto hace que sea m\xc3\xa1s f\xc3\xa1cil colocar el mismo dato en m\xc3\xbaltiples listas enlazadas. Aunque con el almacenamiento interno los mismos datos pueden ser colocados en m\xc3\xbaltiples listas incluyendo m\xc3\xbaltiples referencias siguientes en la estructura de datos del nodo, esto podr\xc3\xada ser entonces necesario para crear rutinas separadas para a\xc3\xb1adir o borrar celdas basadas en cada campo. Esto es posible creando listas enlazadas de elementos adicionales que usen almacenamiento interno usando almacenamiento externo, y teniendo las celdas de las listas enlazadas adicionales almacenadas las referencias a los nodos de las listas enlazadas que contienen los datos._NEWLINE_En general, si una serie de estructuras de datos necesita ser incluida en m\xc3\xbaltiples listas enlazadas, el almacenamiento externo es el mejor enfoque. Si una serie de estructuras de datos necesitan ser incluidas en una sola lista enlazada, entonces el almacenamiento interno es ligeramente mejor, a no ser que un paquete gen\xc3\xa9rico de listas gen\xc3\xa9ricas que use almacenamiento externo est\xc3\xa9 disponible. Asimismo, si diferentes series de datos que pueden ser almacenados en la misma estructura de datos son incluidos en una lista enlazada simple, entonces el almacenamiento interno puede ser mejor._NEWLINE_Otro enfoque que puede ser usado con algunos lenguajes implica tener diferentes estructuras de datos, pero todas tienen los campos iniciales, incluyendo la siguiente (y anterior si es una lista doblemente enlazada) referencia en la misma localizaci\xc3\xb3n. Despu\xc3\xa9s de definir estructuras distintas para cada tipo de dato, una estructura gen\xc3\xa9rica puede ser definida para que contenga la m\xc3\xadnima cantidad de datos compartidos por todas las estructuras y contenidos al principio de las estructuras. Entonces las rutinas gen\xc3\xa9ricas pueden ser creadas usando las m\xc3\xadnimas estructuras para llevar a cabo las operaciones de los tipos de las listas enlazadas, pero separando las rutinas que pueden manejar los datos espec\xc3\xadficos. Este enfoque es usado a menudo en rutinas de an\xc3\xa1lisis de mensajes, donde varios tipos de mensajes son recibidos, pero todos empiezan con la misma serie de campos, generalmente incluyendo un campo para el tipo de mensaje. Las rutinas gen\xc3\xa9ricas son usadas para a\xc3\xb1adir nuevos mensajes a una cola cuando son recibidos, y eliminarlos de la cola en orden para procesarlos. El campo de tipo de mensaje es usado para llamar a la rutina correcta para procesar el tipo espec\xc3\xadfico de mensaje._NEWLINE_En la secci\xc3\xb3n implementaciones (en este mismo art\xc3\xadculo) se expone c\xc3\xb3digo referente a este tema._NEWLINE_Hay que notar que cuando usamos almacenamiento externo, se necesita dar un paso extra para extraer la informaci\xc3\xb3n del nodo y hacer un casting dentro del propio tipo del dato. Esto es porque ambas listas, de familias y miembros, son almacenadas en dos listas enlazadas usando la misma estructura de datos (nodo), y este lenguaje no tiene tipos param\xc3\xa9tricos._NEWLINE_Si conocemos el n\xc3\xbamero de familias a las que un miembro puede pertenecer en tiempo de compilaci\xc3\xb3n, el almacenamiento interno trabaja mejor. Si, sin embargo, un miembro necesita ser incluido en un n\xc3\xbamero arbitrario de familias, sabiendo el n\xc3\xbamero espec\xc3\xadfico de familias solo en tiempo de ejecuci\xc3\xb3n, el almacenamiento externo ser\xc3\xa1 necesario.\n_START_SECTION_\nAgilizaci\xc3\xb3n de la b\xc3\xbasqueda\n_START_PARAGRAPH_\nBuscando un elemento espec\xc3\xadfico en una lista enlazada, incluso si esta es ordenada, normalmente requieren tiempo O (n) (b\xc3\xbasqueda lineal). Esta es una de las principales desventajas de listas enlazadas respecto a otras estructuras. Adem\xc3\xa1s algunas de las variantes expuestas en la secci\xc3\xb3n anterior, hay numerosas v\xc3\xadas simples para mejorar el tiempo de b\xc3\xbasqueda._NEWLINE_En una lista desordenada, una forma simple para decrementar el tiempo de b\xc3\xbasqueda medio es el mover al frente de forma heur\xc3\xadstica, que simplemente mueve un elemento al principio de la lista una vez que es encontrado. _NEWLINE_Esta idea, \xc3\xbatil para crear cach\xc3\xa9s simples, asegura que el \xc3\xadtem usado m\xc3\xa1s recientemente es tambi\xc3\xa9n el m\xc3\xa1s r\xc3\xa1pido en ser encontrado otra vez._NEWLINE_Otro enfoque com\xc3\xban es indizar una lista enlazada usando una estructura de datos externa m\xc3\xa1s eficiente. Por ejemplo, podemos construir un \xc3\xa1rbol rojo-negro o una tabla hash cuyos elementos est\xc3\xa1n referenciados por los nodos de las listas enlazadas. Pueden ser construidos m\xc3\xbaltiples \xc3\xadndices en una lista simple. La desventaja es que estos \xc3\xadndices puede necesitar ser actualizados cada vez que un nodo es a\xc3\xb1adido o eliminado (o al menos, antes que el \xc3\xadndice sea utilizado otra vez).\n_START_SECTION_\nEstructuras de datos relacionadas\n_START_PARAGRAPH_\nTanto las pilas como las colas son a menudo implementadas usando listas enlazadas, y simplemente restringiendo el tipo de operaciones que son soportadas._NEWLINE_La skip list, o lista por saltos, es una lista enlazada aumentada con capas de punteros para saltos r\xc3\xa1pidos sobre grandes n\xc3\xbameros de elementos, y descendiendo hac\xc3\xada la siguiente capa. Este proceso contin\xc3\xbaa hasta llegar a la capa inferior, la cual es la lista actual._NEWLINE_Un \xc3\xa1rbol binario puede ser visto como un tipo de lista enlazada donde los elementos est\xc3\xa1n enlazados entre ellos mismos de la misma forma. El resultado es que cada nodo puede incluir una referencia al primer nodo de una o dos listas enlazadas, cada cual con su contenido, formando as\xc3\xad los sub\xc3\xa1rboles bajo el nodo._NEWLINE_Una lista enlazada desenrollada es una lista enlazada cuyos nodos contiene un vector de datos. Esto mejora la ejecuci\xc3\xb3n de la cach\xc3\xa9, siempre que las listas de elementos est\xc3\xa9n contiguas en memoria, y reducen la sobrecarga de la memoria, porque necesitas menos metadatos para guardar cada elemento de la lista._NEWLINE_Una tabla hash puede usar listas enlazadas para guardar cadenas de \xc3\xadtems en la misma posici\xc3\xb3n de la tabla hash.\n_START_SECTION_\nImplementaciones\n_START_PARAGRAPH_\nAqu\xc3\xad se expone el c\xc3\xb3digo necesario para complementar el art\xc3\xadculo a fin de poder realizar una lectura \xc3\xa1gil sobre el art\xc3\xadculo y a su vez quien necesite el c\xc3\xb3digo pueda f\xc3\xa1cilmente encontrar el mismo si est\xc3\xa1 contenido.\n_START_SECTION_\nOperaciones sobre listas enlazadas\n_START_PARAGRAPH_\nCuando se manipulan listas enlazadas, hay que tener cuidado con no usar valores que hayamos invalidado en asignaciones anteriores. Esto hace que los algoritmos de insertar y borrar nodos en las listas sean algo especiales. A continuaci\xc3\xb3n se expone el pseudoc\xc3\xb3digo para a\xc3\xb1adir y borrar nodos en listas enlazadas simples, dobles y circulares.\n_START_SECTION_\nListas simples enlazadas\n_START_PARAGRAPH_\nNuestra estructura de datos tendr\xc3\xa1 dos campos. Vamos a mantener la variables PrimerNodos que siempre apunta al primer nodo de tal lista, \xc3\xb3 nulo para la lista vac\xc3\xada._NEWLINE_ record Node {_NEWLINE_    data // El dato almacenado en el nodo_NEWLINE_    next // Una referencia al nodo siguiente, nulo para el \xc3\xbaltimo nodo_NEWLINE_ }_NEWLINE_ record List {_NEWLINE_     Node PrimerNodo   // Apunta al primer nodo de la lista; nulo para la lista vac\xc3\xada_NEWLINE_ }_NEWLINE_El recorrido en una lista enlazada es simple, empezamos por el primer nodo y pasamos al siguiente hasta que la lista llegue al final._NEWLINE_ node\xc2\xa0:= list.PrimerNodo_NEWLINE_ while node not null {_NEWLINE_     node\xc2\xa0:= node.next_NEWLINE_ }_NEWLINE_El siguiente c\xc3\xb3digo inserta un elemento a continuaci\xc3\xb3n de otro en una lista simple. El diagrama muestra como funciona._NEWLINE__NEWLINE_  _NEWLINE_ function insertAfter(Node node, Node newNode) {_NEWLINE_     newNode.next\xc2\xa0:= node.next_NEWLINE_     node.next    := newNode_NEWLINE_ }_NEWLINE_Insertar al principio de una lista requiere una funci\xc3\xb3n por separado. Se necesita actualizar PrimerNodo._NEWLINE_ function insertBeginning(List list, Node newNode) {_NEWLINE_     newNode.next   := list.firstNode_NEWLINE_     list.firstNode\xc2\xa0:= newNode_NEWLINE_ }_NEWLINE_De forma similar, tambi\xc3\xa9n tenemos funciones para borrar un nodo dado \xc3\xb3 para borrar un nodo del principio de la lista. Ver diagrama._NEWLINE_ function removeAfter(Node node) { _NEWLINE_     obsoleteNode\xc2\xa0:= node.next_NEWLINE_     node.next\xc2\xa0:= node.next.next_NEWLINE_     destroy obsoleteNode_NEWLINE_ }_NEWLINE_ function removeBeginning(List list) { _NEWLINE_     obsoleteNode\xc2\xa0:= list.firstNode_NEWLINE_     list.firstNode\xc2\xa0:= list.firstNode.next          _NEWLINE_     destroy obsoleteNode_NEWLINE_ }_NEWLINE_Advertimos que BorrarPrincipio pone PrimerNodo a nulo cuando se borra el \xc3\xbaltimo elemento de la lista._NEWLINE_Adjuntar una lista enlazada a otra puede resultar ineficiente a menos que se guarde una referencia a la cola de la lista, porque si no tendr\xc3\xadamos que recorrer la lista en orden hasta llegar a la cola y luego a\xc3\xb1adir la segunda lista.\n_START_SECTION_\nListas doblemente enlazadas\n_START_PARAGRAPH_\nCon estas listas es necesario actualizar muchos m\xc3\xa1s punteros pero tambi\xc3\xa9n se necesita menos informaci\xc3\xb3n porque podemos usar un puntero para recorrer hacia atr\xc3\xa1s y consultar elementos. Se crean nuevas operaciones y elimina algunos casos especiales. A\xc3\xb1adimos el campo anterior a nuestros nodos, apuntando al elemento anterior, y UltimoNodo a nuestra estructura, el cual siempre apunta al \xc3\xbaltimo elemento de la lista. PrimerNodo y UltimoNodo siempre est\xc3\xa1n a nulo en la lista vac\xc3\xada._NEWLINE_ record Node {_NEWLINE_    data // El dato almacenado en el nodo_NEWLINE_    next // Una referencia al nodo siguiente, nulo para el \xc3\xbaltimo nodo_NEWLINE_    prev // Una referencia al nodo anterior, nulo para el primer nodo_NEWLINE_ }_NEWLINE_ record List {_NEWLINE_     Node firstNode   // apunta al primer nodo de la lista; nulo para la lista vac\xc3\xada_NEWLINE_     Node lastNode    // apunta al \xc3\xbaltimo nodo de la lista; nulo para la lista vac\xc3\xada_NEWLINE_ }_NEWLINE_Formas de recorrer la lista:_NEWLINE_Hacia Delante_NEWLINE_ node\xc2\xa0:= list.firstNode_NEWLINE_ while node \xe2\x89\xa0 null_NEWLINE_     <do something with node.data>_NEWLINE_     node\xc2\xa0:= node.next_NEWLINE_Hacia Atr\xc3\xa1s_NEWLINE_ node\xc2\xa0:= list.lastNode_NEWLINE_ while node \xe2\x89\xa0 null_NEWLINE_     <do something with node.data>_NEWLINE_     node\xc2\xa0:= node.prev_NEWLINE_Estas funciones sim\xc3\xa9tricas a\xc3\xb1aden un nodo despu\xc3\xa9s o antes de uno dado:_NEWLINE_ function insertAfter(List list, Node node, Node newNode)_NEWLINE_     newNode.prev\xc2\xa0:= node_NEWLINE_     newNode.next\xc2\xa0:= node.next_NEWLINE_     if node.next = null_NEWLINE_         node.next\xc2\xa0:= newNode_NEWLINE_         list.lastNode\xc2\xa0:= newNode_NEWLINE_     else_NEWLINE_         node.next.prev\xc2\xa0:= newNode_NEWLINE_         node.next\xc2\xa0:= newNode_NEWLINE_ function insertBefore(List list, Node node, Node newNode)_NEWLINE_     newNode.prev\xc2\xa0:= node.prev_NEWLINE_     newNode.next\xc2\xa0:= node_NEWLINE_     if node.prev is null_NEWLINE_         node.prev\xc2\xa0:= newNode_NEWLINE_         list.firstNode\xc2\xa0:= newNode_NEWLINE_     else_NEWLINE_         node.prev.next\xc2\xa0:= newNode_NEWLINE_         node.prev\xc2\xa0:= newNode_NEWLINE_Tambi\xc3\xa9n necesitamos una funci\xc3\xb3n para insertar un nodo al comienzo de una lista posiblemente vac\xc3\xada._NEWLINE_ function insertBeginning(List list, Node newNode)_NEWLINE_     if list.firstNode = null_NEWLINE_         list.firstNode\xc2\xa0:= newNode_NEWLINE_         list.lastNode  := newNode_NEWLINE_         newNode.prev\xc2\xa0:= null_NEWLINE_         newNode.next\xc2\xa0:= null_NEWLINE_     else_NEWLINE_         insertBefore (list, list.firstNode, newNode)_NEWLINE_Una funci\xc3\xb3n sim\xc3\xa9trica que inserta al final:_NEWLINE_ function insertEnd(List list, Node newNode)_NEWLINE_     if list.lastNode = null_NEWLINE_         insertBeginning (list, newNode)_NEWLINE_     else_NEWLINE_         insertAfter (list, list.lastNode, newNode)_NEWLINE_Borrar un nodo es f\xc3\xa1cil, solo requiere usar con cuidado firstNode y lastNode._NEWLINE_ function remove(List list, Node node)_NEWLINE_   if node.prev = null_NEWLINE_       list.firstNode\xc2\xa0:= node.next_NEWLINE_   else_NEWLINE_       node.prev.next\xc2\xa0:= node.next_NEWLINE_   if node.next = null_NEWLINE_       list.lastNode\xc2\xa0:= node.prev_NEWLINE_   else_NEWLINE_       node.next.prev\xc2\xa0:= node.prev_NEWLINE_   destroy node_NEWLINE_Una consecuencia especial de este procedimiento es que borrando el \xc3\xbaltimo elemento de una lista se ponen PrimerNodo y UltimoNodo a nulo, habiendo entonces un problema en una lista que tenga un \xc3\xbanico elemento.\n_START_SECTION_\nListas enlazadas circulares\n_START_PARAGRAPH_\nEstas pueden ser simples o doblemente enlazadas. En una lista circular todos los nodos est\xc3\xa1n enlazados como un c\xc3\xadrculo, sin usar nulo. Para listas con frente y final (como una cola), se guarda una referencia al \xc3\xbaltimo nodo de la lista. El siguiente nodo despu\xc3\xa9s del \xc3\xbaltimo ser\xc3\xada el primero de la lista. Los elementos se pueden a\xc3\xb1adir por el final y borrarse por el principio en todo momento._NEWLINE_Ambos tipos de listas circulares tienen la ventaja de poderse recorrer completamente empezando desde cualquier nodo. Esto nos permite normalmente evitar el uso de PrimerNodo y UltimoNodo, aunque si la lista estuviera vac\xc3\xada necesitar\xc3\xadamos un caso especial, como una variable UltimoNodo que apunte a alg\xc3\xban nodo en la lista o nulo si est\xc3\xa1 vac\xc3\xada._NEWLINE_Las operaciones para estas listas simplifican el insertar y borrar nodos en una lista vac\xc3\xada pero introducen casos especiales en la lista vac\xc3\xada.\n_START_SECTION_\nListas enlazadas doblemente circulares\n_START_PARAGRAPH_\nAsumiendo que someNodo es alg\xc3\xban nodo en una lista no vac\xc3\xada, esta lista presenta el comienzo de una lista con someNode._NEWLINE_Hacia Delante_NEWLINE_ node\xc2\xa0:= someNode_NEWLINE_ do_NEWLINE_     do something with node.value_NEWLINE_     node\xc2\xa0:= node.next_NEWLINE_ while node\xc2\xa0!= someNode_NEWLINE_Hacia Atr\xc3\xa1s_NEWLINE_ node\xc2\xa0:= someNode_NEWLINE_ do_NEWLINE_     do something with node.value_NEWLINE_     node\xc2\xa0:= node.prev_NEWLINE_ while node\xc2\xa0:= someNode_NEWLINE__NEWLINE_Esta funci\xc3\xb3n inserta un nodo en una lista enlazada doblemente circular despu\xc3\xa9s de un elemento dado:_NEWLINE_ function insertAfter(Node node, Node newNode)_NEWLINE_     newNode.next\xc2\xa0:= node.next_NEWLINE_     newNode.prev\xc2\xa0:= node_NEWLINE_     node.next.prev\xc2\xa0:= newNode_NEWLINE_     node.next      := newNode_NEWLINE_Para hacer  "insertBefore", podemos simplificar "insertAfter (node.prev, newNode)". Insertar un elemento en una lista que puede estar vac\xc3\xada requiere una funci\xc3\xb3n especial._NEWLINE_ function insertEnd(List list, Node node)_NEWLINE_     if list.lastNode = null_NEWLINE_         node.prev\xc2\xa0:= node_NEWLINE_         node.next\xc2\xa0:= node_NEWLINE_     else_NEWLINE_         insertAfter (list.lastNode, node)_NEWLINE_     list.lastNode\xc2\xa0:= node_NEWLINE_Para insertar al principio simplificamos "insertAfter (list.lastNode, node)". _NEWLINE_ function remove(List list, Node node)_NEWLINE_     if node.next = node_NEWLINE_         list.lastNode\xc2\xa0:= null_NEWLINE_     else_NEWLINE_         node.next.prev\xc2\xa0:= node.prev_NEWLINE_         node.prev.next\xc2\xa0:= node.next_NEWLINE_         if node = list.lastNode_NEWLINE_             list.lastNode\xc2\xa0:= node.prev;_NEWLINE_     destroy node_NEWLINE_Como una lista doblemente enlazada, "removeAfter" y "removeBefore" puede ser implementada con "remove (list, node.prev)" y "remove (list, node.next)".\n_START_SECTION_\nListas enlazadas usando vectores de nodos\n_START_PARAGRAPH_\nPreviamente se crea una estructura que contiene los apuntadores:_NEWLINE_record Entry {_NEWLINE_    integer next; // \xc3\xadndice de la nueva entrada en el vector_NEWLINE_    integer prev; // entrada previa_NEWLINE_    string name;_NEWLINE_    real balance;_NEWLINE_ }_NEWLINE_Y finalmente se declara el vector:_NEWLINE_integer listHead;_NEWLINE_Entry Records[1000];\n_START_SECTION_\nImplementaci\xc3\xb3n de una lista enlazada en C\n_START_PARAGRAPH_\nLas listas enlazadas son t\xc3\xadpicamente construidas usando referencias junto con el tipo de dato record_NEWLINE_#include <stdio.h>   /* for printf */#include <stdlib.h>  /* for malloc */typedef struct ns {_NEWLINE_int data;_NEWLINE_struct ns *next;} node;node *list_add(node **p, int i) {_NEWLINE_    /* algunos compiladores no requieren un casting del valor del retorno para malloc  */_NEWLINE_    node *n = (node *)malloc(sizeof(node));_NEWLINE_    if (n == NULL)_NEWLINE_        return NULL;_NEWLINE_    n->next = *p;                                                                            _NEWLINE_    *p = n;_NEWLINE_    n->data = i;_NEWLINE_    return n;}void list_remove(node **p) { /* borrar cabeza*/_NEWLINE_    if (*p != NULL) {_NEWLINE_        node *n = *p;_NEWLINE_*p = (*p)->next;_NEWLINE_free(n);_NEWLINE_    }}node **list_search(node **n, int i) {_NEWLINE_    while (*n != NULL) {_NEWLINE_        if ((*n)->data == i) {_NEWLINE_            return n;_NEWLINE_        }_NEWLINE_        n = &(*n)->next;_NEWLINE_    }_NEWLINE_    return NULL;}void list_print(node *n) {_NEWLINE_    if (n == NULL) {_NEWLINE_        printf("lista esta vac\xc3\xada\\n");_NEWLINE_    }_NEWLINE_    while (n != NULL) {_NEWLINE_        printf("print %p %p %d\\n", n, n->next, n->data);_NEWLINE_        n = n->next;_NEWLINE_    }}int main(void) {_NEWLINE_    node *n = NULL;_NEWLINE__NEWLINE_    list_add(&n, 0); /* lista: 0 */_NEWLINE_    list_add(&n, 1); /* lista: 1 0 */_NEWLINE_    list_add(&n, 2); /* lista: 2 1 0 */_NEWLINE_    list_add(&n, 3); /* lista: 3 2 1 0 */_NEWLINE_    list_add(&n, 4); /* lista: 4 3 2 1 0 */_NEWLINE_    list_print(n);_NEWLINE_    list_remove(&n);            /* borrar primero(4) */_NEWLINE_    list_remove(&n->next);      /* borrar nuevo segundo (2) */_NEWLINE_    list_remove(list_search(&n, 1)); /* eliminar la celda que contiene el 1 (primera) */_NEWLINE_    list_remove(&n->next);      /* eliminar segundo nodo del final(0)*/_NEWLINE_    list_remove(&n);            /* eliminar ultimo nodo (3) */_NEWLINE_    list_print(n);_NEWLINE__NEWLINE_    return 0;}\n_START_SECTION_\nImplementaci\xc3\xb3n de una lista simplemente enlazada en C++ empleando clases\n_START_PARAGRAPH_\nListas simplemente enlazada con el empleo de punteros y direcciones de memoria. En este ejemplo empleamos dos clases una clase TElemento (nodo, item o elemento) y una clase TlistaSL (simplemente ligada, o simplemente enlazada). Cada una de ellas con sus atributos y m\xc3\xa9todos se\xc3\xb1alando como m\xc3\xa1s importante aInfo(informaci\xc3\xb3n del elemento) y aSeguinte (puntero al pr\xc3\xb3ximo elemento)._NEWLINE_//--Unit2.h-------------------------------------------------------------------------#ifndef Unit2H#define Unit2H#include <iostream.h>//---------------------------------------------------------------------------class TElemento{protected:_NEWLINE_    int aInfo;_NEWLINE_    TElemento *aSeguinte ;public:_NEWLINE_    TElemento(int pInfo){aInfo = pInfo; aSeguinte=NULL;};  //Construtor_NEWLINE_    ~TElemento(){};    //Destruidor_NEWLINE_          //Opera\xc3\xa7\xc3\xb5es_NEWLINE_    int LerInfo(){return  aInfo;};          //Ler_NEWLINE_    void EscInfo(int pInfo){aInfo = pInfo;};  //Escrever_NEWLINE_    TElemento *LerSeguinte(){return aSeguinte;};     //Ler_NEWLINE_    void EscSeguinte(TElemento *pSeguinte){aSeguinte = pSeguinte;};  //Escrever};class TListaSL{private:_NEWLINE_    TElemento *aPrimeiro;_NEWLINE_    int alongitude;public:           _NEWLINE_    TListaSL(){aPrimeiro = NULL; alongitude = 0;}; //Construtor_NEWLINE_    TListaSL(int pnovoelemento);                 //Construtor_NEWLINE_    ~TListaSL(); //Destruidor_NEWLINE_        //Opera\xc3\xa7\xc3\xb5es_NEWLINE_    int Longitud(){return alongitude;};_NEWLINE_    bool Vazia(){return !alongitude;};_NEWLINE_    void Adicionar(int pnovoelemento);_NEWLINE_    void Inserir(int pnovoelemento, int pIndice);_NEWLINE_    void Eliminar(int pIndice);_NEWLINE_    int Obter(int pIndice);_NEWLINE_    void Mostrar();};#endif//--Final Unit2.h-------------------------------------//--Unit2.cpp-------------------------------------------------------------------------#pragma hdrstop#include "Unit2.h"#include <vcl.h>#pragma argsused//---------------------------------------------------------------------------TListaSL::TListaSL(int pnovoelemento){_NEWLINE_    aPrimeiro = new TElemento(pnovoelemento);_NEWLINE_    alongitude = 1;}TListaSL::~TListaSL(){_NEWLINE_    TElemento *cursor;_NEWLINE_    while(aPrimeiro){_NEWLINE_        cursor = aPrimeiro;_NEWLINE_        cursor = aPrimeiro->LerSeguinte();_NEWLINE_        delete cursor;_NEWLINE_    }}void TListaSL::Adicionar(int pnovoelemento){_NEWLINE_    TElemento *novoNodo = new TElemento(pnovoelemento);_NEWLINE_    if (Vazia())_NEWLINE_        aPrimeiro = novoNodo;_NEWLINE_    else{_NEWLINE_        TElemento *cursor = aPrimeiro;_NEWLINE_        while(cursor->LerSeguinte())_NEWLINE_            cursor = cursor->LerSeguinte();_NEWLINE_        cursor->EscSeguinte(novoNodo);_NEWLINE_    }_NEWLINE_    alongitude++;}void  TListaSL:: Eliminar(int  pIndice  ){_NEWLINE_    if ((pIndice<0) || (pIndice>=alongitude))_NEWLINE_        printf("\\n Nao elimino. Posicao fora de rango");   // Posi\xc3\xa7ao fora a rango_NEWLINE_    TElemento *cursor = aPrimeiro;_NEWLINE_    if (pIndice != 0){_NEWLINE_        for (int i = 0; i < pIndice - 1; i++){_NEWLINE_            cursor = cursor->LerSeguinte();_NEWLINE_        }_NEWLINE_        TElemento *nodoEliminar = cursor->LerSeguinte(); //refer\xc3\xaancia ao nodo_NEWLINE_        cursor->EscSeguinte(nodoEliminar->LerSeguinte());  // tirar da lista_NEWLINE_        cursor = nodoEliminar;_NEWLINE_    }_NEWLINE_    else  // Eliminar o primeiro nodo_NEWLINE_        aPrimeiro= aPrimeiro->LerSeguinte();_NEWLINE_    delete cursor;_NEWLINE_    alongitude--;}void TListaSL::Inserir(int pnovoelemento, int pIndice){_NEWLINE_    if ((pIndice<0) || (pIndice >= alongitude))_NEWLINE_        printf("\\n Nao insiriou. Posicao fora de rango");      //Posi\xc3\xa7ao fora a rango_NEWLINE_    TElemento *novoNodo = new TElemento(pnovoelemento);_NEWLINE_    if (pIndice != 0){_NEWLINE_        TElemento *cursor = aPrimeiro;_NEWLINE_        int  contador = 1;_NEWLINE_        while (contador < pIndice){_NEWLINE_            cursor = cursor->LerSeguinte();  //Posicionar-se no nodo anterior_NEWLINE_            contador++;_NEWLINE_        }_NEWLINE_        novoNodo->EscSeguinte(cursor->LerSeguinte());_NEWLINE_        cursor->EscSeguinte(novoNodo);_NEWLINE_    }_NEWLINE_    else {_NEWLINE_        novoNodo->EscSeguinte(aPrimeiro);       //Inserir na primeira posi\xc3\xa7\xc3\xa3o_NEWLINE_        aPrimeiro = novoNodo;_NEWLINE_    }_NEWLINE_    alongitude++;}int TListaSL::Obter(int pIndice){_NEWLINE_    if ((pIndice<0) || (pIndice>=alongitude))_NEWLINE_        printf("\\n Nao posso mostrar. Posicao fora de rango");  //Posi\xc3\xa7ao fora a rango_NEWLINE_    TElemento *cursor = aPrimeiro;_NEWLINE_    for (int i = 0; i < pIndice; i++){ //Percorrer a lista at\xc3\xa9 chegar ao elemento  pIndice_NEWLINE_        cursor = cursor->LerSeguinte();_NEWLINE_    }_NEWLINE_    return cursor->LerInfo();}void TListaSL::Mostrar(){_NEWLINE_    TElemento *cursor = aPrimeiro;_NEWLINE_    for(int i = 0; i <= alongitude - 1; i++){_NEWLINE_        printf("%i ", cursor->LerInfo());_NEWLINE_        cursor = cursor->LerSeguinte();_NEWLINE_    }}/* Programa principal de la aplicaci\xc3\xb3n con algunas operaciones de prueba */int main(int argc, char* argv[]){_NEWLINE_    char espera;_NEWLINE_    TListaSL *Lista = new TListaSL();_NEWLINE_    Lista->Adicionar(0);_NEWLINE_    Lista->Adicionar(3);_NEWLINE_    Lista->Adicionar(2);_NEWLINE_    Lista->Adicionar(12);_NEWLINE_    Lista->Adicionar(6);_NEWLINE_    Lista->Adicionar(9);_NEWLINE_    Lista->Adicionar(7);_NEWLINE_    printf("\\n Lista de elementos: ");_NEWLINE_    Lista->Mostrar();_NEWLINE_    //printf("\\n%i", Lista->Obter(3));_NEWLINE_    Lista->Inserir(20,2);_NEWLINE_    printf("\\n Lista mas uno insertado: ");_NEWLINE_    Lista->Mostrar();_NEWLINE_    Lista->Eliminar(6);_NEWLINE_    printf("\\n Lista menos uno eliminado: ");_NEWLINE_    Lista->Mostrar();_NEWLINE_    cin >> espera;_NEWLINE_    return 0;};//---------------------------------------------------------------------------#pragma package(smart_init)\n_START_SECTION_\nImplementaci\xc3\xb3n de una lista enlazada en C++\n_START_PARAGRAPH_\n#include <iostream>    // Para cout#include <sstream>     // Utilizado para validar entradas del teclado#include <new>         // Utilizado para validad reservacion de memoria al utilizar el operator NEW.using namespace stdstruct camera_t {_NEWLINE_     int idcam;_NEWLINE_     string serial;_NEWLINE_     int idroom;_NEWLINE_     camera_t *next;_NEWLINE_ };//Insertar al principio de una lista requiere una funci\xc3\xb3n por separado. Se necesita actualizar PrimerNodo.void list_add(camera_t **node_cam){_NEWLINE_    camera_t *newnode = new (nothrow) camera_t;_NEWLINE_    if(newnode==NULL){_NEWLINE_        cout << "Error. No possible allocate memory to new node.";_NEWLINE_    }_NEWLINE_    else{_NEWLINE_        newnode->next = *node_cam;_NEWLINE_        *node_cam = newnode;_NEWLINE_        cout << "Hola";_NEWLINE_    }}//El recorrido en una lista enlazada es simple, empezamos por el primer nodo y pasamos al siguiente hasta// que la lista llegue al final.void list_print(camera_t *node_cam){_NEWLINE_    if (node_cam == NULL){_NEWLINE_        cout << "Lista vacia";_NEWLINE_    }_NEWLINE_    else{_NEWLINE_        while (node_cam!=NULL)_NEWLINE_        {_NEWLINE_            cout << "idcam: " << node_cam->idcam << "\\nName: " << node_cam->name << "\\nModel: " << node_cam->model;_NEWLINE_            cout << "\\nSerial: " << node_cam->serial << "\\nIdRoom: " << node_cam->idroom << "\\nNameRoom: " << node_cam->room;_NEWLINE_            cout << "\\n\\n";_NEWLINE_            node_cam = node_cam->next;_NEWLINE_        }_NEWLINE_    }}int main(void){_NEWLINE_     string mystr;_NEWLINE_     camera_t *node_cam = 0;_NEWLINE__NEWLINE_     cout << "Ingrese los datos de la camara." << endl;_NEWLINE_    _NEWLINE_     list_add(&node_cam);_NEWLINE__NEWLINE_     cout << "Indentificador de camara: 23";_NEWLINE_     node_cam->idcam = N_globalCamera;_NEWLINE_     node_cam->name = "PanSonyc";_NEWLINE_     cout << "Precione una tecla para regresar al menu principal.";_NEWLINE_     getline(cin,mystr);_NEWLINE__NEWLINE_    list_print(node_cam);}\n_START_SECTION_\nImplementaci\xc3\xb3n de una lista enlazada en Maude\n_START_PARAGRAPH_\nfmod LISTA-GENERICA {X\xc2\xa0:: TRIV} is_NEWLINE_    _NEWLINE_protecting NAT ._NEWLINE__NEWLINE_*** tipos_NEWLINE_    _NEWLINE_sorts ListaGenNV{X} ListaGen{X} ._NEWLINE_    _NEWLINE_subsort ListaGenNV{X} < ListaGen{X} ._NEWLINE__NEWLINE_*** generadores_NEWLINE_    _NEWLINE_op crear\xc2\xa0: -> ListaGen{X} [ctor] ._NEWLINE_    _NEWLINE_op cons\xc2\xa0: X$Elt ListaGen{X} -> ListaGenNV{X} [ctor] ._NEWLINE__NEWLINE_*** constructores_NEWLINE_    _NEWLINE_op _::_\xc2\xa0: ListaGen{X} ListaGen{X} -> ListaGen{X} [assoc id: crear ] . *** concatenaci\xc3\xb3n_NEWLINE_    _NEWLINE_op invertir\xc2\xa0: ListaGen{X} -> ListaGen{X} ._NEWLINE_    _NEWLINE_op resto    : ListaGenNV{X} -> ListaGen{X} ._NEWLINE__NEWLINE_*** selectores_NEWLINE_    _NEWLINE_op primero\xc2\xa0: ListaGenNV{X} -> X$Elt ._NEWLINE_    _NEWLINE_op esVacia?\xc2\xa0: ListaGen{X} -> Bool . _NEWLINE_    _NEWLINE_op longitud\xc2\xa0: ListaGen{X} -> Nat ._NEWLINE__NEWLINE_*** variables_NEWLINE_    _NEWLINE_vars L L1 L2\xc2\xa0: ListaGen{X} ._NEWLINE_    _NEWLINE_vars E E1 E2\xc2\xa0: X$Elt ._NEWLINE__NEWLINE_*** ecuaciones_NEWLINE_    _NEWLINE_eq esVacia?(crear) = true ._NEWLINE_eq esVacia?(cons(E, L)) = false ._NEWLINE__NEWLINE_    _NEWLINE_eq primero(cons(E, L)) = E ._NEWLINE_    _NEWLINE_eq resto(cons(E, L)) = L ._NEWLINE__NEWLINE_    _NEWLINE_eq longitud(crear) = 0 ._NEWLINE_eq longitud(cons(E, L)) = 1 + longitud(L) ._NEWLINE_ _NEWLINE_eq cons(E1, L1)\xc2\xa0:: cons(E2, L2) = cons(E1, L1\xc2\xa0:: cons(E2, L2)) ._NEWLINE__NEWLINE_    _NEWLINE_eq invertir(crear) = crear ._NEWLINE_eq invertir(cons(E, L)) = invertir(L)\xc2\xa0:: cons(E, crear) ._NEWLINE__NEWLINE__NEWLINE_endfm\n_START_SECTION_\nEjemplos de almacenamiento interno y externo\n_START_PARAGRAPH_\nSuponiendo que queremos crear una lista enlazada de familias y sus miembros. Usando almacenamiento interno, la estructura podr\xc3\xada ser como la siguiente:_NEWLINE_ record member { // miembro de una familia _NEWLINE_     member next_NEWLINE_     string firstName_NEWLINE_     integer age_NEWLINE_ }_NEWLINE_ record family { // // la propia familia _NEWLINE_     family next_NEWLINE_     string lastName_NEWLINE_     string address_NEWLINE_     member members // de la lista de miembros de la familia_NEWLINE_ }_NEWLINE_Para mostrar una lista completa de familias y sus miembros usando almacenamiento interno podr\xc3\xadamos escribir algo como esto:_NEWLINE_ aFamily\xc2\xa0:= Families // comienzo de la lista de familias_NEWLINE_ while aFamily \xe2\x89\xa0 null { // bucle a trav\xc3\xa9s de la lista de familias_NEWLINE_     print information about family_NEWLINE_     aMember\xc2\xa0:= aFamily.members // coger cabeza de esta lista de miembros de esta familia_NEWLINE_     while aMember \xe2\x89\xa0 null { //bucle para recorrer la lista de miembros_NEWLINE_         print information about member_NEWLINE_         aMember\xc2\xa0:= aMember.next_NEWLINE_     }_NEWLINE_     aFamily\xc2\xa0:= aFamily.next_NEWLINE_ }_NEWLINE_Usando almacenamiento externo, nosotros podr\xc3\xadamos crear las siguientes estructuras:_NEWLINE_ record node { // estructura gen\xc3\xa9rica de enlace_NEWLINE_     node next_NEWLINE_     pointer data // puntero gen\xc3\xa9rico del dato al nodo_NEWLINE_ }_NEWLINE_ record member { // estructura de una familia_NEWLINE_     string firstName_NEWLINE_     integer age_NEWLINE_ }_NEWLINE_ record family { // estructura de una familia_NEWLINE_     string lastName_NEWLINE_     string address_NEWLINE_     node members // cabeza de la lista de miembros de esta familia_NEWLINE_ }_NEWLINE_Para mostrar una lista completa de familias y sus miembros usando almacenamiento externo, podr\xc3\xadamos escribir:_NEWLINE_ famNode\xc2\xa0:= Families // comienzo de la cabeza de una lista de familias_NEWLINE_ while famNode \xe2\x89\xa0 null { // bucle de lista de familias_NEWLINE_     aFamily = (family) famNode.data // extraer familia del nodo_NEWLINE_     print information about family_NEWLINE_     memNode\xc2\xa0:= aFamily.members // coger lista de miembros de familia_NEWLINE_     while memNode \xe2\x89\xa0 null { bucle de lista de miembros_NEWLINE_         aMember\xc2\xa0:= (member) memNode.data // extraer miembro del nodo_NEWLINE_         print information about member_NEWLINE_         memNode\xc2\xa0:= memNode.next_NEWLINE_     }_NEWLINE_     famNode\xc2\xa0:= famNode.next_NEWLINE_ }'