网站 风格,做网站都可以做什么,上海企业网站模板建站平台,网站设置为默认主页前言#xff1a;链表是算法中比较难理解的部分#xff0c;本博客记录单链表、双链表学习#xff0c;理解节点和指针的使用#xff0c;主要内容包括#xff1a;使用python创建链表、实现链表常见的操作。 目录
单链表
双链表 单链表
引入链表的背景#xff1a;
先来看… 前言链表是算法中比较难理解的部分本博客记录单链表、双链表学习理解节点和指针的使用主要内容包括使用python创建链表、实现链表常见的操作。 目录
单链表
双链表 单链表
引入链表的背景
先来看一下数据数组是一块连续的区域需要预留空间。
链表是一种线性表线性表包括顺序表、链表但链表不像顺序表一样连续地存储数据而是在每个节点里存放下一个节点的位置信息地址。
单链表第一个节点是头节点最后一个节点是尾节点。
操作链表时需要注意特殊的情况
空链表只有一个头节点没有尾节点的链表头节点地址指向空有一个头节点接着连接一个尾节点没有中间节点 使用python语言创建一个单链表
需要实现以下功能
实现判断链表是否为空计算链表的长度在链表头部添加元素在链表尾部添加元素在链表的指定位置添加元素删除指定元素的节点判断节点是否存在
class Node(object):def __init__(self, elem):# 节点self.elem elemself.next None# 单链表
class SingleLinkList(object):def __init__(self, nodeNone):self.__head node# 判断链表是否为空def is_empty(self):return self.__head None# 链表的长度def length(self):# cur游标用来遍历节点cur self.__headcount 1while cur ! None:count 1cur cur.nextreturn count# 链表的遍历def travel(self):cur self.__headwhile cur ! None:print(cur.elem, end )cur cur.next# 头部添加元素def add(self, item):node Node(item)node.next self.__headself.__head node# 尾部添加元素def append(self, item):node Node(item)if self.is_empty():self.__head nodeelse:cur self.__headwhile cur.next ! None:cur cur.nextcur.next nodepass# 指定位置添加元素def insert(self, pos, item):if pos 0:self.add(item)elif pos (self.length() - 1):self.append(item)else:pre self.__headcount 0while count (pos - 1):count 1pre pre.next# 当循环退出后 pre指向pos-1node Node(item)node.next pre.nextpre.next node# 删除元素 找到具体的数据删除def remove(self, item):cur self.__headpre Nonewhile cur ! None:if cur.elem item:if cur self.__head:self.__head cur.nextelse:pre.next cur.nextbreakelse:pre curcur cur.next# 查找节点是否存在def search(self, item):cur self.__headwhile cur ! None:if cur.elem item:return Trueelse:cur cur.nextreturn False
双链表
双链表比单链表多了个前驱节点 使用python语言创建一个双链表
需要实现以下功能
实现判断链表是否为空计算链表的长度在链表头部添加元素在链表尾部添加元素在链表的指定位置添加元素删除指定元素的节点判断节点是否存在 class Node(object):def __init__(self, item):self.elem itemself.next Noneself.prev Noneclass DoubleLinkList(object):# 双链表def __init__(self, nodeNone):self.__head node# 判断链表是否为空def is_empty(self):return self.__head None# 链表的长度def length(self):# cur游标用来遍历节点cur self.__headcount 1while cur ! None:count 1cur cur.nextreturn count# 链表的遍历def travel(self):cur self.__headwhile cur ! None:print(cur.elem, end )cur cur.next# 头部添加元素def add(self, item):node Node(item)node.next self.__headself.__head nodenode.next.prev node# 尾部添加元素def append(self, item):node Node(item)if self.is_empty():self.__head nodeelse:cur self.__headwhile cur.next ! None:cur cur.nextcur.next nodenode.prev curpass# 指定位置添加元素def insert(self, pos, item):if pos 0:self.add(item)elif pos (self.length() - 1):self.append(item)else:cur self.__headcount 0while count (pos - 1):count 1cur cur.next# 当循环退出后 pre指向posnode Node(item)node.next curnode.prev cur.prevcur.prev.next nodecur.prev node# 删除元素 找到具体的数据删除def remove(self, item):cur self.__headwhile cur ! None:if cur.elem item:if cur self.__head:self.__head cur.nextif cur.next:# 判断链表是否只有一个节点cur.next.prev Noneelse:cur.prev.next cur.nextif cur.next:cur.next.prev cur.prevbreakelse:cur cur.next# 查找节点是否存在def search(self, item):cur self.__headwhile cur ! None:if cur.elem item:return Trueelse:cur cur.nextreturn False
