Python单向链表操作

目录

一、单向链表

单向链表示例图

 二、单向链表的操作

1、判断链表是否为空

2，链表长度

3，遍历整个链表

4，在链表头部添加元素

5、链表尾部添加元素

6，在指定位置插入元素

7，修改指定位置的元素

8，删除元素

9、查找元素是否存在

三、完整代码

一、单向链表

单向链表示例图

结点node里有两个部分：elem(元素)和next(指向下一结点的指针)，head指针指向头结点

 二、单向链表的操作

1、判断链表是否为空

    def is_empty(self):"""判断链表是否为空"""if self.__head is None:return Trueelse:return False

2，链表长度

只要当前的指针不指向None，每次遍历就加1

    def length(self):"""链表长度"""count = 0cur = self.__headwhile cur is not None:count += 1cur = cur.nextreturn count    

3，遍历整个链表

    def travel(self):"""遍历整个链表"""cur = self.__headwhile cur is not None:print(cur.elem, end=' ')cur = cur.nextprint('')

4，在链表头部添加元素

    def add(self, item):"""链表头部添加元素"""node = Node(item)if self.is_empty():self.__head = nodeelse:# 新来的节点的next指向第一个节点node.next = self.__head# 再改变第一个节点的指针指向新节点self.__head = node

5、链表尾部添加元素

    def append(self, item):"""链表尾部添加元素"""# 创建新结点node = Node(item)# 是空链表就把头节点指向这个节点if self.is_empty():self.__head = nodeelse:cur = self.__headwhile cur.next is not None:cur = cur.nextcur.next = node

6，在指定位置插入元素

遍历找到要插入位置的前一个结点

修改前一个结点与新插入结点的指针指向

再修改新插入结点的指针与后一个结点的指针指向

    def insert(self, pos, item):"""在指定位置插入元素"""# 位置pos在第一个元素之前，则在头部插入if pos <= 0:self.add(item)# 位置pos大于总长度，则在尾部插入elif pos > self.length():self.append(item)else:# 指定位置添加元素node = Node(item)count = 0pre = self.__head# 循环定位指针位置while count < (pos-1):count += 1pre = pre.nextnode.next = pre.nextpre.next = node

7，修改指定位置的元素

    def modify(self, pos, item):"""修改指定位置的元素"""# 位置pos小于等于0时，则修改头部元素if pos <= 0:self.__head.elem = item# 位置pos大于总长度，则修改尾部元素elif pos >= self.length():pre = self.__head# 循环指针找到尾部元素while pre is not None:if pre.next is None:  # pre.next为None说明已经找到尾部元素了pre.elem = itembreakelse:pre = pre.next  # 不是尾部元素就继续指针指向下一个else:count = 0pre = self.__head# 循环找出位置while count < pos:  # 1.当不满足count < pos条件时，说明指针已经指向了给定pos的位置count += 1pre = pre.nextpre.elem = item  # 2.修改元素

8，删除元素

    def remove(self, item):"""删除节点"""cur = self.__headpre = Nonewhile cur is not None:# 找到了要删除的元素if cur.elem == item:# 要删除的元素就是第一个元素，就把头指针指向当前的下一个节点if not pre:self.__head = cur.nextelse:pre.next = cur.nextbreak# 未找到要删除的元素，指向向后走，继续遍历else:pre = curcur = cur.next

9、查找元素是否存在

    def search(self, item):"""查找节点是否存在"""cur = self.__headwhile cur is not None:# 找到了返回True,未回到指向下一个继续遍历if cur.elem == item:return Truecur = cur.nextreturn False

三、完整代码

具体说明都在注释里

class Node():def __init__(self, elem):# 单链表结点self.elem = elemself.next = Noneclass SingleLinkList():def __init__(self, node=None):self.__head = nodedef is_empty(self):"""判断链表是否为空"""if self.__head is None:return Trueelse:return Falsedef length(self):"""链表长度"""count = 0cur = self.__headwhile cur is not None:count += 1cur = cur.nextreturn countdef travel(self):"""遍历整个链表"""cur = self.__headwhile cur is not None:print(cur.elem, end=' ')cur = cur.nextprint('')def add(self, item):"""链表头部添加元素"""node = Node(item)if self.is_empty():self.__head = nodeelse:# 新来的节点的next指向第一个节点node.next = self.__head# 再改变第一个节点的指针指向新节点self.__head = nodedef append(self, item):"""链表尾部添加元素"""# 创建新结点node = Node(item)# 是空链表就把头节点指向这个节点if self.is_empty():self.__head = nodeelse:cur = self.__headwhile cur.next is not None:cur = cur.nextcur.next = nodedef insert(self, pos, item):"""在指定位置插入元素"""# 位置pos在第一个元素之前，则在头部插入if pos <= 0:self.add(item)# 位置pos大于总长度，则在尾部插入elif pos > self.length():self.append(item)else:# 指定位置添加元素node = Node(item)count = 0pre = self.__head# 循环定位指针位置while count < (pos-1):count += 1pre = pre.nextnode.next = pre.nextpre.next = nodedef modify(self, pos, item):"""修改指定位置的元素"""# 位置pos小于等于0时，则修改头部元素if pos <= 0:self.__head.elem = item# 位置pos大于总长度，则修改尾部元素elif pos >= self.length():pre = self.__head# 循环指针找到尾部元素while pre is not None:if pre.next is None:  # pre.next为None说明已经找到尾部元素了pre.elem = itembreakelse:pre = pre.next  # 不是尾部元素就继续指针指向下一个else:count = 0pre = self.__head# 循环找出位置while count < pos:  # 1.当不满足count < pos条件时，说明指针已经指向了给定pos的位置count += 1pre = pre.nextpre.elem = item  # 2.修改元素def remove(self, item):"""删除节点"""cur = self.__headpre = Nonewhile cur is not None:# 找到了要删除的元素if cur.elem == item:# 要删除的元素就是第一个元素，就把头指针指向当前的下一个节点if not pre:self.__head = cur.nextelse:pre.next = cur.nextbreak# 未找到要删除的元素，指向向后走，继续遍历else:pre = curcur = cur.nextdef search(self, item):"""查找节点是否存在"""cur = self.__headwhile cur is not None:# 找到了返回True,未回到指向下一个继续遍历if cur.elem == item:return Truecur = cur.nextreturn Falseif __name__ == '__main__':ll = SingleLinkList()print(ll.is_empty())print(ll.length())ll.travel()print('append')ll.append(10)ll.append(12)ll.travel()print('add')ll.add(9)ll.travel()print('insert')ll.insert(1, 33)ll.travel()print('remove')ll.remove(9)ll.travel()print('modify')ll.modify(-1, 13)ll.travel()ll.modify(10, 44)ll.travel()ll.modify(1, 55)ll.travel()print('search')print(ll.search(12))