关于链表的相关内容（一）

现在有这么一个链表（二维数组模拟）

索引（地址）	数据	指针
0	'E'	-1
1	'D'	0
2	'B'	4
3	'A'	2
4	'C'	1

data=[['E',-1],['D',0],['B',4],['A',2],['C',1]]; head=3

遍历

接下来演示链表遍历示意图：

它的基本代码是：

data=[['E',-1],['D',0],['B',4],['A',2],['C',1]]
head=3
p=head
while p!=-1:
    print(data[p][0],end='->')
    p=data[p][1]

输出结果是：

A->B->C->D->E->

插入

向元素之后插入

以data=[['D',-1],['B',3],['A',1],['C',0]]; head=2为例，在'B'元素之后加入'BB'
加下来是插入的示意图：

代码如下：

data=[['D',-1],['B',3],['A',1],['C',0]]
head=2
cp=head
while cp!=-1:
    if data[cp][0]=='B':
        data.append(['BB',data[cp][1]])
        data[cp][1]=len(data)-1
        break
    cp=data[cp][1]

p=head
while p!=-1:
    print(data[p][0],end='->')
    p=data[p][1]

输出的结果是：

A->B->BB->C->D->

向元素之前加入

以data=[['D',-1],['B',3],['A',1],['C',0]]; head=2为例，在'C'元素之前加入'BB'

代码如下：

data=[['D',-1],['B',3],['A',1],['C',0]]
head=2
cp=head     #指针
pp=head     #前驱指针（储存指针的上一个值）
while cp!=-1:
    if data[cp][0]=='C':    #图中if条件指此条件
        data.append(['BB',cp])
        data[pp][1]=len(data)-1
        break
    pp=cp
    cp=data[cp][1]

p=head
while p!=-1:
    print(data[p][0],end='->')
    p=data[p][1]

输出的结果是

A->B->BB->C->D->

在头节点前插入

以data=[['B',2],['D',-1],['C',1],['A',0]]; head=3为例,将'AA'作为头节点插入

代码如下：

data=[['B',2],['D',-1],['C',1],['A',0]]
head=3
data.append(['AA',head])
head=len(data)-1

p=head
while p!=-1:
    print(data[p][0],end='->')
    p=data[p][1]

输出的结果是

AA->A->B->C->D->

删除

删除非头节点

以data=[['B',2],['D',-1],['C',1],['A',0]]; head=3为例,将'B'删除

代码如下：

data=[['B',2],['D',-1],['C',1],['A',0]]
head=3
cp=head
pp=head
while cp!=-1:
    if data[cp][0]=='B':
        data[pp][1]=data[cp][1]
        break
    pp=cp
    cp=data[cp][1]

p=head
while p!=-1:
    print(data[p][0],end='->')
    p=data[p][1]

输出的结果是

A->C->D->

删除头节点

以data=[['B',2],['D',-1],['C',1],['A',0]]; head=3为例,将头节点'A'删除

代码如下：

data=[['B',2],['D',-1],['C',1],['A',0]]
head=3
head=data[head][1]

p=head
while p!=-1:
    print(data[p][0],end='->')
    p=data[p][1]

输出的结果是

B->C->D->

知识点的汇总与实践

1.在链表中选择一个节点，在该节点前加入新的节点

data=[['C',4],['B',0],['A',1],['E',-1],['D',3]]
head=2
cp=head
pp=head
flag=False
oldPoint=input("请输入要在哪个节点前加入：")
while cp!=-1:
    if data[cp][0]==oldPoint:
        flag=True
        newPoint=input("请输入要加入的节点内容:")
        if cp==head:
            data.append([newPoint,head])
            head=len(data)-1
        else:
            data.append([newPoint,cp])
            data[pp][1]=len(data)-1
        break
    else:
        pp=cp
        cp=data[cp][1]

if flag:
    p=head
    while p!=-1:
        print(data[p][0],end='->')
        p=data[p][1]
else:
    print("没找到该节点")

2.在链表中删除一个指定节点

data=[['C',4],['B',0],['A',1],['E',-1],['D',3]]
head=2
cp=head
pp=head
flag=False
Point=input("要删除的节点元素：")
while cp!=-1:
    if data[cp][0]==Point:
        flag=True
        if cp==head:
            head=data[head][1]
        else:
            data[pp][1]=data[cp][1]
        break
    else:
        pp=cp
        cp=data[cp][1]

if flag:
    p=head
    while p!=-1:
        print(data[p][0],end='->')
        p=data[p][1]
else:
    print("未找到该节点")

3.按照从小到大的顺序将两个升序链表合并

def read(data,head):
    tmp=head                                    #这里tmp代替指针
    while tmp!=-1:
        print(a[tmp][0],end=" ")
        tmp=a[tmp][1]
    print()

a=[[1,1],[3,2],[4,3],[8,4],[16,-1]]             #链表A
b=[[2,1],[5,2],[7,3],[10,4],[15,-1]]            #链表B
heada=headb=0                                   #头节点都为0
ka=kb=qa=0

while kb!=-1 and ka!=-1:                        #当没遍历完时
    if a[ka][0]>b[kb][0]:                       #判断是否需要插入（如果a的当前项>b的当前项，就要在a的当前项前插入b的当前项）
        if ka==heada:                           #判断是否为头节点，如果是就是头节点插入，不是就是普通节点插入
            a.append([b[kb][0],heada])
            heada=len(a)-1
        else:                                   #普通节点插入
            a.append([b[kb][0],ka])
            a[qa][1]=len(a)-1
        qa=len(a)-1                             #插入节点之后把a的前驱指针指向
        kb=b[kb][1]                             #b的指针下移
    else:                                       #否则就a的指针下移
        qa=ka
        ka=a[ka][1]

while kb!=-1:
    a.append([b[kb][0],ka])                     #把b中剩余的全部加入a
    a[qa][1]=len(a)-1
    qa=len(a)-1                                 #也可以写成qa=a[qa][1]
    kb=b[kb][1]
        
read(a,heada)                                   #遍历