I'm making a class that simulates java LinkedLists, because handling LinkedLists is different from arrays, I'm stuck with a couple of methods.
In the code that I leave below the methods that are a bit incomplete, I put comments so that it is understood what it intends to do. Apart from the help with these methods, I also need, as far as possible, that they are as well commented as possible to be able to understand them as well as possible.
LinkedList class
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package ds;
import java.util.Iterator;
/**
*
* @author Pillado
* @param <T>
*/
@SuppressWarnings("unchecked")
public class LinkedList<T> implements Iterable<T>{
//Hecho por Fran
private ListNode<T> head;
private int len;
public int size() { return this.len; }
public void add(T data) {
ListNode<T> newNode = new ListNode<T>(data);
newNode.setNext(this.head);
this.head = newNode;
++len;
}
public T get(int index) {
if(index<0 || index>=this.len) throw new IndexOutOfBoundsException("Indice fuera de rango: " + index);
if(index==0) return head.getData(); // si queremos el primero de la lista
ListNode<T> node = head; // si no, empezamos por el primero...
while(index-->0) node = node.getNext(); // saltamos de nodo en nodo tantas veces como index
return node.getData();
}
//Hecho por Julio
@Override
public Iterator<T> iterator(){
return new Iterator(){
@SuppressWarnings("FieldMayBeFinal")
private int p = 0;
@Override
public boolean hasNext() {
return (p < len);
}
@Override
public Object next() {
return null;
//return data[p++];//modificar
}
};
}
/**
* Vacía el LinkedList
*/
public void clear(){
for (int i = 0; i < this.len; i++) {
this.remove(i);
}
}
/**
* Inserta el dato en la posición indicada
* @param index indice del array
* @param data dato a almacenar
* @throws IndexOutOfBoundsException indice fuera de rango
*/
public void add(int index, T data){
if(index<0 || index>=this.len) throw new IndexOutOfBoundsException("Indice fuera de rango: " + index);
this.len++;
}
/**
* Modifica el valor en la posición indicada con el nuevo dato
* @param index indice del array
* @param data dato a almacenar
* @throws IndexOutOfBoundsException indice fuera de rango
*/
public void set(int index, T data){
if(index<0 || index>=this.len) throw new IndexOutOfBoundsException("Indice fuera de rango: " + index);
}
/**
* Devuelve el dato de la posición indicada y la elimina del array
* @param index indice a eliminar
* @return dato que se ha eliminado del array
* @throws IndexOutOfBoundsException indice fuera de rango
*/
public T remove(int index){
if(index<0 || index>=this.len) throw new IndexOutOfBoundsException("Indice fuera de rango: " + index);
T data = null;
this.len--;
return data;
}
/**
* Elimina el dato del array. Devuelve un valor indicando si la operación tuvo éxito o no
* @param data dato a eliminar
* @return Booleano, true si se ha eliminado
*/
public boolean delete(T data){
int index = indexOf(data);
if (index != -1) { remove(index); }
return (index != -1);
}
/**
* Devuelve la posición en la que se encuentra dato indicado
* @param data dato a buscar en el array
* @return Indice donde esta la cadena, -1 si no encuentra
*/
public int indexOf(T data){
return 0;
}
}
ListNode class
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package ds;
/**
*
* @author Pillado
* @param <T>
*/
public class ListNode<T> {
private T data;
private ListNode next;
ListNode(T data) { this.data = (T) data; }
T getData() { return this.data; }
ListNode getNext() { return this.next; }
void setNext(ListNode<T> nextNode) { this.next = nextNode; }
}
I am aware that this time I am asking too much with this problem but I am quite stuck with it. Thanks for the help.
-- MODIFICATION --
The problem I'm having deals with handling nodes. When you have to add a node you have to modify the corresponding references to the nodes, when it comes to removing a node you also have to modify the references and this is why I still don't know how to do it.
The methods in question are in the LinkedList class and are as follows:
public void add(int index, T data){}
public void set(int index, T data){}
public T remove(int index)
There is also an iterator where I don't really know how to override the next method.
-- MODIFICATION --
I leave some images that show the results after using the set and add method
-- MODIFICATION --
Below I leave three screenshots of how I have implemented the set and add methods
Method 1
We must follow the following algorithm:
1.- We will create a new node where we will store the object to which the parameter points
data
.2.- We go through the linked list until we find the node that is in the given position.
3.- We link the next field of the new node with the node to which the auxiliary variable points.
4.- If the position is different from
0
, it is because the auxiliary variable points to an intermediate or last node. If this condition is met, we must link the old node to the new node.5.- If step 4 is not fulfilled, it is because the auxiliary variable points to the first node, therefore, we must update the reference
head
, since the new node will be the first node .6.- We increase the variable
len
.Java code:
Verification:
Imagine that the linked list has the following elements:
We will now use our algorithm to insert the number
25
at position2
.1.- We go through the list until we find the node with the given position:
2.- We link the new node with which the reference points
aux
:We then link the old node (the one before the node pointed to
aux
) with the new node:Clever! We have inserted the number
20
at position2
.What would happen if we insert the number
25
at position0
?We follow the steps:
1.- We go through the list until we find the node with the given position:
2.- Enlazamos el nuevo nodo con el que apunte la referencia
aux
y actualizamos la referenciahead
:El último paso se cancela porque no hay un nodo anterior.
Método 2
La implementación de este método es sencillo, por esa razón no incluiré una comprobación ni algoritmo.
Código en Java:
Nota: El método
setData
debe estar definido en la clase genéricaListNode
.Método 3
Su algoritmo es:
1.- Recorremos la lista hasta encontrar el nodo con la posición dada.
2.- Verificamos si la variable auxiliar coincide con el primer nodo, si se cumple la condición, debemos actualizar la referencia
head
, ya que apuntará al nodo al que apunte el campo siguiente del nodo al que apunteaux
.3.- Si la variable
aux
coincide con el último nodo, debemos asignar unnull
al campo siguiente del anterior nodo. De esto depende que la lista enlazada tenga un fin.4.- Si la variable
aux
coincide con un nodo intermedio, debemos enlazar el campo siguiente del anterior nodo con el nodo al que apunte el campo siguiente del nodo al que apunteaux
.Código en Java:
Para poder recorrer la lista enlazada necesitas de una referencia auxiliar. Por esa razón debemos agregarla como un atributo en la clase
LinkedList
:Posteriormente, debemos asignar el contenido al que apunte
head
enauxLK
. Esta asignación se la hará en el métodoiterator()
.In the method
hasNext()
we only have to add a condition in which it tells us if the auxiliary variable reachednull
(it tells us the end of the linked list) and in the methodnext()
the object of type must be returnedT
, for that reason I made the anonymous class to be genericExample: