LinkedList中的排序列表

普密特·帕特尔（Bhumi Patel）

我已经编写了这段代码，以将元素插入和删除并形成链表。我想将元素插入到排序列表中的列表中。如何改善我的“添加”方法来做到这一点？

public void add(String element)
      {
       if (isEmpty()) 
          {
              first = new Node(element);
              last = first;
          }
          else
          {
              // Add to end of existing list
              last.next = new Node(element);
              last = last.next;
        }

      }

      /**
      * The toString method computes the string representation of the list.
      * 
      * @return The string form of the list.
      */
      public String toString()
      {
        StringBuilder strBuilder = new StringBuilder();

        // Use p to walk down the linked list
        Node p = first;
        while (p != null) {
          strBuilder.append("[" + p.value + "]");
          p = p.next;
        }
        return strBuilder.toString();
      }


           The remove method removes an element.
           @param element The element to remove.
           @return true if the remove succeeded, 
             false otherwise.


        public boolean remove(String element)
        {
           if (isEmpty()) 
               return false;      

           if (element.equals(first.value))
           {
              // Removal of first item in the list
              first = first.next;
              if (first == null)
                  last = null;       
              return true;
           }

          // Find the predecessor of the element to remove
          Node pred = first;
          while (pred.next != null && 
                 !pred.next.value.equals(element))
          {
              pred = pred.next;
          }

          // pred.next == null OR pred.next.value is element
          if (pred.next == null)
              return false;

          // pred.next.value  is element
          pred.next = pred.next.next;    

          // Check if pred is now last
          if (pred.next == null)
              last = pred;

          return true;       
        }

桑杰斯

这是一个排序的链表。插入时，我们可以使其插入正确的位置。

1）如果列表为空，则将第一个和最后一个作为新元素。别的

2）如果新元素小于第一个节点，则使新元素为第一个。别的

3）遍历列表，找到上一个节点较小而下一个节点较大或为空的位置。在这个位置插入新节点

因此，使用此方法，我们可以始终对列表进行排序。

 public void add(String element)
  {
      Node newNode = new Node(element);
      if (isEmpty()) 
      {
          first = newNode;
          last = newNode;
      }
      else if (element.compareTo(first.value) < 0)//if element is lesser than all elements in list
      {
         newNode.next = first;
         first= newNode;
      }
      else
      {
        Node after = first.next;
        Node before = first;
        while (after != null)// finding exact position to insert
        {
            if (element.compareTo(after.value) < 0)
                break;
            before = after;
            after = after.next;
        }
        // insert between before & after
        newNode.next = before.next;
        before.next = newNode;
      }

  }

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。