java - 我想找到链表之间的数字

Question

我正在尝试找到如何使用 inBetween 作为公共(public)方法来获取列表中数字之间的值。

双链接类:

public class DoublyLinkedList
   {
   private Link first;               // ref to first item
   private Link last;                // ref to last item
// -------------------------------------------------------------
   public DoublyLinkedList()         // constructor
      {
      first = null;                  // no items on list yet
      last = null;
      }
// -------------------------------------------------------------
   public boolean isEmpty()          // true if no links
      { return first==null; }
// -------------------------------------------------------------
   public void insertFirst(long dd)  // insert at front of list
      {
      Link newLink = new Link(dd);   // make new link

      if( isEmpty() )                // if empty list,
         last = newLink;             // newLink <-- last
      else
         first.previous = newLink;   // newLink <-- old first
      newLink.next = first;          // newLink --> old first
      first = newLink;               // first --> newLink
      }
// -------------------------------------------------------------
   public void insertLast(long dd)   // insert at end of list
      {
      Link newLink = new Link(dd);   // make new link
      if( isEmpty() )                // if empty list,
         first = newLink;            // first --> newLink
      else
         {
         last.next = newLink;        // old last --> newLink
         newLink.previous = last;    // old last <-- newLink
         }
      last = newLink;                // newLink <-- last
      }
// -------------------------------------------------------------
   public Link deleteFirst()         // delete first link
      {                              // (assumes non-empty list)
      Link temp = first;
      if(first.next == null)         // if only one item
         last = null;                // null <-- last
      else
         first.next.previous = null; // null <-- old next
      first = first.next;            // first --> old next
      return temp;
      }
// -------------------------------------------------------------
   public Link deleteLast()          // delete last link
      {                              // (assumes non-empty list)
      Link temp = last;
      if(first.next == null)         // if only one item
         first = null;               // first --> null
      else
         last.previous.next = null;  // old previous --> null
      last = last.previous;          // old previous <-- last
      return temp;
      }
// -------------------------------------------------------------
                                     // insert dd just after key
   public boolean insertAfter(long key, long dd)
      {                              // (assumes non-empty list)
      Link current = first;          // start at beginning
      while(current.dData != key)    // until match is found,
         {
         current = current.next;     // move to next link
         if(current == null)
            return false;            // didn't find it
         }
      Link newLink = new Link(dd);   // make new link

      if(current==last)              // if last link,
         {
         newLink.next = null;        // newLink --> null
         last = newLink;             // newLink <-- last
         }
      else                           // not last link,
         {
         newLink.next = current.next; // newLink --> old next
                                      // newLink <-- old next
         current.next.previous = newLink;
         }
      newLink.previous = current;    // old current <-- newLink
      current.next = newLink;        // old current --> newLink
      return true;                   // found it, did insertion
      }
// -------------------------------------------------------------
   public Link deleteKey(long key)   // delete item w/ given key
      {                              // (assumes non-empty list)
      Link current = first;          // start at beginning
      while(current.dData != key)    // until match is found,
         {
         current = current.next;     // move to next link
         if(current == null)
            return null;             // didn't find it
         }
      if(current==first)             // found it; first item?
         first = current.next;       // first --> old next
      else                           // not first
                                     // old previous --> old next
         current.previous.next = current.next;

      if(current==last)              // last item?
         last = current.previous;    // old previous <-- last
      else                           // not last
                                     // old previous <-- old next
         current.next.previous = current.previous;
      return current;                // return value
      }
// -------------------------------------------------------------
   public void displayForward()
      {
      System.out.print("List (first-->last): ");
      Link current = first;          // start at beginning
      while(current != null)         // until end of list,
         {
         current.displayLink();      // display data
         current = current.next;     // move to next link
         }
      System.out.println("");
      }
// -------------------------------------------------------------
   public void displayBackward()
      {
      System.out.print("List (last-->first): ");
      Link current = last;           // start at end
      while(current != null)         // until start of list,
         {
         current.displayLink();      // display data
         current = current.previous; // move to previous link
         }
      System.out.println("");
      }
// -------------------------------------------------------------
   }  // end class DoublyLinkedList

InBetweenDemo 类作为主类:

public class InBetweenDemo
{
   public static void main(String[] args)
      {                             // make a new list
      DoublyLinkedList theList = new DoublyLinkedList();

      theList.insertFirst(22);      // insert at front
      theList.insertFirst(44);
      theList.insertFirst(66);

      theList.insertLast(11);       // insert at rear
      theList.insertLast(33);
      theList.insertLast(55);

      theList.displayForward(); 
      int n=55;// display list forward
      System.out.println("inBetween("+n+") "+ theList.inBetween(n));

      theList.deleteFirst();        // delete first item
      theList.displayForward(); 
      n=55;
      System.out.println("inBetween("+n+") "+ theList.inBetween(n));

      theList.deleteLast(); 
      theList.displayForward(); 
      n=33;
      System.out.println("inBetween("+n+") "+ theList.inBetween(n));
      theList.deleteKey(22);        // delete item with key 11
      theList.displayForward(); 

      System.out.println("inBetween("+n+") "+ theList.inBetween(n));
      n=99;
      System.out.println("inBetween("+n+") "+ theList.inBetween(n));

      theList.displayForward();     // display list forward

      theList.insertAfter(11, 77);  // insert 77 after 22
      theList.insertAfter(33, 88);  // insert 88 after 33

      theList.displayForward();     // display list forward
      }  // end main()
   }  // end class DoublyLinkedApp
////////////////////////////////////////////////////////////////

我计划让 inBetween 方法接受一个项目作为其参数，如果该项目位于该列表中最小和最大元素之间，则返回 true。否则，该方法返回 false。但是我不确定如何用代码编写它。另外，我想知道如果删除列表中最小的项目或删除列表中最大的项目，程序可能不知道哪个项目最大和最小。那么我还应该使用一种方法来首先获取最大值和最小值吗？

Answer 1

您可以创建 inBetween 方法，使其以数字作为参数，并且在内部您可以调用一个方法，在该方法中您将实现确定列表中最小值和最大值的算法。 注意仅当您的列表是全局定义的而不是在特定方法中时，这才有效，否则您还必须将该列表作为参数提供给 inBetween 方法。所以在伪代码中你可以这样做:

inBetween(numberToBeChecked):
   max = getMax(yourList)
   min = getMin(yourList)        // you can implement this in one method and return an array containing of two elements for example. It's your choice.
   if (numberToBeChecked > min && numberToBeChecked < max):
          return True
   else:
          return False

希望这有帮助。