哪種方式最好是寫一個單向鏈表

我看到2個YouTube視頻顯示，在年底方法，例如哪種方式最好是寫一個單向鏈表

public void insertFirstLink(String bookName, int millionsSold) { 
     Link newLink = new Link(bookName, millionsSold); 
     newLink.next = firstLink; 
     firstLink = newLink; 
    }

這看起來非常乾淨的一個附加的補充方法，但我通過另一個教程，做去這

public void insert(int x) { 
     if (head == null) { 
      head = new Node(x, head); 
     } else { 
      Node current = head; 

      while (current.getNext() != null) { 
       current = current.getNext(); 
      } 
      Node newNode = new Node(x, null); 
      current.setNext(newNode); 
     } 
    }

爲什麼我會使用第二個，因爲它更長，遍歷列表只是爲了增加到最後。我對鏈接列表很陌生，對於爲什麼有這麼多人用不同的方式寫它，我感到困惑，我看到的每個教程都使用了不同的技巧。我主要學習這個能夠回答面試問題，所以我需要了解所有的可能性。

我也不清楚'head/current/first'節點是什麼。在教程中他提到head是第一個添加的節點，併成爲下一個添加的節點，因此最終「頭」節點是最後一個節點的權利？當他印刷他的名單時，情況正好相反。

來源

2014-01-28 gallly

這兩種方法做的不一樣。第一個插入新元素的第一個位置，第二個將其添加到最後。 – user14325

第一種方法在當前位置插入一個節點（它看起來像是指向列表末尾的指針）。第二個在末尾插入一個節點，但不保留尾指針，所以它必須首先遍歷列表直到找到結束節點，然後將新節點放在那裏。

第一個版本還是第二個版本「更正確」更符合您的特定軟件要求。他們都是正確的;他們只是以不同的方式做同樣的事情。雖然這個例子看起來特別微不足道，但當你試圖在跳過列表和二叉樹之間進行選擇時，它並不是微不足道的。

來源

2014-01-28 18:12:52

firstLink是根據教程添加的第一個節點或最後一個節點，這讓我感到困惑。如果我添加10個節點，那麼firstLink將是我相信的第10個位置。從這個意義上說，它總是增加到最後是不是？當你說外部狀態，你是什麼意思，你的意思是方法是分開的節點，而不是分開的LinkedList類保持'頭'位置 – gallly

是的;你是對的;我對我的答案做了一些修改。 –

謝謝，我仍然沒有100％完成但接近。無論有什麼權利，他們兩個都加入到列表的「結尾」中？如果一個採訪者要求我採取加法結束的方法，那麼兩者都可以接受？我不明白爲什麼你說第一種方法增加了當前位置，不是當前位置總是會成爲最後一個位置，因爲頭部的值是最後一個增加的值。這是90％的人如何寫它？ – gallly

第二種做事方式的原因是，通常假定add方法將元素放在列表的末尾。如果您使用ArrayList和LinkedList進行遊戲，您會看到按照它們添加的順序打印元素。 ArrayList和LinkedList的行爲方式非常重要。

優化第二段代碼的一種方法是存儲一個指向列表尾部的指針以及一個指向頭部的指針，這樣adds和pushes都需要O（1）次。但是，如果在您的數據結構中排序並不重要，那麼您應該使用第一種方法。爲了澄清，對於「添加」，您必須使用第二種方法（或某種變體）才能成爲增加，而對於「推送」，您必須使用類似於第一種方法;但沒有理由你的班級不能兼得。

來源

2014-01-28 18:19:08 acbabis

@CatznDogz我認爲在你的代碼中，鏈接和節點的用途相同，只是名稱不同。如果節點有一個add方法，這意味着Node類包含一些邏輯。這對於列表不是必需的，但可能對樹或更復雜的數據結構有幫助。你的第二個代碼示例只是在Node上使用getter和setter，與get方法不同。 getter和setter通常被認爲是Java中的良好實踐（正如我相信你知道的那樣），但在私有內部類中使用較少。希望有所幫助。 – acbabis

感謝它幫助 – gallly

哪種方式最好是寫一個單向鏈表

回答

相關問題