Написание метода size() для определяемого пользователем класса стека (связанный список)

Question

Я создаю свою собственную общую структуру данных стека, используя связанный список в качестве основы для нее, но мне нужно сделать размер() метод, аналогичный методу встроенного размера для стеков. Я не уверен, как это сделать со структурой Linked List?

public class LLStack<T> implements StackInterface { 
private class ListNode 
{ 
    private T data; 
    private ListNode link; 
    public ListNode(T aData, ListNode aLink) 
    { 
     data = aData; 
     link = aLink; 
    } 
} 
private ListNode head; 
public LLStack() 
{ 
    head = null; 
} 
public void push(Object data) 
{ 
    ListNode newNode = new ListNode((T)data, head); 
    head = newNode; 
} 
public T pop() 
{ 
    if(head == null)//Empty stack 
     return null; 
    T retVal = head.data; 
    head = head.link; 
    return retVal; 
} 
public T peek() 
{ 
    if(head == null) 
     return null; 
    else 
     return head.data; 
} 
public void print() 
{ 
    ListNode temp = head; 
    while(temp != null) 
    { 
     System.out.println(temp.data); 
     temp = temp.link; 
    } 
} 
public int size() { 

} 

Answer 1

Это в основном то же самое, что и метод печати.

public int size() 
{ 
    ListNode temp = head; 
    int size = 0; 
    while(temp != null) 
    { 
     size += 1; 
     temp = temp.link; 
    } 
    return size; 
} 

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

Answer 2

Как это:

Держите переменную величину в классе:

public class LLStack<T> implements StackInterface { 
{ 
    private int size; 
.... 

В вашем нажимной и попе-метода, увеличение/уменьшение размера:

public void push(Object data) 
{ 
    ListNode newNode = new ListNode((T)data, head); 
    head = newNode; 
    size ++; 
}  
public T pop() 
{ 
    if(head == null)//Empty stack 
     return null; 
    size --; 
    T retVal = head.data; 
    head = head.link; 
    return retVal; 
} 

Тогда имеет ПОЛУЧАЕТ размер:

public int getSize() 
{ 
    return size; 
} 

Answer 3

Есть два простых способа сделать то, что вы хотите:

1. Count списка, делая из конца в конец обхода каждый раз, когда метод вызывается. Это будет медленным, и я бы не рекомендовал его за пределами иллюстративного примера. Таким образом, вам не нужно хранить размер в поле:

   public int size() { 
       ListNode current = head; 
       int count; 
       for(count = 0; current != null; count++) 
        current = current.link; 
       return count; 
   } 
   

2. Намного лучше было бы просто сохранить счет как частное поле. Метод size бы просто быстро геттер:

   public int size() { return this.count; } 
   

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

   public LLStack() { 
       this.head = null; 
       this.count = 0; 
   } 
   
   public void push(T data) { 
       ... 
       this.count++; 
   } 
   
   public T pop() { 
       ... 
       this.count--; 
       return retval; 
   }