элемент по индексу в круговом связанном списке

Question

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

public int elementAt(int index){ 
     if(index>size){ 
      return -1; 
     } 
     Node n = head; 
     while(index-1!=0){ // this line is unclear for me 
      n=n.next; 
      index--; 
     } 
     return n.data; 
    } 

Я хотел бы написать один и тот же код, но таким образом:

public int elementAt(int index){ 
     if(index>size){ 
      return -1; 
     } 
     Node n = head; 
     while(n.size != index){ // here is my change in the code 
      n=n.next; 
     } 
     return n.data; 
    } 

Вот весь код: http://algorithms.tutorialhorizon.com/circular-linked-list-complete-implementation/

Могу ли я делать прямо во втором коде?

Thanks

Answer 1

это просто счет. Вы можете сделать это по-разному. Я предполагаю, что размер является размером вашего LinkedList. В этом случае ваш код неверен. вы можете сделать, как следующая

public int elementAt(int index){ 
     if(index>size){ 
      return -1; 
     } 
     Node n = head; 
     int i = 0; // zero-indexing 
     while(i++ != index){ // you can increment i at the end too 
      n=n.next; 
     } 
     return n.data; 
    } 

первый код также рассчитывает, но вместо того, чтобы использовать другую переменную она использовала существующий

Answer 2

Пример кода использует индекс 1 на основе: с 1, 2, 3,. .., размер. Что странно в информатике, где можно было бы ожидать: 0, .., size-1.

К сожалению, size является собственностью полного списка, а не один узел в списке. Поэтому их решение в порядке.

Хотя, когда индекс < = 0, тогда приятные вещи случаются.

---

Для реального списка круговой узел имеет previous поле. И последний узел связан двумя способами с первым узлом.

В этом случае вы можете ходить в обоих направлениях, следуя next или previous. Тогда, когда индекс < размер/2 можно было бы на next перейти к индексу, а также вернуться на previous для шагов (размер - индекс). Чтобы выполнить меньшее количество шагов.

Answer 3

Линия, которую вы не понимаете, это просто подсчет «индексных» позиций fordward, и она начинается с головы. Таким образом, метод возвращает вам элементы «индекс-1» из элемента головки. . Другое предположение состоит в том, что элемент головки находится в 1