在继续进行讲解前，我们首先来了解指针的相关概念，以便更好的理解链表。假设我们需要处理一个大型数据文件，这一文件已经被读取保持在内存中，当我们在函数间传递文件时，并不会直接传递整个文件，我们需要创建变量来保存文件在内存中的位置，这些变量很小，很容易在不同的函数之间传递。
使用指针的好处之一就是可以用一个简单的内存地址就可以指向一个更大的内存地址段。计算机硬件中存在对指针的支持，称为间接寻址。
与 C 语言等不同，在 Python 中，我们不需要直接操作指针，但这并不意味着 Python 中不使用指针。例如赋值语句 l = list([1, 2, 3])，我们通常会说 l 是列表类型的变量，或者直接说 l 是一个列表，但这并不准确，变量 l 是对列表的引用(指针)，list 构造函数在内存中的创建一个 list 并返回该 list 起始的内存位置，这就是存储在 l 中的内容，Python 隐藏了这种复杂性。
1.2 指针结构
Next 指针初始化为 None，这意味着默认结点为端点，除非更改 Next 的值，这样可以确保正确终止链表。我们也可以根据需要向结点类添加其他内容，例如我们可以创建一个 Fruit 类，用于存储不同水果售价信息等数据，并使用数据域链接到 Fruit 类的实例。
为了能够打印节点信息，我们需要重载 __str__ 方法：
为了实现读取链表指定位置元素的操作，我们将重载 __getitem__ 操作。我们已经知道单链表中的结点只能顺序存取，即访问前一个结点后才能接着访问后一个结点。因此要访问单链表中第 i i i 个元素值，必须从头指针开始遍历链表，依次访问每个结点，直到访问到第 i i i 个结点为止。因此操作的复杂度为 O ( n ) O(n) O(n)。同时，我们希望确保索引在可接受的索引范围内，否则将引发 IndexError 异常：
def __getitem__(self, index):
if index > self.length - 1 or index < 0:
raise IndexError("SinglyLinkedList assignment index out of range")
else:
count = -1
current = self.head
while count < index:
current = current.next
count += 1
return current.data
复制代码
我们也可以实现修改指定位置元素的操作，只需要重载 __setitem__ 操作，其复杂度同样为 O ( n ) O(n) O(n)：
def __setitem__(self, index, value):
if index > self.length - 1 or index < 0:
raise IndexError("SinglyLinkedList assignment index out of range")
else:
count = -1
current = self.head
while count < index:
current = current.next
count += 1
current.data = value
复制代码
2.4 查找指定元素
当查找指定元素时，需要设置一个跟踪链表结点的指针 current，初始时 current 指向链表中的第一个数据结点， 然后顺着 next 域依次指向每个结点，每指向一个结点就判断其值是否等于指定值 value，若是则返回该结点索引；否则继续往后搜索，如果链表中无此元素，则引发 ValueError 异常，其时间复杂度为 O ( n ) O(n) O(n)：
def locate(self, value):
count = -1
current = self.head
while current != None and current.data != value:
count += 1
current = current.next
if current and current.data == value:
return count
else:
raise ValueError("{} is not in sequential list".format(value))
复制代码
2.5 在指定位置插入新元素
单链表结点的插入只需要修改结点指针域的值，使其指向新的链接位置，而无需移动任何元素。 例如我们要在链表中索引为 i i i 处插入一个新结点，必须首先找到所插位置的前一个结点 i − 1 i-1 i−1，再进行插入，设指针 previous 指向待插位置的前驱结点，指针 current 指向插入前链表中索引为 i i i 的结点，同时也是待插位置的后继结点，指针 new_node 指向待插新结点，插入操作过程如下所示：
使用 Python 实现算法如下：
def insert(self, index, data):
count = -1
current = self.head
# 判断插入位置的合法性
if index > self.length or index < 0:
raise IndexError("SinglyLinkedList assignment index out of range")
else:
node = Node(data)
while count < index:
# 查找插入位置
previous = current
current = current.next
count += 1
# 插入新结点
node.next = previous.next
previous.next = node
self.length += 1
复制代码
也可以利用上述思想，直接在链表中插入结点：
def insert_node(self, index, node):
count = -1
current = self.head
if index > self.length or index < 0:
raise IndexError("SinglyLinkedList assignment index out of range")
else:
while count < index:
previous = current
current = current.next
count += 1
node.next = previous.next
previous.next = node
self.length += 1
复制代码
2.6 删除指定位置元素
要删除链表中第 i i i 个结点，首先在单链表中找到删除位置的前一个结点 previous，指针 current 指向要删除的结点，将 previous 的指针域修改为待删除结点 current 的后继结点的地址，删除后的结点需动态的释放。下图 (b) 中的粉色虚线表示删除结点 current 后的指针指向：
使用 Python 实现算法如下：
def __delitem__(self, index):
if index > self.length - 1 or index < 0:
raise IndexError("SinglyLinkedList assignment index out of range")
else:
count = -1
previous = self.head
while count < index - 1:
previous = previous.next
count += 1
current = previous.next
previous.next = current.next
self.length -= 1
del current
复制代码
在插入和删除操作中，都是先确定操作位置，然后再进行插入和删除操作，所以其时间复杂度均为 O ( n ) O(n) O(n)。由于算法在进行插入和删除操作时没有移动元素的位置，只是修改了指针链接，所以采用链表存储方式进行插入和删除操作要比顺序存储方式的效率高。
2.7 其它一些有用的操作
