Ingeniero

Clase Lista C++ Estándar

Agustín J. González Versión original de Kip Irvine ElO326 Seminario II 2do. Sem.2001
1

Estructura de Datos Lista (List)
• Una estructura de datos Lista esuna secuencia conectada de nodes, cada uno de los cuales contiene algún dato. • Hay un nodo al comienzo llamado la cabeza o frente (head o front). • Hay un nodo de término llamado la colao atrás (tail o back). • Una Lista sólo puede ser recorrida en secuencia, usualmente hacia atrás o adelante. • Hay varias formas de implementar una lista, como se muestra a continuación...Lista Simplemente Enlazada
Una lista simplemente enlazada tiene punteros conectando los nodos sólo en dirección hacia la cola. Cada uno de los nodos contiene un string en este ejemplo:Fred Jim Anne Susan

(head)

(tail)

Lista Doblemente Enlazada
Una lista doblemente enlazada tiene punteros conectando los nodos en ambas direcciones. Esto permite recorrer lalista en ambas direcciones:

Fred

Jim

Anne

Susan

(head)

(tail)

Las clase List en la biblioteca estándar una esta implementación.

Clase List Estándar C++
• La claselist es una clase template (plantilla) en la Biblioteca estándar C++* • Podemos crear listas que contengan cualquier tipo de objeto. • Las clases list y vector comparten muchas operaciones,incluyendo: push_back(), pop_back(), begin(), end(), size(), y empty() • EL operador sub-índice ( [ ] )no puede ser usado con listas.
* Esta no es exactamente la misma que la "StandardTemplate Library" (STL) actualmente mantenida por Silicon Graphics Corporation (www.sgi.com), pero compatible en la gran mayoría de los casos.

Agregar y remover nodos
El siguiente códigocrea una lista, agrega cuatro nodos, y remueve un nodo:
#include list staff; staff.push_back("Fred"); staff.push_back("Jim"); staff.push_back("Anne"); staff.push_back("Susan"); cout