What is a linked list?什么是链表？

Boxes that hold hands. Each one knows only where the next one is.手拉手的一串盒子，每个只知道自己右边是谁。

Short answer先给答案A linked list is boxes joined by pointers: each node keeps a value and where the next node is. You cannot jump, you walk. Inserting is O(1) once you stand there; finding that place is O(n).链表是用指针串起来的盒子：每个节点存一个值和下一个节点的位置。不能跳，只能顺着走。已经站在那一点时插入是 O(1)，但找到那一点要 O(n)。

Basics基础data structure数据结构O(1) insert插 O(1)

01The idea先有一个画面

Think of it like this先这样想A treasure hunt. The first note says “the next note is under the tree”. The second says “the next note is in the kitchen”. To get to the third note, you must read the first and the second. There is no number to jump to.寻宝游戏：第一张纸条写“下一张在树下”，第二张写“下一张在厨房”。想到第三张，必须先读第一张、再读第二张。没有编号可以直接跳。

A linked list is that chain of notes. Each box is a node. A node holds:链表就是这一串纸条。每个盒子叫 node（节点），里面装两样东西：

the value值（要存的东西）
the pointer to the next node指向下一个节点的指针

10→20→30→ null

Three nodes. The last one points to null — “nothing”.三个节点，最后一个指向 null，意思是“没有了”。

02Array vs linked list数组和链表差在哪

	Array数组	Linked list链表
Where the boxes are盒子在哪	next to each other紧挨着	anywhere, joined by pointers随便放，用指针连起来
Read number 500读第 500 个	O(1) one stepO(1)，一步	O(n) walk 500 nodesO(n)，要走 500 个
Insert in the middle中间插入	O(n) move everything afterO(n)，后面全要挪	O(1) change two pointersO(1)，改两个指针
Memory内存	needs one full block要一整块连续内存	any small blocks小块内存就行

03Why it is used in HashMap为什么 HashMap 里要用它

Two different keys can land in the same bucket. The simplest fix is to keep them in a short linked list: put the new one at the end, and when you look up a key, walk the list and compare keys.两个不同的 key 可能落进同一个桶。最简单的办法就是把它们串成一条短链表：新的放末尾，查找时顺着链走、逐个比 key。

That is why the array inside a HashMap is called an “array of buckets”: each cell holds the head of a small list.所以 HashMap 里的数组叫“桶数组”：每一格存的是那条短链的头。

04Where you meet it你会在哪里遇到它

HashMap: one bucket = one short list (lesson 4).HashMap：一个桶就是一条短链（第 4 课会讲）。
A queue of tasks with a pointer to the next: a linked list.任务队列：每个任务指向下一个，本质就是链表。

→New words新词

linked list /lɪŋkt lɪst/ Boxes joined by pointers.链表：用指针串起来的盒子 ▶ hear it

node /noʊd/ One box: a value plus a pointer.节点：一个值加一个指针 ▶ hear it

pointer /ˈpɔɪntər/ A value that says where the next box is.指针：记录下一个盒子在哪 ▶ hear it

head /hed/ The first node of the list.头节点：链表的第一个 ▶ hear it

null /nʌl/ Nothing. The end of a list.空；链表的结尾 ▶ hear it

Click ▶ hear it for real people on YouGlish; 🔊 for the computer voice.点 ▶ hear it 听真人发音（YouGlish）；点 🔊 听电脑朗读。

✓Check yourself自测

Why can I not jump to the 500th item?为什么不能直接跳到第 500 个？
Insert in the middle: array or linked list? Why?中间插入：数组还是链表？为什么？
What does the last pointer hold?最后一个节点的指针指向什么？

Answer out loud first. Only then open the answers below.先自己出声答，再看下面的答案。

Answers参考答案

01There is no index and no formula. The boxes are not next to each other, so you must follow every pointer.没有下标也没有公式。盒子不连续，只能一个指针一个指针地走。

02Linked list: change two pointers, O(1). An array would shift everything after it, O(n).链表：改两个指针，O(1)。数组要把后面全部挪一遍，O(n)。

03null — “nothing”. That is how you know the list has ended.null，表示“没有了”。看到它就说明到头了。

Next: Lesson 3, tree →下一课：第 3 课，树 →