【数据结构】链表的基本操作

本篇从链表的任意位置删除元素开始讲述，前面相关操作可以看文末完整代码

---

任意位置删除元素

思路：

思路：

1、既然我们要删除任意位置，所需的参数肯定有：表示位置的location。

2、链表中删除，我们使用删除结点的前一个结点的next指向要删除的结点的后一个结点。

即要同时找到图中的q和location

伪代码如下：

找q部分：                                          

q=head

i=i

while i<location-1:

        q=q.next

        i+=1

删除操作核心部分：

q.next=q.next.next

size-=1

最后考虑一下几个特殊点：

①删除位置是否合法：空表，删不了，location小于零或者大于元素个数，删不了

②单结点：因为无法进入循环也无法用q删除，所以我们直接调用写好的删头（尾）结点函数或者直接head=None

③删末尾元素：本情况已包含在代码里

④是否对size自减，while循环i是否自增？

那么我们直接上代码：

#任意位置删除def del_anywhere(self,location):if self.is_empty() or location<0 or location>self.size:print('空表删不了哦')elif self.size == 1 or location == 1:self.head=Noneself.size-=1else:q=self.headi=1while i<location-1:q=q.nexti+=1q.next=q.next.nextself.size-=1

测试案例以及结果如下：

---

按位置修改元素

思路：

1、我们需要什么参数？------------位置参数location你总得要吧，修改的新值value才能改吧

2、怎么修改？我们要找到location位置的结点，这时候需要它前一个结点的next指向才可以，所以又用到了我们的 q

3、找到q，修改即可

4、考虑一下特殊情况

伪代码如下：

找q部分：                                          

q=head

i=i

while i<location-1:

        q=q.next

        i+=1

该值部分：

q.next.data=value

考虑特殊点：

①空表：改不了

②单结点：无法进入循环，直接head.data赋值

③删末尾元素：无特例

④size不用变，while的i记得自增

 上代码：

#按位置修改值def change_anywhere(self,location,value):if self.is_empty():print('空表无法修改元素')elif self.size == 1:self.head.data=valueelse:q=self.headi=1while i<location-1:q=q.nexti+=1q.next.data=value

测试案例以及结果：

---

按值修改元素（小细节很多建议反复看）🏆

思路：

1、既然是按值修改，那么就要遍历以获取有多少所匹配的元素

2、所需的参数为匹配的data值和要改的新data

3、遍历到底

4、空表无法修改

5、遍历完了我们需要知道是否改了值，那么可以再循环内加个  flag  记录

万事俱备,直接上伪代码：

遍历：

q=head                        

while q:                        #这里q到了最后一轮循环会指向None，自动退出循环

        q=q.next

        

匹配旧值部分：

if q.data == old_value:

匹配成功赋新值：

q.data=new_value 

记录遍历过程是否改了值：（细节部分）

flag=0

while .......：

        if........:

                ..........

                flag+=1

if flag=0：

        没有改值

else：

        改了flag次        

        

上封装函数代码：

#按值修改def change_value(self,old_value,new_value):if self.is_empty():print('空表修改不了哦')returnq=self.headflag=0while q:if q.data == old_value:q.data=new_valueflag+=1q=q.nextif flag == 0:print('未匹配相关值，修改失败')else:print(f'修改了{flag}处')

测试以及结果：

---

按值查找返回位置（同样有很多细节）

分析：

①遍历链表，而且要遍历充分

②链表没有索引下标，所以要自己记录下标

③空表情况无法遍历

④可以用 flag 记录匹配成功次数，若为0记录为匹配失败

⑤设置一个  bag[ ]  列表用于存储可能有多个的下标，并且有返回值

伪代码如下：

遍历和记录：q=self.headflagbagsi=1while q:if q.data == value:bags追加iflag+=1q=q.nexti+=1循环结束的判断匹配是否成功：if flag == 0:查无此值return []else:查到flag个值return bags

上完整代码：

#按值返回位置def return_index(self,value):if self.is_empty():print('空表无法操作')returnq=self.headflag=0bags=[]i=1while q:if q.data == value:bags.append(i)flag+=1q=q.nexti+=1if flag == 0:print('查无此值')return []else:print(f'查到{flag}个值')return bags

结果如下：（查找值为20的位置）

返回了一个列表包含两个值

---

链表转置（用到了双指针）

不多说了，直接看分析：

为了编写一个反转链表的函数，我们可以保持您现有的链表类和节点类不变，并添加一个新的方法来执行反转操作。

反转链表的核心思想是迭代地遍历链表，同时改变每个节点的 next 指针，使其指向前一个节点

# 反转链表def reverse(self):prev = Noneq = self.headwhile q:next_node = q.next  # 保存对下一个节点的引用q.next = prev       # 反转当前节点的指针prev = q            # 移动 prev 指针到当前节点q = next_node       # 移动 q 指针到下一个节点self.head = prev              # 更新头节点为新的头节点（原来的尾节点）

def reverse(self):if self.is_empty() or self.size==1:returnelse:prev=Noneq=self.headwhile q:next_q=q.nextq.next=prev #self.head=q        可在此处更新头结点为q（不过没必要），因为可在外部直接设置为prev（因为循环内部还未将prev更新为q）prev=qq=next_q self.head=prev          #此位置为外部设置新头结点

       注意

标红处之所以我们可以直接放到循环外部，因为不论是内部还是外部该语句都是更新头结点，循环内部是不断一步步更新，放循环外部是一步更新头结点

结果如下：

方法二：

    def reverse2(self):if self.is_empty():print('空表')else:q=self.headself.head=Nonewhile q:self.add_head(q.data)q=q.next

直接把头结点拿出来之后用q遍历每个结点进行头插即可

---

链表思维导图

---

完整代码&测试样例

#结点的类
class Node(object):def __init__(self,data):self.data=dataself.next=None
#链表类
class LinkList(object):def __init__(self):self.head=Noneself.size=0
#判空def is_empty(self):return self.size == 0
#头插def add_head(self,value):node=Node(value)node.next=self.headself.head=nodeself.size+=1
#遍历def show_me(self):if self.is_empty():print('空链表，不用遍历')returnelse:q=self.headwhile q:print(q.data,end=' ')q=q.next
#尾插def add_tail(self,value):node=Node(value)if self.is_empty():self.head=nodeself.size+=1else:p=self.headwhile p.next:p=p.nextp.next=nodeself.size+=1
#任意位置插入def add_anywhere(self,location,value):node = Node(value)if location>self.size+1 or location<=0:print('插入位置有误')returnelse:r = self.head#第一个位置就头插if location == 1:self.add_head(value)else:i=1while i<location-1:r = r.nexti+=1node.next = r.nextr.next = nodeself.size += 1
#头删def del_head(self):if self.is_empty():print('删不了一点')returnself.head=self.head.nextself.size-=1
#尾删def del_tail(self):if self.is_empty():         #空表删不了print('删不了哦')elif self.size == 1:        #一个元素直接让self.head = Noneself.head = Noneself.size -= 1else:p = self.headwhile p.next.next:      #遍历到倒数第二个结点，#如果这种方式理解不了可以用 i=1 while i<self.size-1 然后内部i+=1 也可以p = p.nextp.next = Noneself.size -= 1
#任意位置删除def del_anywhere(self,location):if self.is_empty():print('空表删不了哦')elif self.size == 1:self.head=Noneelse:q=self.headi=1while i<location-1:q=q.nexti+=1q.next=q.next.nextself.size-=1
#按位置修改值def change_anywhere(self,location,value):if self.is_empty():print('空表无法修改元素')elif self.size == 1:self.head.data=valueelse:q=self.headi=1while i<location-1:q=q.nexti+=1q.next.data=value
#按值修改def change_value(self,old_value,new_value):if self.is_empty():print('空表修改不了哦')returnq=self.headflag=0while q:if q.data == old_value:q.data=new_valueflag+=1q=q.nextif flag == 0:print('未匹配相关值，修改失败')else:print(f'修改了{flag}处')
#按值返回位置def return_index(self,value):if self.is_empty():print('空表无法操作')returnq=self.headflag=0bags=[]i=1while q:if q.data == value:bags.append(i)flag+=1q=q.nexti+=1if flag == 0:print('查无此值')return []else:print(f'查到{flag}个值')return bags
# 反转链表def reverse(self):prev = Noneq = self.headwhile q:next_node = q.next  # 保存对下一个节点的引用q.next = prev       # 反转当前节点的指针prev = q            # 移动 prev 指针到当前节点q = next_node       # 移动 q 指针到下一个节点self.head = prev              # 更新头节点为新的头节点（原来的尾节点）if __name__ =='__main__':new_l=LinkList()print('头插')new_l.add_head(10)new_l.add_head(20)new_l.add_head(30)new_l.show_me()print()print('尾插')new_l.add_tail(10)new_l.add_tail(20)new_l.add_tail(40)new_l.show_me()print()print('任意位置')new_l.add_anywhere(6,30)new_l.show_me()print()print('任意位置（尾部）')new_l.add_anywhere(8,50)new_l.show_me()print()print('任意位置（头部）')new_l.add_anywhere(1,0)new_l.show_me()print()print('头删')new_l.del_head()new_l.show_me()print()print('尾删')new_l.del_tail()new_l.show_me()print()print('任意位置删(这里删的10)')new_l.del_anywhere(4)new_l.show_me()print()print('任意位置该元素')new_l.change_anywhere(3,1)new_l.show_me()print()print('按值修改')new_l.change_value(1,666)new_l.show_me()print()print('查下标')print(new_l.return_index(20))print('反转链表前')new_l.show_me()print()# 反转链表new_l.reverse()print('反转链表后')new_l.show_me()print()

---