链表是一系列数据元素,通过链接连接在一起。 每个数据元素都以指针的形式包含到另一个数据元素的连接。单链表。 在这种类型的数据结构中,任何两个数据元素之间只有一个链接。 创建一个链表并使用一些方法来插入,更新和从列表中移除元素。
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