Java remove an item within a simple linked list

Question

Java remove an item within a simple linked list

Navigation

#1 by (1 votes)

3

I am having difficulty generating a code to remove an item from a certain position in a linked list, this is not an ArrayList, but a linked list, for this I am creating a method as below:

public Object remove(int posicao){

I know the creation is similar to that of the method in position, but I'm not able to develop the method in the way of removing items in the middle of the list.

package slist;

import java.util.Scanner;

public class SList {

private SListNode head;
  private int tamanho;

  public SList() {
    tamanho = 0;
    head = null;
  }

  public boolean eVazio() {
    return tamanho == 0;
  }

  public int length() {
    return tamanho;
  }

  public void insereAntes(Object obj) {
    head = new SListNode(obj, head);
    tamanho++;
  }

  public void insereApos(Object obj) {
    if (head == null) {
      head = new SListNode(obj);
    } else {
      SListNode no = head;
      while (no.next != null) {
        no = no.next;
      }
      no.next = new SListNode(obj);
    }
    tamanho++;
  }

  public Object naPosicao(int posicao) {
    SListNode noAtual;

    if ((posicao < 1) || (head == null)) {
      return null;
    } else {
      noAtual = head;
      while (posicao > 1) {
        noAtual = noAtual.next;
        if (noAtual == null) {
          return null;
        }
        posicao--;
      }
      return noAtual.item;
    }
  } 

  public Object remove(int posicao){

}  

  public String toString() {
    int i;
    Object obj;
    String res = "[  ";

    SListNode atual = head;

    while (atual != null) {
      obj = atual.item;
      res = res + obj.toString() + "  ";
      atual = atual.next;
    }
    res = res + "]";
    return res;
  }

    public static void main (String[] args) {
    SList lst1 = new SList();
    SList lst2 = new SList();
    int escolha;
    Scanner opcao = new Scanner(System.in);

    do {
        System.out.println("Menu de opcoes \n"
        + "1 - Coloca na lista \n"
        + "2 - Mostra na Lista \n"
        + "3 - Listar conteudo de determinada posicao\n"
        + "4 - Remover conteudo de determinada posicao \n");

        escolha = opcao.nextInt();

            switch (escolha) {
                case 1: System.out.println(" Diga o nome do aluno");
                opcao.nextLine();
                String item = opcao.nextLine();
                    lst1.insereApos(item);
                    break;
                case 2: System.out.println("Listando os nomes da lista\n"
                                            + lst1.toString());
                    break;
                case 3: System.out.println("informe a posicao desejada");
                    int esc = opcao.nextInt();
                    System.out.println("Objeto na posicao " + esc + " " + lst1.naPosicao(esc));
                case 4:     


            }
    } while (escolha <=4);
  }
}

And here's the Class SListNode

package slist;

public class SListNode {
  Object item;
  SListNode next;

  SListNode(Object obj) {
    item = obj;
    next = null;
  }

  SListNode(Object obj, SListNode next) {
    item = obj;
    this.next = next;
  }

}

java lista-encadeada

asked by anonymous 06.09.2014 / 19:10

1 answer

pinch zoom android What is the best way to split a Django project into apps?

score 1 · Accepted Answer

You just have to change the link by removing the current link and passing the current link to the predecessor.

The logic is quite simple:

List

{Node-Previous} - > {Node to be Excluded} - > {Post-deleted node}

Operation to be done:

{Previous Node} .next = {Node after deleted}

For this I modified your Object naPosicao() method to return a node in the list:

public SListNode getNo(int posicao) { //retorna direto um nó e não um objeto
    SListNode noAtual;

    if ((posicao < 1) || (head == null)) {
        return null;
    } else {
        noAtual = head;
        while (posicao > 1) {
            noAtual = noAtual.next;
            if (noAtual == null) {
                return null;
            }
            posicao--;
        }
        return noAtual; // única mudança real no método.
    }
}

Now that you can get the nodes with this method just use it to do the logic I described earlier:

public void remove(int posicao) {
    try{
        SListNode predecessor = getNo(posicao - 1);
        SListNode excluido = predecessor.next;
        predecessor.next = excluido.next;
        excluido = null;  // Para tentar facilitar a exclusão para o garbage collector
    }catch(Exception e){
        e.printStackTrace();
    }
}

Note that I do not delete the object, as this can not be done directly in Java, but by setting excluido = null; I delete references to get it (in a more explicit way) by the garbage collector. This is not a necessary step, as the reference will disappear from the program after this method is called, but makes it clear that you do not intend to use the deleted node again.