什么是鏈表？
鏈表是一種數(shù)據(jù)結(jié)構(gòu)才避，由許多稱為“節(jié)點(diǎn)”的迷你數(shù)據(jù)結(jié)構(gòu)組成橱夭。節(jié)點(diǎn)鏈接在一起形成一個(gè)列表。
整個(gè)鏈表桑逝，由3個(gè)節(jié)點(diǎn)鏈接在一起組成棘劣。
每個(gè)節(jié)點(diǎn)包含2個(gè)屬性
它的價(jià)值。這可以是任何東西：整數(shù)楞遏，字符茬暇，字符串，對(duì)象等寡喝。
指向序列中下一個(gè)節(jié)點(diǎn)的指針糙俗。
一些定義
頭節(jié)點(diǎn)：頭節(jié)點(diǎn)只是鏈表中的第一個(gè)節(jié)點(diǎn)。從上面的例子可以看出预鬓，包含'5'的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)巧骚，因此是頭部。
'尾節(jié)點(diǎn)：尾節(jié)點(diǎn)是序列中的最后一個(gè)節(jié)點(diǎn)。由于它是最后一個(gè)節(jié)點(diǎn)网缝，因此它指向null，因?yàn)樾蛄兄袥]有下一個(gè)節(jié)點(diǎn)蟋定。在上面的示例中粉臊，包含“3”的節(jié)點(diǎn)將是尾節(jié)點(diǎn)。
單身聯(lián)系與雙重聯(lián)系
在鏈接列表方面驶兜，有兩種主要類型扼仲。
那些“單獨(dú)”聯(lián)系的，以及那些“雙重”聯(lián)系的抄淑。
單獨(dú)鏈接意味著每個(gè)節(jié)點(diǎn)僅指向最多1個(gè)其他節(jié)點(diǎn)屠凶，即其前面的節(jié)點(diǎn)。這在上面的例子中展示肆资。
雙重鏈接意味著每個(gè)節(jié)點(diǎn)可以指向其他2個(gè)節(jié)點(diǎn)矗愧，前面的節(jié)點(diǎn)和它后面的節(jié)點(diǎn)。正如我們從下面的例子中可以看到的那樣郑原，由于頭節(jié)點(diǎn)之前沒有節(jié)點(diǎn)（即5）唉韭，因此其中一個(gè)指針指向null。
代碼是如何工作的呢犯犁？
編碼鏈接列表可能是4行問題或400行問題属愤。這取決于你想要如何接近它。
在最簡(jiǎn)單的層面上酸役，就像我們討論的那樣住诸，鏈表只是一堆連接的節(jié)點(diǎn)。
因此涣澡，我們真正需要?jiǎng)?chuàng)建此結(jié)構(gòu)的只是一個(gè)節(jié)點(diǎn)對(duì)象贱呐。
class linkedListNode:
def __init__(self, value, nextNode=None):
self.value = value
self.nextNode = nextNode
在這里我們可以看到我們只是創(chuàng)建了一個(gè)具有value和nextNode屬性的類。
要?jiǎng)?chuàng)建節(jié)點(diǎn)暑塑，我們只需傳入一個(gè)值吼句。
node1 = linkedListNode("3") # "3"
node2 = linkedListNode("7") # "7"
node3 = linkedListNode("10") # "10"
在這里，我們創(chuàng)建了3個(gè)單獨(dú)的節(jié)點(diǎn)事格。
下一步就是將它們連接在一起惕艳。
node1.nextNode = node2
node2.nextNode = node3
上面的第一行使node1指向node2：
“3”→“7”
上面的第二行使node2指向node3：
“7”→” 10"
總之，我們留下了一個(gè)鏈接列表驹愚，如下所示：
“3”→” 7" →” 10" →null
注意：“10”指向null远搪，因?yàn)闆]有為node3分配nextNode，并且默認(rèn)的nextNode為Null逢捺。
就像我之前提到的谁鳍，有很多不同的方法可以做到這一點(diǎn)。這只是最簡(jiǎn)單的。
遍歷鏈接列表
如果您正在進(jìn)行編程訪談倘潜，并且您會(huì)收到鏈接列表問題绷柒，那么您將無法獲得所有節(jié)點(diǎn)。
所有你得到的是頭節(jié)點(diǎn)涮因。
從該頭節(jié)點(diǎn)废睦，您必須獲得列表的其余部分。
首先讓我們了解如何從Python中的節(jié)點(diǎn)獲取值和nextNode养泡。
假設(shè)我們有一個(gè)名為'node'的節(jié)點(diǎn)嗜湃。
獲取節(jié)點(diǎn)的值：
node.value
獲取節(jié)點(diǎn)的nextNode：
node.nextNode
Traversal
我們要做的第一件事就是創(chuàng)建一個(gè)名為“currentNode”的變量來跟蹤我們所處的節(jié)點(diǎn)。我們首先想要將它分配給我們的頭節(jié)點(diǎn)澜掩。
currentNode = head
現(xiàn)在我們要做的就是檢查當(dāng)前節(jié)點(diǎn)是否為Null购披。如果不是，我們將'currentNode'等于'currentNode'的'nextNode'肩榕。
currentNode = node1
while currentNode is not None:
currentNode = currentNode.nextNode
假設(shè)我們有以下鏈接列表：“3”→“7”→“10”刚陡。
我們的頭和第一個(gè)'currentNode'是“3”。
當(dāng)我們這樣做
currentNode = currentNode.nextNode
我們將'currentNode'重新分配給當(dāng)前節(jié)點(diǎn)的鄰居株汉，在這種情況下是“7”橘荠。
這將繼續(xù)，直到currentNode指向None郎逃，在這種情況下循環(huán)停止哥童。
這是在Python中遍歷鏈表的基本方法。
鏈接到Github上的代碼褒翰。
插入元素
將元素插入鏈接列表時(shí)贮懈，除非另有說明，否則將其插入后面优训。
我們使用以下示例：
“3”→” 7" →” 10" →空
假設(shè)我們要插入一個(gè)“4”朵你。
我們只需找到尾節(jié)點(diǎn)，在本例中為“10”揣非，并將其nextNode設(shè)置為“4”節(jié)點(diǎn)抡医。
“3”→” 7" →” 10" →‘4’→null
node4 = linkedListNode("4")
node3.nextNode = node4
假設(shè)我們?cè)谝粋€(gè)訪談中，我們只有head節(jié)點(diǎn)早敬。我們只需遍歷LinkedList即可找到尾部忌傻。一旦我們得到尾部，我們只需將其nextNode設(shè)置為我們創(chuàng)建的新節(jié)點(diǎn)搞监。
def insertNode(head, valuetoInsert):
currentNode = head
while currentNode is not None:
if currentNode.nextNode is None:
currentNode.nextNode = linkedListNode(valuetoInsert)
return head
currentNode = currentNode.nextNode
刪除元素
刪除可能會(huì)有點(diǎn)棘手水孩。
我們來看同樣的例子。
“3”→” 7" →” 10" →null
如果我們想要?jiǎng)h除“7”琐驴，我們需要做的就是將“3”指向“10”俘种，以便永遠(yuǎn)不會(huì)引用“7”秤标。
“3”→” 10" →null
要做到這一點(diǎn)，我們必須遍歷列表宙刘，同時(shí)不僅要跟蹤currentNode苍姜，還要跟蹤previousNode。
我們還必須考慮頭節(jié)點(diǎn)是我們想要?jiǎng)h除的節(jié)點(diǎn)悬包。
在下面的代碼中怖现，我們只刪除要?jiǎng)h除的值的第一個(gè)實(shí)例。
請(qǐng)注意玉罐，有很多方法可以實(shí)現(xiàn)這一點(diǎn)，下面的解決方案可能不是您生活中最清晰的代碼潘拨。然而吊输，在采訪的熱度中，面試官可能不會(huì)期望教科書完美的代碼铁追。
def deleteNode(head, valueToDelete):
currentNode = head
previousNode = None
while currentNode is not None:
if currentNode.value == valueToDelete:
if previousNode is None:
newHead = currentNode.nextNode
currentNode.nextNode = None
return newHead # Deleted the head
previousNode.nextNode = currentNode.nextNode
return head
previousNode = currentNode
currentNode = currentNode.nextNode
return head # Value to delete was not found.
在上面的代碼中季蚂，一旦我們找到要?jiǎng)h除的節(jié)點(diǎn)，我們將前一節(jié)點(diǎn)的“nextNode”設(shè)置為已刪除節(jié)點(diǎn)的“nextNode”琅束，以將其完全從列表中刪除扭屁。
大O時(shí)間復(fù)雜性分析
注意這些是上述節(jié)點(diǎn)結(jié)構(gòu)的時(shí)間復(fù)雜性，最有可能出現(xiàn)在訪談中涩禀。在實(shí)際情況中料滥，您可以將屬性存儲(chǔ)在LinkedList類中以降低這些復(fù)雜性。
'n'=鏈接列表中的元素?cái)?shù)量艾船。
插入到鏈接列表的后面 -我們遍歷所有n個(gè)元素以找到尾部并插入我們的新節(jié)點(diǎn)葵腹。O(n)
插入鏈接列表的前面 -?我們只需創(chuàng)建新節(jié)點(diǎn)并將其nextNode設(shè)置為head。無需遍歷列表屿岂。O（1）
遍歷 - ?我們遍歷所有n個(gè)元素践宴。O(n)
刪除 -?最糟糕的情況是，我們刪除的節(jié)點(diǎn)是最后一個(gè)節(jié)點(diǎn)爷怀，導(dǎo)致我們遍歷整個(gè)列表阻肩。O(n)
現(xiàn)在您已經(jīng)掌握了處理鏈表面試問題所需的基本知識(shí)!
