単一リンクリストのdelete()メソッド


4

単一リンクリストからノードを削除する方法を簡単に確認してください。私はこれがほぼ最適に行われていないことをかなり確信しており、フィードバックを得たいと思っています。

ノードとしてSinglyLinkedNode要素を使用します:

public class SinglyLinkedNode {
    private SinglyLinkedNode next = null;
    int data;
    public SinglyLinkedNode(int data){
        this.data=data;
    }
    public int getData(){
        return this.data;
    }
    public void setNext(SinglyLinkedNode next){
        this.next = next;
    }
    public SinglyLinkedNode getNext(){
        return this.next;
    }
}

要素の定義と削除機能は次のとおりです:

import data_structures.LinkedLists.SinglyLinkedNode;

public class SinglyLinkedList{
    private SinglyLinkedNode head = null;
    private SinglyLinkedNode tail = null;
    private int length = 0;
    public SinglyLinkedList(int data){
        this.head = new SinglyLinkedNode(data);
        this.tail = this.head;
        this.length = 1;
    }

    public void delete(int data){
        SinglyLinkedNode n = this.head;
        if (n==null){
            return;
        }
        if (n.getData()==data){//If the head is the data we want
            if (n.getNext()==null){//If it's the only node, null the head and tail
                this.tail = null;
                this.head = null;
                this.length = 0;
            }
            else {//Or move the head to the next node
                this.head = n.getNext();
                this.length--;
            }
            return;
        }
        while (n.getNext()!=null && n.getNext().getData()!=data){//Get the data node or the last node at n.next
            n=n.getNext();
        }
        if (n.getNext() == null){//If n is the last element in the list
            if (n.getData()!=data){//If data wasn't in array then we're done
                return;
            }
            //If we're deleting the only remaining element
            if (this.length <=1){
                this.tail = null;
                this.head = null;
                this.length=0;
            }
            else {//If we're just moving the tail
                n.setNext(null);
                this.tail = n;
                this.length--;
            }
        }
        else {//If n is not the last element
            if (n.getNext().getNext()==null){//If n.next is the last element
                n.setNext(null);
                this.tail = n;
                this.length--;
            }
            else {//If n.next is not the last element
                n.setNext(n.getNext().getNext());
                this.length--;
            }
        }
    }
}

ご覧のとおり、これはかなりのコード行です-正確には46行です。特に、whileループの下のセクションは冗長に見えますが、どのように置き換えるかわかりません。

4

That's a very lengthly piece of code. To delete a Node, it's not about doing something confusing; it's about changing links around. Imaging this list:

1, 2, 3, 4, 5

In this case, 1 links to 2, which links to 3, and so on. So what if you want to remove 3, for example? Well, change the links so that 2 links to 4!

How? Well...

  1. Rewrite the method so that it returns a boolean depending on if the delete was a success:

    public boolean delete(int data) {
    
  2. Handle special case head and empty list:

        SinglyLinkedNode nodeBeforeDelete = this.head;
        if (nodeBeforeDelete == null) { // List in empty
            return false;
        } else if (nodeBeforeDelete.getData() == data) {
            this.head = this.head.getNext();
            return true;
        }
    
  3. Loop until you find the data:

        while (true) {
            SinglyLinkedNode next = nodeBeforeDelete.getNext()
            if (next == null) { // No data found in list
                return false;
            } else if (next.getData() == data) {
                break;
            }
            nodeBeforeDelete = next;
        }
    
  4. Relink the nodes:

        SinglyLinkedNode next = nodeBeforeDelete.getNext();
        nodeBeforeDelete.setNext(next.getNext());
        next.setNext(null);
    
  5. End the method:

        return true;
    }
    

Result:

    public boolean delete(int data) {
        SinglyLinkedNode nodeBeforeDelete = this.head;
        if (nodeBeforeDelete == null) { // List in empty
            return false;
        } else if (nodeBeforeDelete.getData() == data) {
            this.head = this.head.getNext();
            return true;
        }
        while (true) {
            SinglyLinkedNode next = nodeBeforeDelete.getNext()
            if (next == null) { // No data found in list
                return false;
            } else if (next.getData() == data) {
                break;
            }
            nodeBeforeDelete = next;
        }
        SinglyLinkedNode next = nodeBeforeDelete.getNext();
        nodeBeforeDelete.setNext(next.getNext());
        next.setNext(null);
        return true;
    }