链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。链表中的每个节点一般由“数据区域”和“指针区域”两部分构成。指针就是下一个节点的存储地址(索引)。每个链表拥有一个表头——head(也称头指针，只有通过头指针才能进入链表)。访问链表中的某一节点，只能从头指针开始，通过指针链接依次访问，不能像数组那样通过下标直接引用。

1.单向链表结构(最后一个节点的指针为空，用-1表示)。

2.循环链表结构(最后一个节点的指针指向第一个节点)。

3.遍历链表。

a =[['x',3],['t',0],['e',-1],['f',4],['z',2]]
head =1
#定义遍历链表的函数
def traverse(a,head):
    p=head
    while p!=-1:
        print(a[p][0])
        p=a[p][1]
#调用函数，遍历链表
traverse(a,head)

4.插人新节点(在节点z后面)。

def insert_d(a,new_value):
    #添加新节点到列表末尾
    a.append([new_value,-1])
    newp =len(a)-1
    p=head
    while p!=-1:
        if a[p][0]=='z':#在节点z后面插入
            a[newp][1]=a[p][1]
            a[p][1]=newp
            break
        p=a[p][1]
insert_d(a,'d')
traverse(a,head)

5.删除节点f。

def delete_f(a, head):
    p = head
    q = None  #前驱节点
    while p != -1:
        if a[p][0] == 'f':
            if q is None:  #删除头节点
                head = a[p][1]  # 返回新的head
            else:
                a[q][1] = a[p][1]
            break
        q = p
        p = a[p][1]
    return head  # 返回修改后的head

# 调用时更新head
head = delete_f(a, head)
traverse(a,head)

6、主程序（测试遍历、插入、删除）

print('原始链表：')
traverse(a,head)    #调用函数实现遍历链表
insert_d(a,'d') #调用函数在节点z之后插入新节点d
print('插入新节点后：')
traverse(a, head)   #调用函数实现遍历链表
head = delete_f(a, head)   #调用函数实现删除节点f
print('删除节点f后：')
traverse(a, head)   #调用函数实现遍历链表