Как найти первое значение в связанном списке?

Question

У меня есть связанный список, который мне дали, и мне нужно найти первое значение в списке с помощью метода getFirst. Мне нужно отобразить сообщение об ошибке и выйти из программы, если значение равно нулю.Связанный список уже дал мне ссылку так:

class MyLinkedList
{
   private class Node            // inner class
   {
      private Node link;
      private int x;
   }
   //----------------------------------
   private Node first = null;    // initial value is null
   //----------------------------------
   public void addFirst(int d)
   {
      Node newNode = new Node(); // create new node
      newNode.x = d;             // init data field in new node
      newNode.link = first;      // new node points to first node
      first = newNode;           // first now points to new node
   }
   //----------------------------------
   public void traverse()
   {
     Node p = first;
      while (p != null)            // do loop until p goes null
      {
         System.out.println(p.x);  // display data
         p = p.link;               // move p to next node
      }
   }
}
//==============================================
class TestMyLinkedList
{
   public static void main(String[] args)
   {
      MyLinkedList list = new MyLinkedList();
      list.addFirst(1);
      list.addFirst(2);
      list.addFirst(3);
      System.out.println("Numbers on list");
      list.traverse();
   }
}

Вот что я опробовал для метода:

 public static Node getFirst(Node list)
  {
    if (list == null)
    {
      System.out.println("Error!");
      System.exit(1);
    }
    return MyLinkedList.first;
  }

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

Answer 1

Класс MyLinkedList в вашем вопросе следует структуре структуры данных стека (в то время, когда я пишу этот ответ).То есть: каждый раз, когда вы добавляете новый элемент, новый элемент заменяет ранее добавленный элемент в качестве первого элемента.

Я думаю, вы хотите получить 1 в качестве первого элемента, если вы добавили элементы 1, 2, 3 в таком порядке.Поправьте меня, если я ошибаюсь.

В этом случае ваш связанный список и его поиск должны быть такими:

(Примечание: я избежал private vars, public геттер, установщик и т. д .; чтобы код был легко читаемым. Но читатели должны добавить их.)

class Node{ int x; Node next; }

class LinkedList
{ Node head,tail;
  void add(int y)
  { Node node = new Node();
    node.x=y;
    if(head==null)
      head = tail = node;
    else
      tail = tail.next = node;
  }
  int getFirst()
  { if(head!=null)
      return head.x;
    else
      throw new java.util.NoSuchElementException("List is empty");
  }
}

Если вы посмотрите на java.util.LinkedList, вы найдете методы, которые обычно используются в связанных списках,Если это не домашнее задание, тогда я предлагаю вам не изобретать велосипед.Просто используйте существующие библиотеки.

Если вам нужно использовать структуру данных стека, и вы не можете ее изменить, тогда я предлагаю вам изменить getFirst() следующим образом:

  int getFirst()
  { if(tail!=null)
      return tail.x;
    else
      throw new java.util.NoSuchElementException("List is empty");
  }

Если вам не разрешено добавлять Node tail в ваш код, тогда ваш getFirst() будет выглядеть следующим образом:

  int getFirst()
  { if(head==null)
      throw new java.util.NoSuchElementException("List is empty");
    Node node = head;
    while(node.next!=null)
      node=node.next;
    return node.x;
  }

Answer 2

Вы должны проверить, что first не null, чтобы сделать то, что вы описываете в вопросе.Кроме того, довольно странно, что первый узел сам ссылается на себя, потому что обычно он остается нулевым, пока вы не добавите другой узел

Answer 3

обратите внимание, что первое значение связано с первым Node с помощью null.Затем вы должны проверить две вещи

1. Node == null (вы получили это)
2. Node.next == null (вы должны сделать это)

КогдаNode.next == null.Это означает, что Node является первым значением, потому что оно связано с начальным Node с помощью null.

Тогда у вас есть

public static Node getFirst(Node list)
{
    // if the list is empty
    if (list == null)
    {
      System.out.println("Error!");
      System.exit(1);
    } else if(list.link == null) {
      // this is the first value!
      return list;
    } else {
    // keep searching recursive with the next Node
    return getFirst(list.link);
    }
}

Answer 4

Я думаю, вы должны взглянуть на https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html и получить представление о поведении связанного списка изначально.Как только у вас появится представление о его поведении, вы можете подумать о том, как добавить к нему функциональность.Прямо сейчас у вас есть только один метод, который вы вызываете больше, чем нужно.Также может помочь создание интерфейса и его документирование, чтобы вы знали, что должен делать каждый метод.