线性表(双向链表(动图解析))

1148-张同学

发表文章数:63

热门标签

, ,
首页 » Python » 正文


这一部分虽然大部分原理与单向链表相似。但是比单向链表多分析“头节点、只有一个节点、中间节点、尾部节点”,针对较为复杂的操作,进行了详细的分析。其余简单的部分可以参考“单向链表”。

双向链表

双向链表或双面链表
每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。
线性表(双向链表(动图解析))

双向链表操作

判断链表是否为空、计算链表长度、遍历整个链表、查找指定元素的操作与单向链表相似

在头部添加元素

线性表(双向链表(动图解析))

// An highlighted block
"""头部添加元素"""
    def add(self, item):
        node =  DoubleLinkList(item)
        node.next = self._head
        self._head = node
        node.next.prev=node
在尾部添加元素

使用cur游标找到尾部,然后对新的元素进行添加
线性表(双向链表(动图解析))

// An highlighted block
 """尾部添加元素"""
    def append(self, item):
        node = DoubleLinkList(item)
        if self.is_empty():  # 先判断链表是否为空,若是空链表,则将_head指向新节点
            self._head = node  # 若不为空,则找到尾部,将尾节点的next指向新节点
        else:
            cur = self._head
            while cur.next!= None:  # 判断下一个节点是否为None
                cur = cur.next
            cur.next = node
            node.prev=cur
指定位置添加元素

通过cur游标找到待添加元素的位置
线性表(双向链表(动图解析))

// An highlighted block
"""在指定位置添加元素
    添加的元素是 (2,50)
    """
    def insert(self, pos, item):
        # 判断指定位置是进行头部添加还是尾部添加
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = DoubleLinkList(item)
            cur = self._head
            count = 0
            # 通过计数判断是否移动到指定位置
            while count < pos :
                count += 1
                cur = cur.next
            node.next = cur
            node.prev = cur.prev
            cur.prev.next=node
            cur.prev=node
删除元素

线性表(双向链表(动图解析))

// An highlighted block
   """删除一个节点"""
    def remove(self, item):
        # 若链表为空,则直接返回
        cur = self._head
        # 若头节点的元素就是要查找的元素item
        while cur != None:
            if cur.item == item:
                # 先判断此节点是否为头结点
                if cur == self._head:
                    self._head = cur.next
                    if cur.next:
                        #判断链表中是否只有一个节点
                        cur.next.prev=None
                else:
                    cur.prev.next=cur.next
                    if cur.next:
                        cur.next.prev=cur.prev
                break
            else:
                cur = cur.next

程序运行

// An highlighted block
class DoubleLinkList(object):
    """双链表"""
    def __init__(self,item=None,node=None):
        self.item = item
        self._head = node
        self.next = None

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

    """链表长度"""
    def length(self):
        cur = self._head  # cur初始时指向头节点
        count = 0
        while cur != None:  # 尾节点指向None,当未到达尾部时
            count=count+1
            cur=cur.next  # 将cur后移一个节点
        return count

    """遍历链表"""
    def travel(self):
        cur = self._head
        while cur != None:
            print(cur.item,end="/t")
            cur = cur.next
        print(end="/n")

    """尾部添加元素"""
    def append(self, item):
        node = DoubleLinkList(item)
        if self.is_empty():  # 先判断链表是否为空,若是空链表,则将_head指向新节点
            self._head = node  # 若不为空,则找到尾部,将尾节点的next指向新节点
        else:
            cur = self._head
            while cur.next!= None:  # 判断下一个节点是否为None
                cur = cur.next
            cur.next = node
            node.prev=cur

    """头部添加元素"""
    def add(self, item):
        node =  DoubleLinkList(item)
        node.next = self._head
        self._head = node
        node.next.prev=node

     """在指定位置添加元素  添加的元素是 (2,50)"""
    def insert(self, pos, item):
        # 判断指定位置是进行头部添加还是尾部添加
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = DoubleLinkList(item)
            cur = self._head
            count = 0
            # 通过计数判断是否移动到指定位置
            while count < pos :
                count += 1
                cur = cur.next
            node.next = cur
            node.prev = cur.prev
            cur.prev.next=node
            cur.prev=node


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

    """删除一个节点"""
    def remove(self, item):
        # 若链表为空,则直接返回
        cur = self._head
        # 若头节点的元素就是要查找的元素item
        while cur != None:
            if cur.item == item:
                # 先判断此节点是否为头结点
                if cur == self._head:
                    self._head = cur.next
                    if cur.next:
                        #判断链表中是否只有一个节点
                        cur.next.prev=None
                else:
                    cur.prev.next=cur.next
                    if cur.next:
                        cur.next.prev=cur.prev
                break
            else:
                cur = cur.next



if __name__=="__main__":
    a=DoubleLinkList()
    print(a.is_empty())
    print(a.length())

    #在尾部增加元素
    a.append(1)
    print(a.is_empty())
    print(a.length())
    a.append(10)
    a.append(56)
    a.append(24)
    a.append(78)
    a.append(4)
    a.travel()
    #在头部增加元素
    a.add(20000)
    a.travel()
    # 在指定位置插入
    a.insert(3,50)
    a.travel()
    print(a.length())
    #删除元素
    a.remove(20000)
    a.travel()
    #查找元素
    a.search(50)
    a.search(10000)
    a.search(30000)

线性表(双向链表(动图解析))

未经允许不得转载:作者:1148-张同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《线性表(双向链表(动图解析))》 发布于2020-07-02

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录