En esta ocasión vengo a mostrarles una implementación propia de la clase LinkedList, esta clase es una coleccion de elementos con una utilidad equivalente a la de ArrayList pero con una estructura distinta.
La principal diferencia es su modo de guardar los elementos; ArrayList lo hace en un array mientras LinkedList lo hace mediante una estructura de objetos encadenados(nodos) por links o instancias.
ArrayList. se puede representar en casillas, donde cada una de ellas es un espacio de memoria destinado a un objeto
LinkedList. los objetos están unidos por conexiones, cada elemento tiene una conexión al objeto siguiente
:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
Nodo.
Los objetos que almacenan los datos y links se llaman nodos, como cada nodo tiene una conexión a su siguiente solo seria necesario saber cual es el primer nodo, sin embargo se pueden poner dos links en cada nodo, uno para el nodo siguiente y uno para el anterior.
acá el código del nodo:
[color=#000000] private class Node<E> {
private E data; // dato de cualquier tipo
private Node<E> after; //link al siguiente nodo
private Node<E> before; //link al anterior nodo
// Getters y Setters
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public Node<E> getAfter() {
return after;
}
public void setAfter(Node<E> link) {
this.after = link;
}
public Node<E> getBefore() {
return before;
}
public void setBefore(Node<E> link) {
this.before = link;
}
// el constructor inicializa las variables con los valores recibidos
public Node(E data, Node<E> after, Node<E> before) {
this.data = data;
this.after = after;
this.before = before;
}
}
[/color]
la clase es privada puesto que se encuentra en la clase LinkedList y solo ella la utilizara
La <E> significa que es de tipo genérico, es decir que se puede almacenar cualquier tipo de dato(int, char, etc).
Existen tres tipos de encadenamiento: el simplemente encadenado(cada nodo tiene un link al siguiente elemento), el doblemente encadenado(link al siguiente y al anterior) y el circular (no hay ni primer ni ultimo nodo, todos están encadenados).
En mi caso utilice el doblemente encadenado, en este el primer nodo no tiene link al anterior y el ultimo no tiene link al siguiente.
:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
Atributos
Serian basicamente 3:
-> una referencia al primer nodo.
-> una referencia al ultimo nodo.
-> un entero con la longitud.
[color=#000000] private int size;
private Node<E> head;
private Node<E> tail;
[/color]
:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
Metodos
repito, esta es una implementación propia, así que no son los mismos métodos del API
-> Constructor:
[color=#000000] public MyLinkedList() {
this.clear();
}
[/color]
llama a un método clear que inicializa las variables.
-> clear
[color=#000000]
public void clear() {
head = new Node<E>(null, tail, null);
tail = new Node<E>(null, null, head);
size = 0;
}
[/color]
inicializa los dos nodos dando a la cabeza un link a la cola y viceversa, también asigna al tama~o el valor de 0.
-> size
[color=#000000]
public int size() {
return size;
}
[/color]
simplemente retorna el valor del atributo size
-> isEmpty
[color=#000000]
public boolean isEmpy() {
return (size == 0);
}
[/color]
dice si la lista esta vacía
-> contains
[color=#000000]public boolean contains(E item) {
boolean contains = false;
Node<E> temp = head;
for (int i = 0; i < size; i++) {
temp = temp.getAfter(); // el nodo se iguala a su siguiente
if (temp.getData() == item)
contains = true;
}
return contains;
}
[/color]
recive un elemento, crea un nodo temporal al que se iguala al primer nodo(cabeza) y se hace una iteración comparando el elemento recibido con el que contiene el nodo temporal.
-> add
[color=#000000]
public void add(E item) {
Node<E> newNode = new Node<E>(item, tail, tail.getBefore()); // crea un nodo con el dato recivido
tail.getBefore().setAfter(newNode); // el nuevo nodo sera el link siguiente al que era el ultimo nodo
tail.setBefore(newNode);
size++;
}
[/color]
crea un nodo con la información recibida y lo pone al final de la lista
-> getNode
[color=#000000]public Node<E> getNode(int index) throws Exception {
Node<E> temp;
if (index < 1 || index > size)
throw new Exception("Indice fuera de rango");
else {
temp = head.getAfter();
for (int i = 1; i < index; i++) {
temp = temp.getAfter();
}
}
return temp;
}[/color]
devuelve el nodo de la posición recibida, igualando el nodo temporal a su siguiente tantas veces como el índice lo indique.
-> get
[color=#000000]
public E get(int index) throws Exception {
return this.getNode(index).getData();
}
[/color]
retorna el dato del nodo en la posición recibida.
-> delete
[color=#000000]
public E delete(Node<E> nodeR) {
nodeR.getAfter().setBefore(nodeR.getBefore());
nodeR.getBefore().setAfter(nodeR.getAfter());
size--;
return nodeR.getData();
}
[/color]
remueve de la lista el nodo recibido y retorna el valor que contenía. Básicamente lo que hace es cambiar los links del anterior y del siguiente nodo para que lo omitan, el dibujo lo explica mejor:
->set
[color=#000000]
public void set(int index, E item) throws Exception {
this.getNode(index).setData(item);
}
[/color]
simplemente iguala el dato del nodo en la posición recibida por el valor entrante.
Esos son los métodos mas básicos, no pongo mas porque me da pereza
:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
si alguno quiere el .java con otros 12 métodos me manda un mp, gracias por pasar!.