Estructuras de datos lineales

Tipos de datos tienen operaciones ej: int soporta + - / * el tipo byte soporta &&, ||, >>, <<

• Tipos primitivos: Datos que trae el lenguaje. int, String, float...
• Tipos referencia: se extiende el lenguaje creando un tipo de dato, una descripcion de lo que tiene la memoria dentro
• TDA: Tipos de Datos Abstractos-->tienen fundamento matematico
  • Tipos de TDA: listas enlazadas(linked list), soporta add, addFirst, addLast, remove, removeLast

---

• Tipos de listas:
  Array:

  • Conexion finita y bien definida de elementos de x tipo
  • Cada elemento esta contiguo al otro en la memoria
  • int[] a=new int[8 /*capacidad del array*/]------> en la meoria va a haber 8 espacios seguidos del Array
  • tiene rapida lectura y escritura, pero lenta incercion en desorden y no puede crecer ni decrecer
  • se recorre :for(int i=i;i<a.lenght;i++){}
  • o: for(int i: a){}//for each

  Matrices:

  • es un array multidimencional
  • filas y columnas
  • se crea: int[][] m = new int [2][2]
  • se recorre: for(int i=0;i<a.length;i++){ for(int j=0;j<a[i].length;j++){}}

  Lista Enlazada:

  • estructura de datos dinamica
  • crece o decrece por demanda
  • no esta contiguua en la memoria
  • lista secuencial de elementos
  • cada elemento es un nodo
  • un nodo es un obj compuesto por dos elementos:
    el valor que guarda o dato
    referencia al siguiente elemento de la lista
    la lista tiene una referencia al primer elemento
    la referencia al primer elemento debe protegerse
    el ultimo nodo apunta a null
    codigo:

package list

class nodo{
private int dato;
private nodo next;
public nodo(int dato){
this.dato=dato;
this.next=null;
}
}
public class list{
private nodo first;
public list(){
this.first=null;
}
}

public void addLast(int e){
if(this.first==null){
this.first=new nodo(e);
}else{
nodo current=this.first
while(current.next!=null){
current=current.next;
}
current.next=new nodo(e)
}
}
main:
list l=new list();
l.addLast(1);
l.addLast(2);

---

Listas Simples

listas simples(una sola referencia) ...
agregar al inicio
public void addFirst(int element){
if(this.first==null){
this.first=new Nodo(element)
}else{
Node temp=new Node(element);
temp.next=this.first;
this.first=temp
}
}

Borrar al inicio
public void deletefirst(){
if(this.first==null){
return;
}else{
//this.first=this.first.next;
Node temp=this.first; //iguala a first
this.first=temp.next; //mueve a first
temp.next=null; //elimina la referencia del primer elemento
}
}

Eliminar al final

public void deletelast(){
if(this.fist!=null){
if(this.first.next==null){
this.first=null;
}else{
node temp=this.first
while(temp.next.next!=null){
temp=temp.next;
}
}temp.next=null; }
}

Listas Dobles

• Se puede navegar hacia atras
• cada nodo tiene 2 referencias: next y previous
  public void addFirst(int element){
  if(this.first==null){
  this.first=new Node(element);
  }else{
  node n =new nodo(element);
  n.next=this.first;
  this.first.previous=n;
  this.first=n
  }
  }
  Listas circulares
  Es una lista en la que cada nodo tiene un sucesor y un predecesor
  el sucesor del "ultimo" es el "primero"
  el predecesor del "primero" es el "ultimo"
  iniciando en cualquier nodo, se puede recorrer la lista completa
  el "first" apunta al "ultio" elemento
  son utiles cunado se necesita acceder rapidamente al inicio/final de la lista
  el recorrido se detiene cuando el current es igual al first

Pilas
conjunto de elementos colocados uno sobre otro
unicamente se puede acceder el ultimo elemento insertado
siempre se incerta al final(el final se llama tope)
naturaleza LIFO (last input, first output)
tiene 3 operaciones:
-push:insertar un elemento en el tope
-pop: eliminar un elemento en el tope
-peek: ver el tope
se puede implementar con listas o arrays

class Stack{
private int maxsize;
private Object[] stackArray;
private int topPosition=-1;
void push(Object new Object){
if(topPosition<maxSize){
stackArray[++topPosition]==new Object;
}
}
object pop(){
return StackArray[topPosition--];
}
}

---