1

Java でカスタム LinkedList を作成しました。これは、マップとリストのクロスのようなものです。私は学ぶためにこの演習を行っただけで、HashMap がより優れた高速な実装であることを知っています。私は LinkedList の削除メソッドを実装しましたが、特定の要素のすべての出現を基本的に削除する deleteAll メソッドを記述する最も最適な方法について少し混乱しています。

コード：

public class LinkedListMain
{
    public static void main(String[] args)
    {
        LinkedList linkedList = new LinkedList();

        System.out.println("isEmpty: " + linkedList.isEmpty());

        linkedList.insert("abc", 34);
        linkedList.insert("pqr", 44);
        linkedList.insert("xyz", 54);
        linkedList.insert("asd", 64);
        linkedList.insert("abc", 74);

        linkedList.print();

/*      System.out.println("delete: " + linkedList.delete("abc"));
        System.out.println("delete: " + linkedList.delete("pqr"));
        System.out.println("delete: " + linkedList.delete("xyz"));
        System.out.println("delete: " + linkedList.delete("asd"));
*/
        System.out.println("deleteAll: " + linkedList.deleteAll("abc"));
        System.out.println("isEmpty: " + linkedList.isEmpty());
    }
}

class LinkedList
{
    private ListNode first;
    private ListNode last;

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

    public void insert(String d1, int d2)
    {
        ListNode node = new ListNode(d1, d2);

        if(first == null)
        {
            node.next = null;
            first = node;
            last = node;
        }

        else
        {
            last.next = node;
            node.next = null;
            last = node;
        }
    }

    public String deleteAll(String str)
    {
        return "To Be Implemented";
    }

    public String delete(String str)
    {
        ListNode slow = first;
        ListNode fast = first;

        int count = 0;

        while(fast != null)
        {
            if(count > 1)
            {
                slow = slow.next;
            }

            if(count <= 1)
            {
                count++;
            }

            if(fast.getVal()==str)
            {
                if(fast == first)
                {
                    first = first.next;
                }

                else
                {
                    if(fast.next != null)
                    {
                        slow.next = fast.next;
                    }

                    else
                    {
                        slow.next = null;
                    }
                }

                fast = null;
                return str;     // fast.getVal()
            }

            fast = fast.next;
        }

        return "not found";
    }

    public void print()
    {
        ListNode currentNode = first;

        while(currentNode != null)
        {
            currentNode.print();
            currentNode = currentNode.next;
        }
    }

    public boolean isEmpty()
    {
//      return ( ((first==null) ? (true) : (false)) && ((last==null) ? (true) : (false)));
        return (first==null) ? (true) : (false);
    }
}

class ListNode
{
    private String data1;
    private int data2;

    public ListNode next;

    public ListNode(String d1, int d2)
    {
        data1 = d1;
        data2 = d2;
    }

    public String getVal()
    {
        return data1;
    }

//  public void printMe(ListNode node)
    public void print()
    {
        System.out.println("data1: [" + data1 + "], data2: [" + data2 + "]");
    }
}

この例に関連する 3 つの質問があります。

  1. 理想的な deleteAll 関数は、私の削除関数を繰り返し使用する必要がありますか? これに対応するには、削除機能を変更する必要がありますか?
  2. isEmpty 関数は、理想的には最初と最後の両方を null と比較する必要がありますか? last を null と比較する必要がある場合、これを実装するには、delete および deleteAll 関数をどのように変更すればよいですか。現在の削除機能でこれを実行しようとしましたが、いくつかの問題が発生しました。
  3. 一般に、このコードを大幅に最適化できますか? 「完全な連結リストが必要な場合は、コレクションを使用する」という意味ではなく、可能であれば、この単一連結リストをより正確に最適化する方法を尋ねるだけですか?
4

1 に答える 1

1

deleteAll()おそらく、前のノードをノード削除メソッドに渡すのが最も快適でしょう。が明らかなポインター操作以外のことを行うことが期待される場合delete()、このアクションは除外できます。

/** 
 Deletes all nodes that contain target_string. 
 Returns the number of nodes deleted.
*/
public int deleteAll(String target_string) {
  int deleted_nodes_cnt = 0;
  ...
  if (prev_node.next.getVal().equals(target_string)) { // not ==
    deleteNextNode(prev_node); 
    prev_node = prev_node.next; 
    deleted_nodes_cnt += 1;
  }
  ...
  return deleted_nodes_cnt;
}

/** Delete the node after prev_node; prev_node.next != null */
private void deleteNextNode(Node prev_node) {
  Node dead_node = prev_node.next;
  prev_node.next = prev_node.next.next;
  dead_node.afterDelete(); // any custom cleanup, if required
}

public boolean delete(String target_string) {
   ... 

  if (prev_node.next.getVal().equals(target_string)) { // looks familiar?
    deleteNextNode(prev_node);
    return true; 
  }
  ...
  return false;
}

うまく分解できる同じリスト反復ロジックを使用してdelete()いることに気付くかもしれません。deleteAll()

/**
 Scan nodes, starting from this.
 Returns node X such that X.next.value equals target_string, or null. 
*/
private Node findNodeBeforeMatching(String target_string) {
  Node prev_node = this;
  while (prev_node.next != null) {
    if (prev_node.next.getVal().equals(target_string)) return prev_node;
    else prev_node = prev_node.next;
  }
  return null;
}

このメソッドを効果的に使用するには、LinkedList(基本的に「リスト ヘッド キーパー」) を のサブクラスにNodeするか、両方を共通のクラスのサブクラスにする必要があります。さらに良いことに、 togetNext()とを許可する同じインターフェイスを実装するようにしdeleteNext()ます。または、各操作から a を返すこともできますが、これはもちろんインターフェイスと Node互換性がありません。Collection

古い、正しくないテキスト:個々のメソッド ID を呼び出さないdeleteAll()でください。ただし、これらのメソッドが子孫クラスで特別なことを行う場合を除きます。その理由は、そのようなものはO(1)であり、一定時間で実行されますが、各ノードへのリストのトラバースはO(n)です。AFAICTインスタンス変数は、リストの最後に要素を追加する速度を上げるだけに役立ちます (奇妙なことをしますが)。したがって、実際に確認する必要があります。の場合、メソッドは. 持っているということは、簿記が間違っていて、データが破損していて、続行できないことを意味すると思います。WRT の最適化、ビザンチンがどのように機能するかわかりませんdelete()deleteAll()delete()lastinsert()isEmpty()firstfirst == null assert last == nullfirst == nulllast != nulldelete()動作するはずです。あなたの場合、2つのポインターを使用しても速度が向上するとは思いません。異なる「速度」で 2 つのポインターを実行することは、サイクルを検出する既知の方法ですが、ここでどのように適用できるかわかりません。

ソートされたデータを高速化したい場合は、スキップ リストについて読むか、ツリーを使用してください。並べ替えられていないデータでは、単純な順次スキャンが最善の策です。

私にとって、LinkedList クラス全体は、論理的に単純なので、半分の長さである必要があります。

あなたのListNodeとLinkedListは で不必要に密結合されinsert()ています。これは、インスタンスを構築するのではなく、受け入れる必要があります。ListNodeさらに良いLinkedListことに、従来の実装と同じである必要があります。

データ構造とアルゴリズムに関する Wirth の本を入手してください。非常に親しみやすいものです。（完全に理解したら、クヌースの本を読み進めてみてください。本当に勇気があるなら、岡崎の本を読み進めてください。）

于 2013-03-24T02:38:00.110 に答える