de um codigo. Esses estados podem ser alterados em varios momentos de acordo com as funcoes que tratam esse objeto. A implementacao de objetos como maquinas de estado, auxilia na reducao dos custos de varios tipos de operacoes que equivale a economia de tempo de execucao e melhora o desempenho de aplicativos.Veja essa implementacao de uma lista e suas operacoes alterar, pesquisar, inserir e apagar itens da lista onde a nocao de efeito colateral restrito ao estado concreto nao e usado:// Listaclass IntList {private static class Node {...}private Node firstElement;private int nElements;public IntList( ) { }//Operacoes de IntList...}// Metodo para alterar valor de um item da lista com custo O(n)public void changeValue(int i,int v)throws E1{Node e; int j;if (i<1 i="">nElements)throw new IndexError();e = getAddress(i);e.info = v;}// Metodo para pesquisar item na lista com custo O(n)public int search(int v) {Node e; int j;if (empty( )) then return 0;for (j = 1 , e = firstElement ; j&lt;=nElements; j++,e = e.right) {if (v == e.value) return j;}return 0;}// Metodo para inserir item na lista com custo O(n)public void insert(int i, int v) throws E1 {Node previous, node; int j;if (i<0 i="">nElements)throw new IndexError();node = new Node(v);if (i == 0) {node.right= firstElement;firstElement = node;} else {previous = getAddress(i);node.right =previous.right;previous.right =node;}nElements++;}// Metodo para deletar um item da lista com custo O(n)public void delete(int i) throws IndexError {Node previous, toBeDeleted;if (i<1 i="">nElements)throw new IndexError();if (i == 1) {firstElement = firstElement.right;}else {previous = getAddresss(i-1);toBeDeleted = previous.right;previous.right = toBeDeleted.right;}nb_elements--;}// Uso de IntListclass User {public static void main(String[ ] a) {LinkedList q;int k, v1 = 1, v2 = 2, v3 = 3, v4 = 4, int n = 5; ...;k = q.search(v1);v4 = q.value(k);q.insert(n, v2);q.changeValue(n,v3);q.delete(n);................}}A lista apresentada possui as operacoes basicas para o funcionamento de uma lista, porem, suas operacoes possuem o custo O(n), pois, em todas as operacoes a lista e percorrida desde o inicio. Esse tipo de implementacao nao poupa tempo de execucao. Essa lista poderia ser reimplementada de modo que suas operacoes tivessem um menor custo. A saida seria implementar essa lista como uma maquina de estados.Na implementacao dessa lista como uma maquina de estados, sera utilizada a nocao de nodo corrente para que as operacoes sejam mais eficientes. Essa nocao sera obtida pela construcao do nodo ativo que armazena informacoes de acordo com as ultimas operacoes realizadas. E todas as operacoes sao definidas em funcao do nodo corrente.Nas Figuras 1 e 2, podemos verificar o funcionamento da nova lista de acordo com o estado abstrato, ou seja, o estado percebido pelo usuario e de acordo com o estado concreto, ou seja, o estado definido pela implementacao do objeto. Na percepcao do usuario, o tempo de execucao sera melhorado e ele notara um retorno mais rapido durante as execucoes. Na demonstracao do estado concreto, podemos verificar como funcionarao as operacoes de acordo coma existencia do nodo active.FIG. 1 Vista do Estado Abstrato do ADT. Fonte: Bigonha.FIG. 2 Vista do Estado Concreto do ADT. Fonte: Bigonha.Vejamos a nova implementacao da lista:class IntList {private static class Node {int value; Node right;Node(int value){this.value = value;}}private int nElements, position;private Node firstElement;private