python实现双向链表的操作

淩亂°似流年 2023-07-21 09:00 33阅读 0赞

![format_png][]双向链表

双向链表又叫做双链表，每个节点有两个指针域和一个数据域。prev指针域指向前一个节点，next指针域指向下一个节点。注意，第一个节点的prev指针域指向空值，最后一个节点的next域也是指向空值。

![format_png 1][]

双链表的主要操作跟单链表一样，具有如下操作

1.  is\_empty() 链表是否为空
2.  length() 链表长度
3.  travel() 遍历整个链表
4.  add(item) 链表头部添加元素
5.  append(item) 链表尾部添加元素
6.  insert(pos, item) 指定位置添加元素
7.  remove(item) 删除节点
8.  search(item) 查找节点是否存在

python 实现：

#_*_coding:utf-8_*_
    
    class Node(object):
        def __init__(self, item):
            self.item = item
            self.prev = None
            self.next = None
    
    
    class DoubleLinkList(object):
        def __init__(self, node=None):
            '''_head 作为类内部使用，对外不可见'''
            self.__head = node
    
        def is_empty(self):
            '''判断链表是否为空'''
            return self.__head is None
    
        def length(self):
            '''链表的长度'''
            #特别要考虑当链表是空的情况
            # cur游标，用来移动遍历节点
            cur = self.__head
            count = 0
            while cur != None:
                count += 1
                cur = cur.next
    
            return count
    
        def travel(self):
            '''遍历整个链表'''
            cur = self.__head
    
            if cur == None:
                print("empty linklist")
                return
            while cur != None:
                print(cur.item, end=' ')
                cur = cur.next
            print('')
        def add(self,item):
            '''在链表头部添加元素,头插法'''
            node = Node(item)
            #指针指向的顺序可以变化
            node.next = self.__head
            self.__head = node
            node.next.prev = node
    
    
        def append(self,item):
            '''在链表尾部添加元素'''
            node = Node(item)
            cur = self.__head
            #如果链表是空，则将头节点直接指向Node
            if self.is_empty():
                self.__head = node
            else:
                while cur.next != None:
                    cur = cur.next
    
                cur.next = node
                node.prev = cur
    
        def insert(self,pos, item):
            '''在链表指定的位置添加元素'''
            """
            :param pos从0开始
            """
            if pos <= 0:
                self.add(item)
            elif pos > (self.length() -1):
                self.append(item)
            else:
    
                cur = self.__head
                count = 0
                while count < pos:
                    count += 1
                    cur = cur.next
                node = Node(item)
    
                node.next = cur
                cur.prev.next = node
                cur.prev = node
                node.prev = cur.prev
    
        def remove(self, item):
            '''删除某个元素的节点'''
            cur = self.__head
            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
    
        def search(self, item):
            ''' 查找节点是否存在'''
            cur = self.__head
            while cur != None:
                if cur.item == item:
                    return True
                else:
                    cur = cur.next
            return False
            
    if __name__ == '__main__':
        ll = DoubleLinkList()
        print(ll.is_empty())
        print(ll.length())
        ll.append(1)
        ll.append(2)
        ll.travel()
        ll.add(3)
        ll.travel()
        ll.insert(2, 4)
        ll.travel()
        print(ll.search(3))
        ll.travel()
        ll.remove(2)
        ll.travel()

运行结果：

True
    0
    1 2 
    3 1 2 
    3 1 4 2 
    True
    3 1 4 2 
    3 1 4

# 2020年最新Python教程： #

如果你处于想学Python或者正在学习Python，Python的教程不少了吧，但是是最新的吗？

说不定你学了可能是两年前人家就学过的内容，在这小编分享一波2020最新的Python教程。

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

以上这些教程小编已经为大家打包准备好了，希望对正在学习的你有所帮助！

# 获取方式，私信小编 “ 资料 ”，即可免费获取哦！ #

[format_png]: /images/20230528/6c788d2fef954a4daba0fbc480857fad.png
[format_png 1]: /images/20230528/1e94122964864ecabf686c2ac40027bd.png
[format_png 2]: /images/20230528/804792d89c11440db97c8636ad95486e.png
[format_png 3]: /images/20230528/8ee943e82a47450691236753d5bcf29b.png
[format_png 4]: /images/20230528/043dc78e6bac45e0beae8dfc4e0aa34c.png
[format_png 5]: /images/20230528/e254519bf9d540c2af25ef7c241cbde5.png