Ver índice de contenidos del libro

16.7. Resumen

  • Un tipo abstracto de datos (TAD) es un tipo de datos que está definido por las operaciones que contiene y cómo se comportan (su interfaz), no por la forma en la que esas operaciones están implementadas.
  • Una lista enlazada es una implementación del TAD lista. Se trata de una lista compuesta por nodos, en la que cada nodo contiene un dato y una referencia al nodo que le sigue.
  • En las listas enlazadas, es barato insertar o eliminar elementos, ya que simplemente se deben alterar un par de referencias; pero es caro acceder a un elemento en particular, ya que es necesario pasar por todos los anteriores para llegar a él.
  • Tanto al insertar como al remover elementos de una lista enlazada, se utiliza la técnica de máquina de parejas, mediante la cual se va recorriendo la lista hasta encontrar el lugar apropiado donde operar con las referencias.
  • Una lista doblemente enlazada es aquella cuyos nodos además del dato contienen una referencia al nodo anterior y otra al nodo siguiente, de modo que se la puede recorrer en ambos sentidos.
  • Una lista circular es aquella en la que el último nodo contiene una referencia al primero, y puede ser recorrida infinitamente.
  • Un iterador es un objeto que permite recorrer uno a uno los elementos de una secuencia.
Copyright (c) 2011-2014 Rosita Wachenchauzer, Margarita Manterola, Maximiliano Curia, Marcos Medrano, Nicolás Paez. La copia y redistribución de esta página se permite bajo los términos de la licencia Creative Commons Atribución - Compartir Obras Derivadas Igual 3.0 siempre que se conserve esta nota de copyright.