Самый эффективный способ удалить узел из одного связанного списка? - PullRequest
Новая
       25

Самый эффективный способ удалить узел из одного связанного списка?

0 голосов
/ 29 сентября 2019

Я реализую один связанный список целых чисел, и мне было интересно, каков наиболее эффективный способ найти данное значение и удалить его из списка.Это то, что я до сих пор: 

public class LinkedList {
    Node head;

  public void insert(int value){
    Node newNode = new Node();
    newNode.data = value;
    newNode.next = null;

    if(head==null){
      head = newNode;
    } else {
      Node iterator = head;
      while(iterator.next!=null){
        iterator = iterator.next;
      }
      iterator.next = newNode;
    }
  }

  public void display(LinkedList list){
    Node iterator = head;
    while (iterator!=null){
      System.out.println(iterator.data);
      iterator = iterator.next;
    }
  }

  public void remove(LinkedList list, int value){
    Node iterator = head;
    while(iterator!=null){
      if(iterator.next.data == value){
          iterator.next = iterator.next.next;
      } else{
        iterator = iterator.next;
      }
    }
  }
}


public class Node {
  int data;
  Node next;
}

1 Ответ

0 голосов
/ 29 сентября 2019

Я добавляю сюда фрагмент, чтобы удалить узел из SinglyLinkedList.Я предпочитаю forLoop более;Вот почему я добавил фрагмент с циклом for.

Надеюсь, что комментарий в коде поможет вам сориентироваться / пробежаться по фрагменту. 

public boolean remove(int value){ 
 Node oneBeforeValueNode;
 // Using for to iterate through the SinglyLinkedList
 // head → is the head of your SingleLinkedList
 for (Node node = head; node != null; node = node.next) {
      // Compare the value with current node
      if (value.equals(node.data)) {
            // if matches then unlink/remove that node from SinglyLinkedList
            // if its a first node in SingleLinkedList
            if(oneBeforeValueNode==null){
              // Considering there exists next element else SLL will be empty
              head = head.next;
            } else {
              // if there exists next element it SLL it will attach that element with previous one
              oneBeforeValueNode.next = node.next;
            }
            return true;
       }
     // Storing previous node from current
     // To use it once value is found to reference it to current.next(node.next)
     oneBeforeValueNode = node;
   }
 return false;
}

Также добавляется вариант while;просто чтобы плыть по течению. 

public Node remove(Node head, int key) {
        Node current = head;
        Node previous = null;
        while (current != null) {
            if(current.data == key) {

                if(current == head) {
                    head = head.next;
                    current = head;

                } else {
                    previous.next = current.next;
                    current = current.next;
                }

            } else {
                previous = current;
                current = current.next;
            }
        }

        return head;
    }
...