Универсальные аргументы Java

Question

Возвращаясь к моим основным материалам ADT, чтобы подготовиться к собеседованию, и пытаюсь убить двух зайцев одним выстрелом, изучая Java, пока я нахожусь. Попытка написать простой алгоритм для сортировки слиянием с общим связанным списком (который я создаю сам). Это оказалось намного сложнее, чем я мог себе представить! Кто-нибудь может мне помочь, пожалуйста? Я начну работать над основами и буду обновлять этот пост по мере прохождения.

Мой код для общего связанного списка выглядит следующим образом:

 public class NodeList<T extends Comparable<T> > {
  private T head;
  public NodeList<T> tail;
  public NodeList( T item, NodeList<T> list ) {
    head = item;
    tail = list;
  } 

}

Я пытаюсь получить доступ к этому классу в другом классе, который я создал, а именно:

    public class MyList<T extends Comparable<T>> {

  private NodeList<T> nodes;
  private static int size;
  public MyList( ) { 
    nodes = null; 
  }

  public MyList(T[] array ){
    for( T item : array ) {
      nodes = new NodeList<T>(item, nodes); 
    }
    size = array.length;
  }


  public void add( T item ) { 
    nodes = new NodeList<T>( item, nodes ); 
    size++;
  }


  public void addEnd( T item ) {
    NodeList<T> temp = nodes;
    while ( temp == null || temp.tail != null) {
      temp = temp.tail;
    }
    size++;
    temp.tail = new NodeList<T> ( item, null);
  }

Я считаю, что до сих пор все было правильно, вплоть до методов add и addEnd, которые должны добавлять универсальный тип в начало списка и конец списка соответственно.

Мой код продолжается с:

 public static <S extends Comparable<S>>
    MyList<S> sort( MyList<S> list ) {

    if ( size > 1 ) {

      MyList<S> left  = leftHalf( list );
      MyList<S> right = rightHalf( list );
      list = merge( left, right );
    }

    return list;
  }

  private static <S extends Comparable<S>>
    MyList<S> merge( MyList<S> left, MyList<S> right ) {

  }

  private static <S extends Comparable<S>>
    MyList<S> leftHalf( MyList<S> list ) {
    MyList <S> leftSide = new MyList();
    int middle;
    if(size % 2 == 1) {
     middle = size +1;
    } else {
     middle = size; 
    }
    for ( int countToMiddle = 0; countToMiddle < middle ; countToMiddle++ ) {
      leftSide.addEnd(nodes);
    }


    // return elements from 0 .. list.size() / 2
  }

И я получаю ошибку:

addEnd (S) в MyList нельзя применить к (NodeList)

, который происходит, когда я бегу

* * 1 022 leftSide.addEnd (узлы);

Может кто-нибудь увидеть причину этого / сказать мне, если я прав до этого момента моей работы? Еще раз большое спасибо!

Answer 1

Если вы хотите, чтобы NodeList и MyList содержали только Comparable элементов, вы можете заменить общий параметр T на что-то вроде:

public class NodeList<T extends Comparable> {

Или

public class NodeList<T extends Comparable<T>> {

Изамените, где вы используете Comparable на T.Таким образом, вы знаете, что T, по крайней мере, реализует методы Comparable.

Oracle учебники для дженериков должны помочь вам освоить их.

---

Одна из проблем, с которой вы можете столкнуться, заключается в том, что вы ссылаетесь на переменные-члены из статических функций, как в leftHalf:

   for ( int countToMiddle = 0; countToMiddle < middle ; countToMiddle++ ) {
      leftSide.addEnd(nodes);
    }

nodes - это переменная-член, то есть нестатическая переменная, поэтомуВы не можете вызвать это из статических методов.В этом примере вы должны получить его из переданного MyList:

   for ( int countToMiddle = 0; countToMiddle < middle ; countToMiddle++ ) {
      leftSide.addEnd(list.nodes);
    }

И то же самое относится и к другим статическим методам, которые пытаются использовать переменные-члены.

---

Кроме того, причина, по которой вы получаете ошибку типа: addEnd(S) in MyList<S> cannot be applied to (NodeList<T>), заключается в том, что S, в соответствии с вашим параметром типа, является сопоставимым.NodeList не расширяет Comparable!

У вас есть два решения:

1. Сделайте NodeList extension Comparable таким образом, чтобы вы могли передать его в MyList.addEnd
2. Сделатьперегрузка (т. е. другой метод с тем же именем) для addEnd, который принимает NodeList и добавляет все элементы в переданном NodeList в MyList

или предлагает другое решение, которое лучше соответствует потребностямиз ваших классов.

---

Хотя я понимаю, что вы реализуете связанный список только для того, чтобы отточить свои навыки для интервью (я желаю вам удачи!), я просто хочу добавить, что есть обобщенный LinkedList уже доступен на Java.

Answer 2

Почему вы публикуете почти один и тот же вопрос дважды?Вы можете расширить свой вопрос, добавить комментарии и т. Д.

Мы уже дали вам подсказку .:)

Answer 3

Ошибка возникает из-за того, что класс NodeList не имеет конструктора, который получает универсальный класс T и NodeList. Фактически, эта реализация заменит ссылочный объект, на который ссылаются узлы в каждом цикле. Вы также должны это исправить.

Что вам нужно сделать, так это поместить T в сопоставимый объект и изменить атрибут, например:

public class NodeList<T extends Comparable> {
    private T head;
    private NodeList tail;
    public NodeList( T item, NodeList list ) {
        head = item;
        tail = list;
    }
}

Было бы лучше, если бы вы сказали нам, для чего именно этот код.