python算法与数据结构-单链表
单向链表定义如下所示:
在头部插入元素如下所示:
头部插入元素最终达到的效果,先改变指向100的节点,再改变指向头部的节点(这个有先后顺序),这样以前100之后的节点顺序什么的就不用改变了
在指定位置插入元素,如下所示:
单链表查找元素如下所示:
单链表删除元素如下所示:
头节点是删除的节点的时候,如下所示:
还有一种情况是只有一个节点的时候,如下所示:
代码如下所示:
# -*-coding=utf-8-*- class Node(object): """单链表的节点""" def __init__(self, elem): # item存放数据元素 self.elem = elem # next是下一个节点的标识 self.next = None class SingleLinkList(object): """单链表""" # head是头节点属性,_head在Python中加两个下划线就是私有属性 # 这个node是用户传进来的 def __init__(self, node=None): self.__head = node def is_empty(self): """判断是否为空""" return self.__head==None def length(self): """链表长度""" # cur初始时指向头节点 # cur游标,用来移动遍历节点 cur = self.__head # 这里是一个下划线还是两个待确定 # count 记录数量 count = 0 # 当cur.next != None,表示始终进入循环体,因为cur.next需要在循环体里面才能知道是多少 # 尾节点指向None,当未到达尾部时 while cur != None: count += 1 # 将cur后移一个节点 cur = cur.next return count def travel(self): """遍历整个链表""" cur = self.__head while cur != None: #添加这个这个,后期打印就不换行了 print(cur.elem,end=" ") cur = cur.next print("") # pass def append(self, item): """链表尾部添加元素,尾插法""" node = Node(item) # print('node值是:') # print(node) # 这个if条件是空链表的意思,我们需要考虑特殊条件 # 先判断链表是否为空,若是空链表,则将_head指向新节点 if self.is_empty(): #赋值为空不然会报错 self.__head = node # 若不为空,则找到尾部,将尾节点的next指向新节点 else: # print("222") # cur = self.__head cur = self.__head while cur.next != None: cur = cur.next cur.next = node # 到最后一个位置将元素赋值 def add(self,item): """链表头部添加元素,头插法""" # 先创建一个保存item值的节点 node = Node(item) # 将新节点的链接域next指向头节点,即_head指向的位置 node.next = self.__head # 将链表的头_head指向新节点 self.__head = node #pos是指定的位置,item是保存的元素 def insert(self,pos,item): """链表指定位置添加元素 :param pos 从0开始 """ # 若指定位置pos为第一个元素之前,则执行头部插入 if pos<=0: #头插法 self.add(item) # 若指定位置超过链表尾部,则执行尾部插入 elif pos > (self.length()-1):#尾插法 self.append(item) # 找到指定位置 else: # pre用来指向指定位置pos的前一个位置pos-1,初始从头节点开始移动到指定位置 prev = self.__head count = 0 while count<(pos-1): count+=1 prev = prev.next #当循环退出后,prev指向pos-1位置 node = Node(item) # 先将新节点node的next指向插入位置的节点 #prev.next存储的是下一个节点的地址,因为是在任意位置插入的,新节点node需要连接下一个节点,node.next指向了下一个节点 node.next = prev.next # 将插入位置的前一个节点的next指向新节点 prev.next = node def search(self,item): """查找节点是否存在""" """链表查找节点是否存在,并返回True或者False""" cur = self.__head while cur!=None: if cur.elem == item: return True else: cur = cur.next return False def remove(self,item): """删除节点""" cur = self.__head pre = None while cur != None: # 找到了指定元素 if cur.elem == item: #先判断此节点是否是头节点 #头节点 # 如果第一个就是删除的节点 if cur == self.__head: # 将头指针指向头节点的后一个节点 self.__head = cur.next else: # 将删除位置前一个节点的next指向删除位置的后一个节点 pre.next = cur.next break # 删除后再退出循环,需要一个总的break退出 else: # 继续按链表后移节点 pre = cur cur = cur.next if __name__ == "__main__": # node = Node(100) ll = SingleLinkList() print(ll.is_empty()) #True print(ll.length()) #0 ll.append(1) print(ll.is_empty()) #False print(ll.length()) #1 # ll.append(2) ll.add(8) ll.append(3) ll.append(4) ll.append(5) ll.append(6) #8 1 2 3 4 5 6 ll.insert(-1,9) ll.travel() #9 8 1 2 3 4 5 6 ll.insert(3, 100) ll.travel() #9 8 1 100 2 3 4 5 6 ll.insert(10,200) ll.travel() #9 8 1 100 2 3 4 5 6 200 ll.remove(100) ll.travel() #9 8 1 2 3 4 5 6 200 ll.remove(9) ll.travel() #8 1 2 3 4 5 6 200 ll.remove(200) ll.travel() #8 1 2 3 4 5 6