链表是一系列数据元素,通过链接连接在一起。 每个数据元素都以指针的形式包含到另一个数据元素的连接。单链表。 在这种类型的数据结构中,任何两个数据元素之间只有一个链接。 创建一个链表并使用一些方法来插入,更新和从列表中移除元素。
Python在其标准库中没有链接列表。用节点概念来实现链表的概念
基本元素:

节点:每个节点有两个部分,左边称为值域,存放用户数据;右边部分称为指针域,用来存放指向下一个元素的指针。
head:head节点永远指向第一个节点
tail: tail永远指向最后一个节点
None:链表中最后一个节点的指针域为None值

时间复杂度:

  • 访问O(N)
  • 查找O(N)
  • 插入O(1)
  • 删除O(1)
    定义链表
class Node:
    def __init__(self,data = None, next = None):
        self.data = data
        self.next = next

定义一个节点,如下创建了三个独立的节点:

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

后再把每个节点的关系表示出来

node1.next = node2
node2.next = node3

遍历链表
probe = head
while probe != None:
probe = probe.next