Data Structures: Linked Lists and Array Implementations in Java

Posted on Jan 31, 2025 in Design

Singly Linked List Implementation

The following code demonstrates a singly linked list implementation in Java:

public class ListaUnNexo {
    private Nodo first;
    private Nodo last;

    public ListaUnNexo() {
        first = null;
        last = null;
    }

    public void ingresar(int d) {
        Nodo curr = new Nodo(d);
        curr.setNext(first);
        first = curr;
    }

    public void ingresarOrdenado(int d) {
        Nodo nuevo = new Nodo(d);
        Nodo previo = null;
        Nodo curr = first;
        while (curr != null && d > curr.getDato()) {
            previo = curr;
            curr = curr.getNext();
        }
        if (previo == null) {
            first = nuevo;
        } else {
            previo.setNext(nuevo);
        }
        nuevo.setNext(curr);
    }

    public Persona buscar(int d) {
        Nodo curr = first;
        while (curr != null && curr.getDato() != d) {
            curr = curr.getNext();
        }
        if (curr != null) {
            return curr.getPersona;
        } else {
            return null;
        }
    }

    public boolean eliminar(int d) {
        Nodo curr = first;
        Nodo prev = first;
        while (curr != null && curr.getDato() != d) {
            prev = curr;
            curr = curr.getNext();
        }
        if (curr != null) {
            if (curr == first) {
                first = first.getNext();
            } else {
                prev.setNext(curr.getNext());
            }
        }
        return true;
    }
}

Doubly Linked List Implementation

Here’s an implementation of a doubly linked list:

public class ListaDosNexos {
    private Nodo first;
    private Nodo last;

    public ListaDosNexos() {
        first = null;
        last = null;
    }

    public Nodo getFirst() {
        return first;
    }

    public void setFirst(Nodo first) {
        this.first = first;
    }

    public Nodo getLast() {
        return last;
    }

    public void setLast(Nodo last) {
        this.last = last;
    }

    public void insertarPrincipio(int d) {
        Nodo curr = new Nodo(d);
        if (first == null) {
            last = curr;
        } else {
            first.setPrev(curr);
        }
        curr.setNext(first);
        first = curr;
    }

    public void insertarOrdenado(int dato) {
        Nodo nuevo = new Nodo(dato);
        Nodo prev = null;
        Nodo actual = first;
        while (actual != null && dato > actual.getDato()) {
            prev = actual;
            actual = actual.getNext();
        }
        if (prev == null) {
            first = nuevo;
        } else {
            prev.setNext(nuevo);
            nuevo.setPrev(prev);
        }
        nuevo.setNext(actual);
        if (actual != null) {
            actual.setPrev(nuevo);
        } else {
            last = nuevo;
        }
    }

    public Persona buscar(int d) {
        Nodo curr = first;
        while (curr != null && curr.getDato() != d) {
            curr = curr.getNext();
        }
        if (curr != null) {
            return curr.getPersona;
        } else {
            return null;
        }
    }

    public boolean eliminar(int d) {
        Nodo curr = first;
        while (curr != null && curr.getDato() != d) {
            curr = curr.getNext();
        }
        if (curr != null) {
            if (curr == first) {
                first = first.getNext();
            } else {
                curr.getPrev().setNext(curr.getNext());
            }
            if (curr == last) {
                last = last.getPrev();
            } else {
                curr.getNext().setPrev(curr.getPrev());
            }
            return true;
        } else {
            return false;
        }
    }
}

Circular Singly Linked List

Implementation of a circular singly linked list:

public class ListaCircularUnNexo {
    private Nodo first;

    public ListaCircularUnNexo() {
        first = null;
    }

    public void ingresar(int d) {
        Nodo curr = new Nodo(d);
        if (first == null) {
            first = curr;
        } else {
            Nodo prev = first;
            while (prev.getNext() != first) {
                prev = prev.getNext();
            }
            prev.setNext(curr);
        }
        curr.setNext(first);
    }

    public boolean eliminar(int d) {
        Nodo curr = first;
        Nodo prev = first;
        if (first != null) {
            while (curr.getNext() != first && curr.getDato() != d) {
                prev = curr;
                curr = curr.getNext();
            }
            Nodo ult = first;
            while (ult.getNext() != first) {
                ult = ult.getNext();
            }
            if (curr.getDato() == d) {
                if (first.getNext() == first) {
                    first = null;
                } else {
                    if (curr == first) {
                        first = first.getNext();
                        ult.setNext(first);
                    } else {
                        prev.setNext(curr.getNext());
                    }
                }
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

    public Nodo getFirst() {
        return first;
    }
}

Circular Doubly Linked List

Implementation of a circular doubly linked list:

public class ListaCircularDobleNexo {
    private Nodo first;
    private Nodo last;

    public ListaCircularDobleNexo() {
        first = null;
        last = null;
    }

    public boolean eliminar(int d) {
        Nodo curr = first;
        while (curr.getNext() != first && curr.getDato() != d) {
            curr = curr.getNext();
        }
        if (curr.getDato() == d) {
            if (first == last) {
                first = null;
                last = null;
            } else {
                if (curr == first) {
                    first = first.getNext();
                    first.setPrev(last);
                    first.setNext(first);
                } else {
                    curr.getPrev().setNext(curr.getNext());
                }
                if (curr == last) {
                    last = last.getPrev();
                    first.setPrev(last);
                    last.setNext(last);
                } else {
                    curr.getNext().setPrev(curr.getPrev());
                }
            return true;
            } 
        } else {
            return false;
        }
    }

    public boolean buscar(int d) {
        Nodo curr = first;
        if (first != null) {
            while (curr.getNext() != first && curr.getDato() != d) {
                curr = curr.getNext();
            }
            if (curr.getDato() == d) {
                System.out.println("Dato encontrado");
                return true;
            } else {
                System.out.println("dato no encontrado");
                return false;
            }
        } else {
            return false;
        }
    }

    public void ingresar(int d) {
        Nodo curr = new Nodo(d);
        if (first == null) {
            first = curr;
            last = curr;
        } else {
            last.setNext(curr);
            curr.setPrev(last);
            last = curr;
        }
        last.setNext(first);
        first.setPrev(last);
    }
}

Array-Based List of Clients

Implementation of a list of clients using an array:

public class ListaClientes {
    private Cliente[] lcl;
    private int cantClientes;
    private int max;

    public ListaClientes(int max) {
        lcl = new Cliente[max];
        cantClientes = 0;
        this.max = max;
    }

    public Cliente getCliente(int i) {
        if (i >= 0 && i < cantClientes) {
            return lcl[i];
        } else {
            return null;
        }
    }

    public boolean IngresarCliente(Cliente c) {
        if (cantClientes < max) {
            lcl[cantClientes] = c;
            cantClientes++;
            return true;
        }
        return false;
    }

    public Cliente BuscarClientePorCodigo(int codigo) {
        int i;
        for (i = 0; i < cantClientes; i++) {
            Cliente c = lcl[i];
            if (c.getCodigoCliente() == codigo) {
                break;
            }
        }
        if (i == cantClientes) {
            return null;
        } else {
            return lcl[i];
        }
    }

    public boolean EliminarClientePorCodigo(int codigo) {
        int i;
        for (i = 0; i < cantClientes; i++) {
            Cliente c = lcl[i];
            if (c.getCodigoCliente() == codigo) {
                break;
            }
        }
        if (i == cantClientes) {
            return false;
        } else {
            for (int j = i; j < cantClientes - 1; j++) {
                lcl[j] = lcl[j + 1];
            }
            cantClientes--;
            return true;
        }
    }

    public int getCantClientes() {
        return cantClientes;
    }

    public void setCantClientes(int cantClientes) {
        this.cantClientes = cantClientes;
    }

    public int getMax() {
        return max;
    }
}

Linked List of Subjects

Implementation of a list of subjects using a LinkedList:

import java.util.LinkedList;
import java.util.Iterator;

public class ListaAsignaturas {
    private LinkedList la;

    public ListaAsignaturas() {
        this.la = new LinkedList();
    }

    public boolean eliminarAsignatura(Asignatura asignatura) {
        la.remove(asignatura);
        return la.remove(asignatura);
    }

    public boolean agregarAsignatura(Asignatura asignatura) {
        la.add(asignatura);
        return la.add(asignatura);
    }

    public Asignatura buscarAsignatura(int codAsig) {
        Iterator iter = la.iterator();
        Asignatura retorna = null;
        while (iter.hasNext()) {
            Asignatura aux = (Asignatura) iter.next();
            if (aux.getCodigo() == codAsig) {
                retorna = aux;
            }
        }
        if (retorna != null) {
            return retorna;
        } else {
            return null;
        }
    }
}

Playing with ArrayList

Example of using ArrayList:

import java.util.ArrayList;
import java.util.Iterator;

public class Main {
    public static void jugarConArrayList() {
        ArrayList lista = new ArrayList<>();
        lista.add(5);
        Iterator iter = lista.iterator();
        while (iter.hasNext()) {
            int x = (int) iter.next();
            System.out.println(x);
        }
        iter = lista.iterator();
        int b = (int) iter.next();
        System.out.println("b: " + b);
        iter.next();
        iter.remove();
        while (iter.hasNext()) {
            System.out.println(">> " + iter.next());
        }
    }
}

Playing with LinkedList

Example of using LinkedList:

import java.util.LinkedList;
import java.util.Iterator;

public class Main {
    public static void jugarConLinkedList() {
        LinkedList lista = new LinkedList();
        lista.add("naranja");
        Iterator iter = lista.iterator();
        while (iter.hasNext()) {
            String dato = (String) iter.next();
            System.out.println(dato);
        }
        iter = lista.iterator();
        iter.next();
        iter.next();
        iter.remove();
        iter = lista.iterator();
        while (iter.hasNext()) {
            String dato = (String) iter.next();
            System.out.println(">> " + dato);
        }
    }
}

Node Class

Definition of the Node class:

public class Nodo {
    private int dato;
    private Nodo next;
    private Nodo prev;

    public Nodo(int dato) {
        this.dato = dato;
        next = null;
        prev = null;
    }

    public int getDato() {
        return dato;
    }

    public void setDato(int dato) {
        this.dato = dato;
    }

    public Nodo getNext() {
        return next;
    }

    public void setNext(Nodo next) {
        this.next = next;
    }

    public Nodo getPrev() {
        return prev;
    }

    public void setPrev(Nodo prev) {
        this.prev = prev;
    }
}

Kbot Class

Implementation of a Kbot class for pathfinding:

public class Kbot {
    private boolean encontrado;
    private final int UP = 1;
    private final int RIGHT = 2;
    private final int DOWN = 3;
    private final int LEFT = 4;
    private final int DEAD_END = 5;

    public String getCaminoSeguro(char[][] campoMinado, int xIni, int yIni) {
        String camino = encontrarCamino(campoMinado, xIni, yIni);
        campoMinado[xIni][yIni] = 'E';
        return camino;
    }

    private String encontrarCamino(char[][] campoMinado, int i, int j) {
        int direccion = UP;
        char orig;
        String camino = "";
        if (i >= 0 && j >= 0 && i < campoMinado.length && j < campoMinado[i].length) {
            switch (campoMinado[i][j]) {
                case 'P':
                case 'M':
                    encontrado = false;
                    break;
                case 'D':
                    camino = "D)";
                    encontrado = true;
                    break;
                case 'S':
                    camino = "S), ";
                case 'E':
                    orig = campoMinado[i][j];
                    campoMinado[i][j] = '-';
                    while (!encontrado && direccion != DEAD_END) {
                        String caminoPosible = "";
                        switch (direccion) {
                            case UP:
                                caminoPosible = "(U,";
                                break;
                            case RIGHT:
                                caminoPosible = "(R,";
                                break;
                            case DOWN:
                                caminoPosible = "(D,";
                                break;
                            case LEFT:
                                caminoPosible = "(L,";
                                break;
                        }
                        if (encontrado) {
                            camino = camino + caminoPosible;
                        }
                        direccion++;
                    }
                    if (!encontrado) {
                        System.out.println("cosa rara");
                        campoMinado[i][j] = orig;
                    }
                    break;
            }
        }
        return camino;
    }
}