5.双向链表操作

双向链表操作，具体实施

#!/usr/bin/env python
#coding:utf8
#++++++++++++description++++++++++++#
"""
@author:ying
@contact:1074020480@qq.com
@site: 
@software: PyCharm
@file: doublylinkedlist.py
@time: 2019/11/13 下午3:50
"""
#+++++++++++++++++++++++++++++++++++#
# 创建单链表
class SingleNode(object):
    def __init__(self, arg):
        """初始化一个单链表，且只有一个值"""
        self.arg = arg
        self.next = None
        self.pre = None



class DoubleLinkList(object):
    def __init__(self, node=None):
        """初始化一个单链表，且只有一个值"""
        self.__head = node
        # self.pre=self.__head


    def is_empty(self):
        """判断为空"""
        if self.__head == None:
            return True
        else:
            return False

    def add(self,arg):
        """头部添加"""
        node=SingleNode(arg)
        if self.is_empty():
            self.__head=node
        else:
            node.next=self.__head
            self.__head.pre=node
            self.__head=node


    def travel(self):
        cur = self.__head
        while cur != None:
            print(cur.arg, end=' ')
            cur = cur.next
        print()

    def append(self,arg):
        """尾部新增数据"""
        node = SingleNode(arg)  # 新的单链表
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.pre=cur

    def lenght(self):
        if self.is_empty():
            return 0
        count=0
        cur=self.__head
        while cur!= None:
            count+=1
            cur=cur.next
        return count

    def pre(self,arg):
        """寻找上一个节点"""
        cur=self.__head
        if self.is_empty():
            return
        while cur != None:
            if cur.arg == arg:
                if cur.pre == None:
                    return None
                return cur.pre.arg
            else:
                # 让游标继续执行
                cur = cur.next

    def next(self,arg):
        """寻找下一个节点"""
        cur=self.__head
        if self.is_empty():
            return
        while cur != None:
            if cur.arg == arg:
                if cur.next == None:
                    return None
                return cur.next.arg
            else:
                # 让游标继续执行
                cur = cur.next

    def search(self,arg):
        """寻找节点"""
        cur = self.__head
        if self.is_empty():
            return False
        while cur != None:
            if cur.arg == arg:
                return True
            else:
                # 让游标继续执行
                cur = cur.next
        return False

    def remove(self,arg):
        """删除节点"""
        cur = self.__head
        pre = None
        while cur != None:
            # 锁定需要删除的值
            if cur.arg == arg:
                # 删除第一个
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    # 直接将上一个节点的下一个值指向当前节点的下一个值，等于就是将当前节点从中脱离出来，删除（因为上下都没有链接）
                    pre.next = cur.next
                break
            else:
                # 没找到就一直往下走，此时上节点的游标与当前节点的游标都要往下走，不然就玩脱了
                pre = cur
                cur = cur.next





d=DoubleLinkList()
d.add(1)
d.add(2)
d.add(3)
d.add(4)
print('is_empty: ',d.is_empty())
d.append(55)
d.append(77)
print('count: ',d.lenght())
print('travel: ' , end='')
d.travel()
print('pre: ',d.pre(77))
print('pre_head: ',d.pre(4))
print('next_tail: ',d.next(77))
print('next: ',d.next(4))
d.remove(4)
print('travel_remove: ' , end='')
d.travel()
print('search: ',d.search(77))
-------------------------结果------------------------------------
is_empty:  False
count:  6
travel: 4 3 2 1 55 77 
pre:  55
pre_head:  None
next_tail:  None
next:  3
travel_remove: 3 2 1 55 77 
search:  True