java - 如何对单向链表实现 "add"方法？

Question

这是类头及其下面的字段:

public class SinglyLinkedList <E> implements MiniList <E> 
{
   protected Entry <E> head = null;

   private int size = 0; 

我需要为我的实验室实现此方法，但我对 LinkedLists 一无所知:

   public boolean add(E element) 
   {

         //method should return true once element is added

         //EDIT: I THINK I SOLVED IT:
         head.element = element;
         return true;

         //Does everyone think the two lines above look correct?
   }

问题非常简单，我对非随机访问数据结构非常陌生。有人可以帮我解决上面的问题吗？我需要一个基础，以便我可以继续实验室的其余部分。

Answer 1

嗯，链接列表的工作原理如下:

你有头节点，它有对下一个节点的引用，下一个节点有对下一个节点的引用，等等。这是我刚刚画的图:

头部有对以下节点的引用，但它也有数据。因此，如果我创建一个字符串链接列表。

LinkedList<String> groceryList = new LinkedList<String>();
groceryList.add("VEGGIES");
groceryList.add("FRUITS");

头部有数据 VEGGIES，然后还有对列表中下一个对象的引用，换句话说就是 FRUITS 项，这也是尾部。

假设我们的列表是空的。没有头，没有尾，没有数据。我们将我们的头部分配为一个新条目。它将是列表中的第一个元素，也是我们访问列表的门户。如果列表不为空，为了添加到列表中，我们必须访问列表中当前的最后一个元素。为此，我们必须沿着列表向下移动。

//Some Pseudo Code
Entry current = head;
Entry last = null;
while(Not Done Looping)
{
    Entry temp = current.getNext();
    if(temp is not null) //We have a reference to another element
    {
        //We have more list to see
        current = temp;
    }
    else
        last = current;
}

这将为我们提供最后一个条目。然后，为了添加另一个元素，我们只需将最后一个对象的引用设置为我们尝试添加的 Entry。

这就是它工作原理的要点。现在您只需根据您的“Entry”对象来实现即可。