контроль методов push и pop в реализации связанных списков

Question

Я читал о реализации дерева в языке Java с помощью eclipse ... Я нашел методы push и pop, которые необходимо реализовать ... Вот два метода, реализованных моим учитель:

public class LimitedStack<E> { 
    private Node<E> first; // refererar till första elementet i listan 
    private Node<E> last; // refererar till sista elementet i listan 
    private int size; // antal element i listan 
    private int maxSize; // maximalt antal tillåtna element i listan 

    public LimitedStack(int maxSize) { 
     first = last = null; 
     size = 0; 
     this.maxSize = maxSize; 
    } 

    public void push(E x) { 
     Node<E> n = new Node<E>(x); 
     if (first == null) {//no overflow in this case 
      first = n; 
      size++; 
     } else { // add new node to front 
      n.next = first; 
      first = n; 
      if (size == maxSize) { //overflow, at least two elements 
       Node<E> p = first; 
       while (p.next.next != null) { //lookup second last 
        p = p.next; 
       } 
       p.next = null; //remove last from list 
      } else { //no overflow, increase size 
       size++; 
      } 
     } 
    } 

    public E pop() { 
     if (size == 0) { 
      return null; 
     } 
     E temp = first.element; 
     first = first.next; 
     size--; 
     return temp; 
    } 
} 

Когда я реализовал эти методы сам я так:

public void push(E x) { 
    if(first == null) { 
     first = new Node<E>(x); 
    } else if (size==maxSize) { 
     Node<E> act = first; 
     last =null; 
     first = new Node<E>(x); 
     first.next=act; 
    } else { 
     Node<E> act = first; 
     first = new Node<E>(x); 
     first.next=act; 
    } 
    size++; 
} 


public E pop() { 
    if(size == 0) { 
     return null; 
    } else { 
     Node<E> act = first; 
     first = act.next; 
     return act.element; 
     size--; 
    } 
} 

Является ли моя реализация правильно, если мы сравним его с ответом моего учителя?

Thanks

Answer 1

Неправильно.

В push() вы разделили его на 3 состояния.

1. Связанный список пуст
2. Связанный список полный
3. Связанный список не пустой и не полный

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

В вашем коде вы не удаляли последний элемент. Вы установите для последнего значение null , но вы никогда не устанавливаете последнее значение для правильного значения вместо нуля. И size связанного списка все еще увеличивается, потому что вы положили size++ за пределы if else.

Так что ваш код push() хотел бы это:

public void push(E x) { 
    Node<E> newNode = new Node<E>(x); 
    if(first == null) { 
     first = newNode; 
     size++; 
    } else if (size==maxSize) { 
     Node<E> act = first; 
     // last =null; 
     first = newNode; 
     first.next=act; 
    } else { 
     Node<E> act = first; 
     first = newNode; 
     first.next=act; 
     size++; 
    } 
} 

И ваш pop() функцию. Вы действительно можете видеть, что ваш код очень похож на учителя. Однако вам нужно поставить size--; перед вашим return act.element;, потому что когда метод выполняет оператор return, он в основном выйдет из метода и вернется к вызывающему абоненту, по крайней мере, в ваш код.

---

Как @SashaSalauyou говорит, что это не дерево, это просто связный список прямо сейчас, и вы должны, по крайней мере, написать некоторые test codes ваши push() и pop(), чтобы увидеть, если ваш связанный список является правильным или нет. Например, вы можете попытаться нажать некоторые значения и поместить некоторые значения в свой main и использовать отладчик, чтобы проверить, что связанный список работает правильно или нет.

Answer 2

Нет, это неправильно. Вы уменьшаете размер после утверждения return в функции pop.