查找正确的位置并存储在LinkedList中

Question

我正在尝试将字符串存储在LinkedList中。我不被允许预先排序，但找到位置并将字符串传递到链表。当我通过文本文件传递字符串时，字符串不会通过最后一个else条件。我的输入文件有乔appyappz斑马cat

当它到达appz时，它不会经过任何语句。它应该插入最后一个else条件并打印5，但没有这样做。

/**
     * Gets the string and arranges them in order
     * @param newString
     */
    public void store(String newString) {
        LinkedListNode current = head;
        System.out.println(newString);
        // if no element in the list
        if (current==null){
            System.out.println("1");
            makeNode(newString);
        }
        // if only 1 elements in the list
        else if(current.getNext()==null ){
            System.out.println("2");
            if(newString.compareTo(current.getName())<0){
                insertBefore(current.getName(),newString);
            } else{
                insertAfter(current.getName(),newString);
            }
        }
        // if the element is smaller than the head in the list
        else if(newString.compareTo(current.getName()) < 0){
            System.out.println("3");
            LinkedListNode temp = makeNode(newString);
            temp.setNext(current);
            head=temp;
        }
        // if the element is greater than the tail in the list
        else if(newString.compareTo(findTail().getName()) > 0){
            System.out.println("4");
            insertAfter(findTail().getName(),newString);
        }
        // for more than two elements in the list
        else{
            System.out.println("5");
            while(!(newString.compareTo(current.getName())>0  && newString.compareTo(current.getNext().getName())<0 ) && current.getNext()!=null){
                current=current.getNext();
            }
            if(newString.compareTo(current.getName())<0){
                insertBefore(current.getName(),newString);
            }
            else{
                insertAfter(current.getName(),newString);
            }
        }
    }   // end of store()

Answer 1

insertBefore有一些问题。我更新了它。

public void insertBefore(String later, String name){
        if(head==null){
            head = new LinkedListNode(name,null);
        }
        else if(head.getName()==later){
            LinkedListNode newNode = makeNode(name);
            newNode.setNext(head);
            head=newNode;   
        }
        else{
            LinkedListNode current = head;
            while(current.getNext().getName()!=later){
                current=current.getNext();
            }
            LinkedListNode newNode = makeNode(name); // create the new node
            newNode.setNext(current.getNext());    
            current.setNext(newNode);
        }
    } // end of insertBefore()

Answer 2

遍历时，不应该更改头引用。要遍历，只需执行以下操作：

Node tmp = head;
while(tmp != null) tmp = tmp.next;

这将非常方便地确定在哪里插入新节点或在哪里删除现有节点。

您的类还应该具有addFirst、addLast、insertBefore和insertAfter的方法。在下面的代码中，Object是您需要的任何数据类型（在您的情况下，String）

public void addLast(Object item)
{
  if(head == null)
  {
    addFirst(item);
  }
  else
  {
    Node<Object> tmp = head;
    while(tmp.next != null)
    {
      tmp = tmp.next;
    }
    tmp.next = new Node<Object>(item, null);
  }
}
public void addFirst(Object item)
{
  head = new Node<Object>(item, head);
}
public void insertAfter(Object key, Object item)
{
  Node<Object> tmp = head;
  while(tmp != null && !tmp.data.equals(key))
  {
    tmp = tmp.next;
  }
  if(tmp != null)
  {
    tmp.next = new Node<Object>(item, tmp.next);
  }
}
public void insertBefore(Object key, Object item)
{
  if(head == null)
  {
    return null;
  }
  if(head.data.equals(key))
  {
    addFirst(item);
    return;
  }
  Node<Object> previous = null;
  Node<Object> current = head;
  while(current != null && !current.data.equals(key))
  {
    previous = current;
    current = current.next;
  }
  //insert between current and previous
  if(current != null)
  {
    previous.next = new Node<Object>(item, current);
  }
}

在我看来，不应该使用嵌套的if/else构造来确定插入位置。这应该取决于您正在调用的方法。

其次，用于控制代码中执行流的条件是不同的。您的IF条件是如果列表为空。如果是，请创建一个新节点并将其添加到列表中。在满足该条件之后，将检查仅包含一个节点的列表。在那之后，您就不再检查列表的长度了。预期的逻辑是，您应该检查大于1的列表大小；然而，这是你的失败案例（最后一个）。如果你要在insert方法之外进行这种检查，那么就这样做（清除你的代码）：

if (current==null){
    System.out.println("1");
    makeNode(newString);
}
// if only 1 elements in the list
else if(current.getNext()==null ){
    System.out.println("2");
    if(newString.compareTo(current.getName())<0){
        insertBefore(current.getName(),newString);
    } else{
        insertAfter(current.getName(),newString);
    }
}
// if the list has more than one element
else
{
    // figure out where it goes (before or after) and insert
}

如果您注意到，else/If和else块基本上做相同的事情。因此，您的代码可以（也应该）简化如下：

if (current==null){
    System.out.println("1");
    makeNode(newString);
}
// if the list has one or more elements
else
{
    // figure out where it goes (before or after) and insert
}