python学习笔记_第27天(线性表_链表1)

1544-陈同学

发表文章数:60

热门标签

,
首页 » 数据结构 » 正文

线性表

链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁,使用时缺乏灵活性。
链表由元素域+链接域,在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址),将元素存放在通过链接构造起来的一系列存储块中。
python学习笔记_第27天(线性表_链表1)

单向链表

单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。
python学习笔记_第27天(线性表_链表1)

  • 表元素域elem用来存放具体的数据。
  • 链接域next用来存放下一个节点的位置
  • 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。

单链表的操作

操作 说明
is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 删除符合条件的第一个节点
search(item) 查找节点是否存在

单链表的实现伪代码

class SingleNode:
    """单链表的结点"""
    def __init__(self,item):
        self.item = item  # item单链表元素域,存放元素对象
        self.next = None  # next单链表链接域,存放下一个节点的标识。初始一个节点时无下一节点,则赋值None。


class SingleLinkList:
    """单链表"""
    def __init__(self,SingleNode = None):  # 使用默认参数,当用户未创建节点时可以初始化一个空链表
        self.__head = SingleNode  # 对象私有属性,指向用户已创建的头节点

    def is_empty(self):
        """判断链表是否为空"""
        pass

    def length(self):
        """链表长度"""
        pass

    def travel(self):
        """遍历整个链表"""
        pass
        
    def add(self, item):
        """链表头部添加元素"""
        pass
        
    def append(self, item):
        """链表尾部添加元素"""
        pass
        
    def insert(self, pos, item):
        """指定位置添加元素"""
        pass
        
    def remove(self,item):
        """删除节点"""
        pass
        
    def search(self,item):
        """查找节点是否存在,并返回True或者False"""
        pass

单链表操作具体实现

  • 单链表类与节点类关联的逻辑:
    单链表类的append、add、insert方法中初始化所属节点类的节点对象。__head私有属性指向首创的节点对象,节点对象中的next属性指向下一个新增的节点对象。
  • is_empty() 链表是否为空
    def is_empty(self):
        """判断链表是否为空"""
        return self.__head == None  # 判断私有属性__head是否为None值,是None值则为空无已建节点
  • length() 链表长度
    def length(self):
        """链表长度"""
        # 遍历计数
        cur = self.__head  # cur游标初始值为头节点,用来移动遍历节点;当为空链表时,cur = None也满足
        count = 0  # 对节点进行计数
        while cur != None:
            count += 1
            cur = cur.next
        return count
  • travel() 遍历整个链表
    def travel(self):
        """遍历整个链表"""
        # 遍历打印
        cur = self.__head  # cur游标初始值为头节点,用来移动遍历节点;当为空链表时,cur = None也满足
        while cur != None:  # 遍历到最后一个已有节点的next所指对象停止,避免遗漏最后一个节点
            print(cur.item, end=' ')  # 默认end为换行符
            cur = cur.next
        print()  # 在完成一次遍历后换行
  • append(item) 链表尾部添加元素
    def append(self, item):
        """链表尾部添加元素,尾插法"""
        singlenode = SingleNode(item)  # 初始化节点
        # 当为空链表时cur = None,None.next出错,需要进行特殊处理
        if self.is_empty():
            self.__head = singlenode  # 当为空列表,直接将头节点指向新建的节点
        else:
            cur = self.__head
            while cur.next != None:  # 遍历到最后一个已存在的节点停止
                cur = cur.next
            cur.next = singlenode
  • add(item) 链表头部添加元素
    def add(self, item):
        """链表头部添加元素,头插法"""
        # 先将新节点的链接域指向__head属性,再将__head属性指向新节点地址。顺序不能颠倒,保证原有链表顺序不打断,颠倒会导致链表的丢失
        singlenode = SingleNode(item)
        singlenode.next = self.__head
        self.__head = singlenode
  • insert(pos, item) 指定位置添加元素
    def insert(self, pos, item):
        """
        指定位置添加元素
        pos参数 起始索引为0
        """
        # pos 是用户传的任意值,要考虑特殊情况
        if pos <= 0:  # 索引小于等于0,则头部追加
            self.add(item)
        elif pos > (self.length() - 1):  # 索引超出长度,则尾部追加;在当前(长度-1)索引处插入,指在尾节点前插入,所以条件不包含等号
            self.append(item)
        else:
            # 游标pre控制指定位置的前一节点的next属性
            pre = self.__head
            count = 0
            # 当循环体退出后,要求pre指向pos-1位置
            while count < (pos - 1):
                count += 1
                pre = pre.next
            singlenode = SingleNode(item)
            singlenode.next = pre.next
            pre.next = singlenode
  • remove(item) 删除节点
    def remove(self, item):
        """删除节点"""
        cur = self.__head
        pre = None  # 与游标cur相隔一个节点
        while cur != None:  # 删除空链表不进入循环,不做操作;删除最后一个节点也适用
            # 考虑空列表、删除第一个节点、删除仅有的一个节点、删除尾节点这四类特殊情况
            if cur.item == item:
                if pre == None:  # 若删除第一个节点,将__head指向cur.next
                    self.__head = cur.next  # 当删除仅有的一个节点也成立
                else:
                    pre.next = cur.next  # 断开当前节点与主链接的联系,来实现节点的删除
                break  # 执行删除操作后,要跳出当前循环
            else:
                pre = cur
                cur = cur.next
  • search(item) 查找节点是否存在
    def search(self, item):
        """查找节点是否存在,并返回True或者False"""
        cur = self.__head
        while cur != None:
            if cur.item == item:
                return True  # 执行return语句退出函数,return之后的语句不再执行
            else:
                cur = cur.next
        return False
	
  • 测试
if __name__ == '__main__':
    ll = SingleLinkList()
    print(ll.is_empty())
    print(ll.length())

    ll.append(1)
    print(ll.is_empty())
    print(ll.length())

    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)  # 索引为负,默认头部添加:9 8 1 2 3 4 5 6
    ll.travel()
    ll.insert(3, 100)  # 在3索引处添加,其余节点后移:9 8 1 100 2 3 4 5 6
    ll.travel()
    ll.insert(10, 200)  # 索引超出链表长度,默认尾部添加:9 8 1 100 2 3 4 5 6 200
    ll.travel()
    
    ll.search(100)
    ll.remove(100)  # 删除第一个匹配的节点:9 8 1 2 3 4 5 6 200
    ll.travel()
    ll.search(100)
    ll.remove(9)  # 删除头节点:8 1 2 3 4 5 6 200
    ll.travel()
    ll.remove(200)  # 删除尾节点:8 1 2 3 4 5 6
    ll.travel()

执行结果:
True
0
False
1
9 8 1 2 3 4 5 6
9 8 1 100 2 3 4 5 6
9 8 1 100 2 3 4 5 6 200
9 8 1 2 3 4 5 6 200
8 1 2 3 4 5 6 200
8 1 2 3 4 5 6

链表与顺序表的对比

顺序表优点在于可以通过O(1)一次性定位,但要求存储空间,当动态改变时整个空间都改变。当内存中没用足够的连续存储空间时,顺序表无法应用,对顺序表来说,n花费在数据搬迁上
链表对离散的内存空间可以达到充分的利用,但额外内存消耗要更多(多一个链接域),且定位元素时只能通过遍历,最差复杂度为O(n),对链表来说n花费在遍历上

未经允许不得转载:作者:1544-陈同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《python学习笔记_第27天(线性表_链表1)》 发布于2021-02-17

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录