How to implement insert and sort method Comparable array with double link list in java

Question

I need help please, I tried to answer but it there a problem.

My question is:

Use the addAtFirstSmaller (T t) method to implement Insertion to sort a Comparable array a.

The implementation will be very simple with the method above.

1: Create a DoublyLinkedList list.call it a list.

2: Iterate over the array a. For each element t in a, add t to list by: lista.addAtFirstSmaller (t);

3: Iterate over the list and place the respective elements in the corresponding place in a. I have method addAtFirstSmaller (t).it work good. I tried in the first tow steps, but I'm not understand how I implement step 3.

please I need help.

enter code here
 public Iterator<T> iterator() {

 return new Iterator<T>() {
    
         ListNode<T> node = head.next;

         @Override
         public boolean hasNext() {
          
                 return node != null;
         }

         @Override
         public T next() {
                 
                 if (!hasNext()) {
                         throw new NoSuchElementException();
                 }
                
                 T elem = node.element;
               
                 node = node.next;
             
                 return elem;
         }
         @Override
         public void remove() {
         }
     };
    }
public void addAtFirstSmaller(T t) {

ListNode<T> curr = getLast();

 or a node with value < t
while(curr != head)
{
    if(curr.element.compareTo(t) < 0) 
        break;
    curr = curr.pre;
}

if(curr == head) 
{
    addFirst(t);
}
else
{
  
    ListNode<T> node = new ListNode<T>(curr, curr.pre, t);
   
   
    curr.pre.next = node;
    curr.pre = node; 
}  
}


  enter code here
 public void insertionSort(Comparable[] a) {
    DoublyLinkedList<T> lista = new DoublyLinkedList<T>();

      T  t;
      int ind =0;
 
for(int i = 0; i< a.length; i++) {
     t =  (T) a[i]; 
    
    lista.addAtFirstSmaller(t);
    }
    
    Iterator<T> ite = lista.iterator();
    while(ite.hasNext()) {
     a[ind] = ite.next();
     ind++;
    }
  } 

  // TestClass
  public static void main(string[] args){
    Comparable[] a = new Comparable[5];
    DoublyLinkedList<Integer> lista = new DoublyLinkedList<Integer>();
    a[0] = Integer.valueOf(13);
    a[1] = Integer.valueOf(2);
    a[2] = Integer.valueOf(1);
    a[3] = Integer.valueOf(5);
    a[4] = Integer.valueOf(8);
    System.out.println("The insertion sort för comprable a array is:");
    lista.insertionSort(a);
    System.out.println(lista);}

I hope help please.

Answer 1

For iterating the elements that you get from the iterator and putting them back into the array a you need two variables: The Iterator that you get from lista.iterator() and an index into the array (an int). Initialize the index to 0. For each element that you get from the iterator put it into the array at the current index, then increment the index. In this way the elements will be stored into a[0], a[1], a[2], etc.

Edit: Have your iterator control a loop for iterating. Personally I prefer a while lopp, there are some that prefer a for loop. You will find numerous examples on both in the Internet. Use your search engine.

Edit: This line in your iterator looks wrong:

     ListNode<T> node = head.next;

It seems to me that you are initializing node to refer to the second node of your list, thus skipping the first node.

Edit: You have got two variables named lista. There’s one in your main method. And there’s another one in the insertionSort method of DoublyLinkedList. When doing your insertion sort, you are filling the numbers into the latter. After the sort you are printing the former. So don’t expect to have your sorted list printed. However if I understood correctly, the end goal was to get your array sorted. So just print it:

    System.out.println(Arrays.toString(a));

This should give you the end result.