Linked lists examples

LinkedListDoublyExemple.java

package com.jocile.example.linkedlist;

/**
 * Dynamically doubly linked list
 */
public class LinkedListDoublyExemple<T> {
  private NodeD<T> primeiroNo;
  private NodeD<T> ultimoNo;

  private int tamanhoLista = 0;

  public void add(T elemento) {
    NodeD<T> novoNo = new NodeD<T>(elemento);
    novoNo.setNoProximo(null);
    novoNo.setNoPrevio(ultimoNo);
    if (primeiroNo == null) {
      primeiroNo = novoNo;
    }
    if (ultimoNo != null) {
      ultimoNo.setNoProximo(novoNo);
    }
    ultimoNo = novoNo;
    tamanhoLista++;
  }

  public void add(int index, T elemento) {
    NodeD<T> noAuxiliar = getNo(index);
    NodeD<T> novoNo = new NodeD<>(elemento);
    novoNo.setNoProximo(noAuxiliar);

    if (novoNo.getNoProximo() != null) {
      novoNo.setNoPrevio(noAuxiliar.getNoPrevio());
      novoNo.getNoProximo().setNoPrevio(novoNo);
    } else {
      novoNo.setNoPrevio(ultimoNo);
      ultimoNo = novoNo;
    }
    if (index == 0) {
      primeiroNo = novoNo;
    } else {
      novoNo.getNoPrevio().setNoProximo(novoNo);
    }
    tamanhoLista++;
  }

  public void remove(int index) {
    if (index == 0) {
      primeiroNo = primeiroNo.getNoProximo();
      if (primeiroNo != null) {
        primeiroNo.setNoPrevio(null);
      }
    } else {
      NodeD<T> noAuxiliar = getNo(index);
      noAuxiliar.getNoPrevio().setNoProximo(noAuxiliar.getNoProximo());
      if (noAuxiliar != ultimoNo) {
        noAuxiliar.getNoProximo().setNoPrevio(noAuxiliar.getNoPrevio());
      } else {
        ultimoNo = noAuxiliar;
      }
    }
    tamanhoLista--;
  }

  public T get(int index) {
    return getNo(index).getConteudo();
  }

  private NodeD<T> getNo(int index) {
    NodeD<T> noAuxiliar = primeiroNo;
    for (int i = 0; (i < index) && (noAuxiliar != null); i++) {
      noAuxiliar = noAuxiliar.getNoProximo();
    }
    return noAuxiliar;
  }

  public int size() {
    return tamanhoLista;
  }

  @Override
  public String toString() {
    String strRetorno = "";
    NodeD<T> noAuxiliar = primeiroNo;
    for (int i = 0; i < size(); i++) {
      strRetorno += "[No{conteudo=" + noAuxiliar.getConteudo() + "}]--->";
      noAuxiliar = noAuxiliar.getNoProximo();
    }
    strRetorno += "null";
    return strRetorno;
  }

  public static void main(String args[]) {
    LinkedListDoublyExemple<String> minhaListaEncadeada = new LinkedListDoublyExemple<>();

    minhaListaEncadeada.add("c1");
    minhaListaEncadeada.add("c2");
    minhaListaEncadeada.add("c3");
    minhaListaEncadeada.add("c4");
    minhaListaEncadeada.add("c5");
    minhaListaEncadeada.add("c6");
    minhaListaEncadeada.add("c7");

    System.out.println(minhaListaEncadeada);

    minhaListaEncadeada.remove(3);
    minhaListaEncadeada.add(3, "99");

    System.out.println(minhaListaEncadeada);
    System.out.println(minhaListaEncadeada.get(3));
  }
}

LinkedListExample.java

package com.jocile.example.linkedlist;

/**
 * Dynamically linked list
 */
public class LinkedListExample<T> {
  private NodeG<T> referenciaEntrada;

  public LinkedListExample() {
    this.referenciaEntrada = null;
  }

  public void add(T content) {
    NodeG<T> novoNo = new NodeG<T>(content);
    if (this.isEmpty()) {
      referenciaEntrada = novoNo;
      return;
    }
    NodeG<T> noAuxiliar = referenciaEntrada;
    for (int i = 0; i < size() - 1; i++) {
      noAuxiliar = noAuxiliar.getNextNode();
    }
    noAuxiliar.setNextNode(novoNo);
  }

  public T get(int index) {
    return getNo(index).getContent();
  }

  private NodeG<T> getNo(int index) {
    validaIndice(index);
    NodeG<T> noAuxiliar = referenciaEntrada;
    NodeG<T> noRetorno = null;
    for (int i = 0; i <= index; i++) {
      noRetorno = noAuxiliar;
      noAuxiliar = noAuxiliar.getNextNode();
    }
    return noRetorno;
  }

  public T remove(int index) {
    validaIndice(index);
    NodeG<T> noPivor = getNo(index);
    if (index == 0) {
      referenciaEntrada = noPivor.getNextNode();
      return noPivor.getContent();
    }
    NodeG<T> noAnterior = getNo(index - 1);
    noAnterior.setNextNode(noPivor.getNextNode());
    return noPivor.getContent();
  }

  public int size() {
    int tamanhoLista = 0;
    NodeG<T> referenciaAux = referenciaEntrada;
    while (true) {
      if (referenciaAux != null) {
        tamanhoLista++;
        if (referenciaAux.getNextNode() != null) {
          referenciaAux = referenciaAux.getNextNode();
        } else {
          break;
        }
      } else {
        break;
      }
    }
    return tamanhoLista;
  }

  private void validaIndice(int index) {
    if (index >= size()) {
      int ultimoIndice = size() - 1;
      throw new IndexOutOfBoundsException(
        "Não existe conteúdo no índice " +
        index +
        " desta lista. Esta lista só vai até o índice " +
        ultimoIndice +
        '.'
      );
    }
  }

  public boolean isEmpty() {
    return referenciaEntrada == null ? true : false;
  }

  public NodeG<T> getReferenciaEntrada() {
    return referenciaEntrada;
  }

  public void setReferenciaEntrada(NodeG<T> referenciaEntrada) {
    this.referenciaEntrada = referenciaEntrada;
  }

  @Override
  public String toString() {
    String strRetorno = "";
    NodeG<T> noAuxiliar = referenciaEntrada;
    for (int i = 0; i < size(); i++) {
      strRetorno += "[No{conteudo=" + noAuxiliar.getContent() + "}]--->";
      noAuxiliar = noAuxiliar.getNextNode();
    }
    strRetorno += "null";
    return strRetorno;
  }

  public static void main(String args[]) {
    LinkedListExample<String> minhaListaEncadeada = new LinkedListExample<>();

    minhaListaEncadeada.add("teste1");
    minhaListaEncadeada.add("teste2");
    minhaListaEncadeada.add("teste3");
    minhaListaEncadeada.add("teste4");

    System.out.println(minhaListaEncadeada.get(0));
    System.out.println(minhaListaEncadeada.get(1));
    System.out.println(minhaListaEncadeada.get(2));
    System.out.println(minhaListaEncadeada.get(3));

    System.out.println(minhaListaEncadeada);

    minhaListaEncadeada.remove(3);

    System.out.println(minhaListaEncadeada);
  }
}

Node.java

package com.jocile.example.linkedlist;

public class Node {
  private int date;
  private Node refNode = null;

  public Node(int date) {
    this.date = date;
  }

  public int getDate() {
    return this.date;
  }

  public void setDate(int date) {
    this.date = date;
  }

  public Node getRefNode() {
    return this.refNode;
  }

  public void setRefNode(Node refNode) {
    this.refNode = refNode;
  }

  @Override
  public String toString() {
    return "Node{" + " date='" + getDate() + "'" + "}";
  }
}

NodeD.java

package com.jocile.example.linkedlist;

/**
 * Doubly linked node
 */
public class NodeD<T> {
  private T conteudo;
  private NodeD<T> noProximo;
  private NodeD<T> noPrevio;

  public NodeD(T conteudo) {
    this.conteudo = conteudo;
  }

  public T getConteudo() {
    return conteudo;
  }

  public void setConteudo(T conteudo) {
    this.conteudo = conteudo;
  }

  public NodeD<T> getNoProximo() {
    return noProximo;
  }

  public void setNoProximo(NodeD<T> noProximo) {
    this.noProximo = noProximo;
  }

  public NodeD<T> getNoPrevio() {
    return noPrevio;
  }

  public void setNoPrevio(NodeD<T> noPrevio) {
    this.noPrevio = noPrevio;
  }

  @Override
  public String toString() {
    return "NodeD{" + "conteudo=" + conteudo + '}';
  }
}

NodeG.java

package com.jocile.example.linkedlist;

public class NodeG<T> {
  private T content;
  private NodeG<T> nextNode = null;

  public NodeG(T content) {
    this.content = content;
  }

  public NodeG(T content, NodeG<T> nextNode) {
    this.content = content;
    this.nextNode = nextNode;
  }

  public T getContent() {
    return content;
  }

  public void setContent(T content) {
    this.content = content;
  }

  public NodeG<T> getNextNode() {
    return nextNode;
  }

  public void setNextNode(NodeG<T> nextNode) {
    this.nextNode = nextNode;
  }

  @Override
  public String toString() {
    return "No{" + content + '}';
  }

  public String toStringLinked() {
    String str = "No{" + content + "}";

    if (nextNode != null) {
      str += "->" + nextNode.toString();
    } else {
      str += "->null";
    }
    return str;
  }
}

NodeGenerics.java

package com.jocile.example.linkedlist;

public class NodeGenerics<T> {
  private T object;
  private NodeGenerics<T> refNode;

  public NodeGenerics() {}

  public NodeGenerics(T object) {
    this.refNode = null;
    this.object = object;
  }

  public Object getObject() {
    return object;
  }

  public void setObject(T object) {
    this.object = object;
  }

  public NodeGenerics<T> getRefNode() {
    return refNode;
  }

  public void setRefNode(NodeGenerics<T> refNode) {
    this.refNode = refNode;
  }

  @Override
  public String toString() {
    return "Node{" + " object='" + getObject() + "'" + "}";
  }
}

NodeObject.java

package com.jocile.example.linkedlist;

public class NodeObject {
  private Object object;
  private NodeObject refNode;

  public NodeObject() {}

  public NodeObject(Object object) {
    this.object = object;
  }

  public Object getObject() {
    return this.object;
  }

  public void setObject(Object object) {
    this.object = object;
  }

  public NodeObject getRefNode() {
    return this.refNode;
  }

  public void setRefNode(NodeObject refNode) {
    this.refNode = refNode;
  }

  @Override
  public String toString() {
    return "{" + " object='" + getObject() + "'" + "}";
  }
}

QueueExample.java

package com.jocile.example.linkedlist;

/**
 * FIFO queue example, first in first out
 */
public class QueueExample {
  private NodeObject firstRefNode;

  public QueueExample() {
    this.firstRefNode = null;
  }

  public void enqueue(Object object) {
    NodeObject newNode = new NodeObject(object);
    newNode.setRefNode(firstRefNode);
    firstRefNode = newNode;
  }

  public Object first() {
    if (!this.isEmpty()) {
      NodeObject firstNode = firstRefNode;
      while (true) {
        if (firstNode.getRefNode() != null) {
          firstNode = firstNode.getRefNode();
        } else {
          break;
        }
      }
      return firstNode.getObject();
    }
    return null;
  }

  public Object dequeue() {
    if (!this.isEmpty()) {
      NodeObject firstNode = firstRefNode;
      NodeObject nodeAuxiliary = firstRefNode;
      while (true) {
        if (firstNode.getRefNode() != null) {
          nodeAuxiliary = firstNode;
          firstNode = firstNode.getRefNode();
        } else {
          nodeAuxiliary.setRefNode(null);
          break;
        }
      }
      return firstNode.getObject();
    }
    return null;
  }

  public boolean isEmpty() {
    return firstRefNode == null ? true : false;
  }

  @Override
  public String toString() {
    String stringReturn = "";
    NodeObject nodeAuxiliary = firstRefNode;

    if (firstRefNode != null) {
      while (true) {
        stringReturn += "[Node{object: " + nodeAuxiliary.getObject() + "}]--->";

        if (nodeAuxiliary.getRefNode() != null) {
          nodeAuxiliary = nodeAuxiliary.getRefNode();
        } else {
          stringReturn += "null";
          break;
        }
      }
    } else {
      stringReturn = "null";
    }

    return stringReturn;
  }

  public static void main(String[] args) {
    QueueExample myqueue = new QueueExample();

    myqueue.enqueue("first");
    myqueue.enqueue("second");
    myqueue.enqueue("third");
    myqueue.enqueue("fourth");

    System.out.println(myqueue);
    System.out.println(myqueue.dequeue());
    System.out.println(myqueue);
    myqueue.enqueue("last");
    System.out.println(myqueue);
    System.out.println(myqueue.first());
    System.out.println(myqueue);
  }
}

QueueGenericExample.java

package com.jocile.example.linkedlist;

/**
 * FIFO queue example, first in first out
 */
public class QueueGenericExample<T> {
  private NodeGenerics<T> firstRefNode;

  public QueueGenericExample() {
    this.firstRefNode = null;
  }

  public void enqueue(T object) {
    NodeGenerics<T> newNode = new NodeGenerics<T>(object);
    newNode.setRefNode(firstRefNode);
    firstRefNode = newNode;
  }

  @SuppressWarnings("unchecked")
  public T first() {
    if (!this.isEmpty()) {
      NodeGenerics<T> firstNode = firstRefNode;
      while (true) {
        if (firstNode.getRefNode() != null) {
          firstNode = firstNode.getRefNode();
        } else {
          break;
        }
      }
      return (T) firstNode.getObject();
    }
    return null;
  }

  @SuppressWarnings("unchecked")
  public T dequeue() {
    if (!this.isEmpty()) {
      NodeGenerics<T> firstNode = firstRefNode;
      NodeGenerics<T> nodeAuxiliary = firstRefNode;
      while (true) {
        if (firstNode.getRefNode() != null) {
          nodeAuxiliary = firstNode;
          firstNode = firstNode.getRefNode();
        } else {
          nodeAuxiliary.setRefNode(null);
          break;
        }
      }
      return (T) firstNode.getObject();
    }
    return null;
  }

  public boolean isEmpty() {
    return firstRefNode == null ? true : false;
  }

  @Override
  public String toString() {
    String stringReturn = "";
    NodeGenerics<T> nodeAuxiliary = firstRefNode;

    if (firstRefNode != null) {
      while (true) {
        stringReturn += "[Node{object: " + nodeAuxiliary.getObject() + "}]--->";

        if (nodeAuxiliary.getRefNode() != null) {
          nodeAuxiliary = nodeAuxiliary.getRefNode();
        } else {
          stringReturn += "null";
          break;
        }
      }
    } else {
      stringReturn = "null";
    }

    return stringReturn;
  }

  public static void main(String[] args) {
    QueueGenericExample<String> myqueue = new QueueGenericExample<>();

    myqueue.enqueue("first");
    myqueue.enqueue("second");
    myqueue.enqueue("third");
    myqueue.enqueue("fourth");

    System.out.println(myqueue);
    System.out.println(myqueue.dequeue());
    System.out.println(myqueue);
    myqueue.enqueue("last");
    System.out.println(myqueue);
    System.out.println(myqueue.first());
    System.out.println(myqueue);
  }
}

StackExample.java

package com.jocile.example.linkedlist;

/**
 * LIFO stack example, last in first out
 */
public class StackExample {
  private Node firstRefNode;

  public StackExample() {
    this.firstRefNode = null;
  }

  public void push(Node newNode) {
    Node refAuxiliary = firstRefNode;
    firstRefNode = newNode;
    firstRefNode.setRefNode(refAuxiliary);
  }

  public Node pop() {
    if (!this.isEmpty()) {
      Node nodePoped = firstRefNode;
      firstRefNode = firstRefNode.getRefNode();
      return nodePoped;
    }
    return null;
  }

  public Node top() {
    return firstRefNode;
  }

  public boolean isEmpty() {
    return firstRefNode == null ? true : false;
  }

  @Override
  public String toString() {
    String stringReturn = "--------------------------------\n";
    stringReturn += " Stack\n";
    stringReturn += "--------------------------------\n";

    Node nodeAuxiliary = firstRefNode;

    while (true) {
      if (nodeAuxiliary != null) {
        stringReturn += "[Node{date=" + nodeAuxiliary.getDate() + "}]\n";
        nodeAuxiliary = nodeAuxiliary.getRefNode();
      } else {
        break;
      }
    }
    stringReturn += "================================\n";
    return stringReturn;
  }

  public static void main(String[] args) {
    StackExample myStack = new StackExample();

    myStack.push(new Node(1));
    myStack.push(new Node(2));
    myStack.push(new Node(3));
    myStack.push(new Node(4));
    myStack.push(new Node(5));
    myStack.push(new Node(6));

    System.out.println(myStack);
    System.out.println(myStack.pop());
    System.out.println(myStack);

    myStack.push(new Node(99));
    System.out.println(myStack);
  }
}