[Powered by Google Translate] 在編程中，我們經常需要代表值列表，
如學生的名字，在一節
或最新的測驗分數。
>> 在C語言中，宣布陣列可以使用
存儲列表。
這很容易列舉的元素的列表
存儲在數組中，如果你需要訪問
或修改第i個列表元素
一些任意的索引，我，
在固定時間內，可以做
但數組，也有缺點。
>> 當我們聲明，我們需要說
前面他們有多大，
那就是，它們可以存儲多少個元素
有多大，這些元素是，這是由它們的類型。
例如int ARR（10）
可存儲10個項目
是一個int的大小。
>> 我們不能改變數組的大小後聲明。
我們有一個新的數組，如果我們要存儲更多的元素。
存在這種限制的原因是，我們的
程序存儲整個陣列
作為一個連續的內存塊。
之所以這樣說，是我們的緩衝區，存儲在數組中。
可能還有其他變數
位於旁邊的陣列
在內存中，所以我們不能
只要大的陣列。
>> 有時，我們希望貿易陣列的快速數據存取速度
多一點靈活性。
輸入的鏈接列表，另一個基本的數據結構
你可能不熟悉。
在較高的水平，
一個鍊錶，將數據存儲在一個節點序列
彼此連接的鏈接，
故名鍊錶。
正如我們將要看到的，這兩種不同的設計
導致不同的優點和缺點
不是一個數組。
>> 這裡有一個非常簡單的整數鍊錶的C代碼。
你可以看到，我們代表每一個節點
列表中的一個結構，其中包含兩件事情，
一個整數來存儲被稱為“值”
和一個鏈接到列表中的下一個節點
我們所代表的被稱為“下一個指針。
這樣一來，我們就可以跟踪整個列表
只是一個單一的指針的第一個節點，
那麼我們可以按照下面的指針
到的第2節點，
到第3節點，
到第四節點，
依此類推，直到我們得到到年底的列表。
>> 您可能能夠看到1的優勢有
在靜態數組結構 - 一個鍊錶，
我們完全不需要一個大的內存塊。
列表中的第一個節點，可以住在這個地方在內存中，
和第二個節點可能是所有來這裡的路上。
我們可以得到的所有節點，不管他們是在內存中，
因為開始的第一個節點，每個節點的next指針
告訴我們到底去哪裡下。
>> 此外，我們並沒有說前
多大的鏈接列表將是我們做事的方式與靜態數組，
因為我們可以將節點添加到列表
只要存在的空間，在內存中的新節點的某個地方。
因此，鍊錶是很容易的動態調整大小。
再說了，在後面的程序中，我們需要添加更多的節點
進入我們的名單。
要插入一個新的節點，進入我們的名單上的蒼蠅，
所有我們需要做的是該節點分配內存，
撲通中的數據值，
然後將其放置在這裡我們要通過調整相應的指針。
>> 例如，如果我們想在兩者之間放置一個節點
第二和第三個節點的列表，
我們將不會有第二或第三個節點。
假設我們將這個紅色節點。
我們必須做的是設置新節點的next指針
指向到第三節點的
然後重新連接第二個節點的next指針
以指向我們的新節點。
因此，我們可以調整我們的名單上飛
因為我們的計算機不依賴於索引，
而是在連接使用指針來存儲它們。
>> 然而，一個缺點鍊錶
是，不同於靜態數組，
計算機不能就直接跳到中間的列表中。
由於電腦已訪問鏈接列表中的每個節點
去下一個，
這將需要更長的時間才能找到一個特定的節點
會比在一個數組中。
要遍歷整個列表，需要一定的時間成正比
的列表的長度，
或O（n）的漸近符號。
平均而言，達成任何節點
還需要一定的時間正比於n。
>> 現在，讓我們寫一些代碼
與鍊錶。
比方說，我們希望有一個鍊錶的整數。
我們可以在我們的名單再次表示節點
作為一個結構與2個字段，
一個整數值，被稱為“值”
和下一個列表中的下一個節點的指針。
好了，似乎很簡單。
>> 比方說，我們要編寫一個函數，
遍歷列表，並打印出
的列表中的最後一個節點中存儲的值。
好了，這意味著我們需要遍歷所有的節點列表中的
找到最後一個，但因為我們沒有加入
或刪除任何東西，我們不希望改變
的內部結構的列表中的下一個指針。
>> 所以，我們需要一個指針，專門為穿越
我們稱之為“履帶”。
將抓取的所有元素的列表
通過鏈中的下一個指針。
我們所儲存的第一個節點是一個指針，
或'頭'之列。
頭部穴位的第一個節點。
這類型的指針節點。
>> 為了獲得實際的列表中的第一個節點，
我們必須取消引用此指針，
但在此之前，我們可以取消對它的引用，我們需要檢查
如果指針為空第一。
如果它是空的，該列表是空的，
我們應該打印出的信息，因為列表是空的，
有沒有最後一個節點。
但是，讓我們說，名單是不是空的。
如果不是的話，那麼我們就應該抓取整個列表
直到我們得到的最後一個節點的列表，
以及如何，我們可以說，如果我們正在尋找在列表中的最後一個節點？
>> 那麼，如果一個節點的next指針為null，
我們知道我們在年底
自上頁下頁指針沒有指向列表中的下一個節點。
這是很好的做法，要始終保持最後一個節點的next指針初始化為null
擁有一個標準化的屬性，它提醒我們，當我們的名單已經走到了盡頭。
>> 所以，如果履帶式→下是空的，
請記住，箭頭語法的快捷方式提領
一個指向結構的指針，然後訪問
它的下一個字段的尷尬：
（履帶式）。下。
一旦我們找到的最後一個節點，
我們要打印的履帶式→值，
當前節點的值中的
我們知道這是最後一次。
否則，如果我們還沒有在列表中的最後一個節點，
我們必須移動到列表中的下一個節點
和檢查，如果這是最後一個。
要做到這一點，我們剛剛成立我們的抓取工具指針
指向當前節點的下一個值，
即，在列表中的下一個節點。
這是通過設置
履帶式履帶式→下。
然後，我們重複這個過程，例如循環，
直到我們找到的最後一個節點。
所以，舉例來說，如果履帶指著頭，
我們設置履帶式履帶式→下，
這是相同的第1節點的下一個字段。
所以，現在我們的抓取工具是指向第二個節點，
，並再次重複這個循環，
直到我們發現的最後一個節點，那就是，
節點的next指針指向空。
在那裡我們擁有它，
我們發現在列表中的最後一個節點，打印其值，
我們只是使用履帶→VAL。
>> 穿越並沒有那麼糟糕，但插入呢？
比方說，我們要到第4個位置插入一個整
在一個整數列表。
這是當前的第3次和第4節點之間。
同樣，我們要遍歷列表
到第三個元素，我們要插入後。
所以，我們創建了一個履帶式指針，再次遍歷列表，
檢查我們的頭指針為空，
如果不是的話，我們的抓取工具在頭節點的指針指向。
因此，我們的第一個元素。
我們必須前進之前，我們可以將更多的元素，
所以我們可以使用一個for循環
i = 1; i <3的我+ +
以及在每個循環迭代中，
1個節點的指針向前推進我們的抓取工具
通過檢查，如果當前節點的下一個字段是空的，
，如果不是的話，我們的抓取工具指針移動到下一個節點
通過設置它等於當前節點的next指針。
所以，既然我們的for循環中說，要做到這一點
兩次，
我們已經達到了第三個節點，
一旦我們的抓取工具指針到達節點後，
我們要插入新的整數，
我們如何真正插入呢？
>> 那麼，我們的新的整數被插入到列表中
作為其自身節點結構的一部分，
因為這是真正的節點序列。
所以，讓我們做一個新的指針節點
被稱為“new_node，”
並將其設置為指向的內存，我們現在分配
在堆中的節點，
我們需要分配多少內存？
那麼，一個節點的大小，
我們要設置其VAL領域，我們要插入的整數。
比方說，6。
現在，節點中包含的整數值。
這是很好的做法，初始化新節點的下一個字段
指向NULL，
但現在該怎麼辦呢？
>> 我們必須改變列表的內部結構的
和包含在列表的現有的下一個指針
第3和第4個節點。
由於下一個指針確定的名單順序，
而且因為我們要插入的新節點
到中間的列表中，
它可以是一個有點棘手。
這是因為，記住，我們的電腦
只知道在列表中的位置的節點
因為存儲在以前的節點的下一個指針。
所以，如果我們失去了這些位置的跟踪，
說通過改變在列表中的下一個指針之一，
例如，假設我們改變
第三個節點的下一個字段
指向某些節點在這裡。
我們很運氣，因為我們不會
有任何想法在哪裡可以找到，其餘的名單，
這顯然非常糟糕。
因此，我們必須非常小心的順序
在我們操作插入時，我們的下一個指針。
>> 因此，為了簡化這一點，讓我們說，
我們的第一個節點
被稱為A，B，C，和D，用箭頭表示的指針的鏈
連接節點。
因此，我們需要將我們的新節點
在節點C和D之間的
它的關鍵在正確的順序做了，我會告訴你為什麼。
>> 讓我們來看看在錯誤的方式來做到這一點。
嘿，我們知道新的節點來右後C，
所以，讓我們來設置C的指針
指向new_node。
好吧，看起來沒問題，我們就必須完成現在
新節點的next指針指向D，
但等待，我們能做到這一點嗎？
唯一能告訴我們其中D，
以前是下一個指針存儲在C，
但我們只是重寫了該指針
以指向新的節點，
因此，我們不再有任何線索，其中D是在內存中，
我們已經失去了休息的列表。
都不好。
>> 那麼，我們該怎麼做是正確的？
首先，指向新節點的next指針D.
現在，新的節點和C的next指針
都指向同一個節點上，D，
但罰款。
現在，我們可以在新的節點C的下一個指針指向。
因此，我們已經做到了這一點，而不會丟失任何數據。
在代碼中，C是當前節點
遍歷指針履帶式指向，
和D表示的由當前節點的下一個字段指向的節點，
或履帶→下一步。
因此，我們首先設置新節點的next指針
履帶式→下，
我們說，new_node的下一個指針應該以同樣的方式
在圖中，指向D。
然後，我們可以設置當前節點的next指針
我們的新節點，
就像我們不得不，等待到C點在繪圖new_node。
現在一切都在秩序，我們並沒有失去
跟踪的任何數據，我們能夠公正
堅持我們的在中間的列表中的新的節點
不重建整個事情的情況下，甚至轉移的任何元素
的方式，我們將不得不與一個固定長度的陣列。
>> 因此，鍊錶是一個基本的，但重要的是，動態​​的數據結構
有優點也有缺點
陣列和其他數據結構相比，
和通常情況下在計算機科學，
重要的是要知道何時使用每個工具，
所以你可以選擇合適的工具，合適的工作。
>> 更多的練習，嘗試寫功能
從鍊錶中刪除節點 -
記得要小心的順序重新排列
你的下一個指針，以確保您不會失去一大塊您的列表 -
或一個函數來計算一個鍊錶中的節點，
一個有趣的，以扭轉在一個鍊錶中的所有節點的順序。
>> 我的名字是傑克遜施泰因坎普，這是CS50。