python—数据结构之链表

首页 » 数据结构 » 正文

链表:

链表是一种线性表,不同顺序表连续存储数据,链表在每个节点里存放下一个节点的位置信息,同时存储数据

单向链表:

需要有一个变量P指向单向链表的首节点(第一个节点),尾节点(最后一个节点)的链接区指向空

单链表的语句操作:

  • is_empty() 链表是否为空
  • length() 链表长度:

      需要一个指针,这里给他取名给Cur,将指针指向head,用来遍历节点,还需要一个count来计数

  • travel() 遍历整个链表

      同样需要一个指针cur通过循环将链表中的数据赋值给cur,再把cur打印出来即可

  • add(item) 链表头部添加元素

     注意要先将要添加的node指向原来的第一个node,否则会丢失原链表

  • append(item) 链表尾部添加元素

     尾部添加需要注意退出循环的条件,有两种:

cur.next != None 
cur!= None

    我们需要使用第一种,第二种会多执行一次循环,从而报错

  • insert(pos, item) 指定位置添加元素

    指定插入元素,要考虑输入的位置是否合理,例如小于等于0则默认首部添加,大于等于链表位置则默认为尾部添加。这里重新定义指针pre,特指需要插入位置前的位置,同时需要采用遍历来获得pre的位置

  • remove(item) 删除节点

    删除需要结合遍历方法,需要两个指针,一个指向需要删除节点的前一个节点,另一个指针指向需要删除的节点。(也可以使用一个指针,两个指针较好理解)需要额外判断删除节点是否是头节点,若是头节点,则需要将self._head指向cur.next

  • search(item) 查找节点是否存在

    查找结合遍历方法,找到返回True,否则返回False

Python 中,等号的本质就是使用了链接的数据结构

后继节点:指定节点的下一个节点

class Node(object):
    # 节点
    def __init__(self, elem):
        self.elem = elem
        self.next = None

    pass


class SingelList(object):
    # 单链表
    def __init__(self, node=None):
        self._head = node

    def is_empty(self):
        # 链表是否为空
        return self._head == None

    def length(self):
        # 链表长度
        cur = self._head
        count = 0  # 若初始值count为1则需要改变判断条件,同时需要考虑空链的情况
        while cur != None:
            count = count + 1
            cur = cur.next
        return count

    def travel(self):
        # 遍历整个链表
        cur = self._head
        while cur != None:
            print(cur.elem,end=" ")
            cur = cur.next
        print("")

    def add(self, item):
        # 链表头部添加元素
        node = Node(item)
        node.next = self._head
        self._head = node

    def append(self, item):
        # 链表尾部添加元素
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            cur = self._head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        # 指定位置添加元素
        if pos <= 0:
            self.add(item)
        elif pos >= (self.length() - 1):
            self.append(item)
        else:
            pre = self._head
            count = 0
            while count < (pos - 1):
                count += 1
                pre = pre.next
                # 当循环退出后,pre指向pos-1的位置
                node = Node(item)
                node.next = pre.next
                pre.next = node

    def remove(self, item):
        # 删除节点 pos 从0开始
        cur = self._head
        pre = None
        while cur != None:
            if cur.elem == item:
                if cur == self._head:
                    self._head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    def search(self, item):
        # 查找节点是否存在
        cur = self._head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

链表和顺序表的对比

链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活。

 

 

未经允许不得转载:作者:1146-陶同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《python—数据结构之链表》 发布于2020-07-01

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录