python数据结构之双链表

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
#                     _ooOoo_
#                   o8888888o
#                    88" . "88
#                 ( | -  _  - | )
#                     O\ = /O
#                 ____/`---'\____
#                  .' \\| |// `.
#                 / \\|||:|||// \
#               / _|||||-:- |||||- \
#                | | \\\ - /// | |
#              | \_| ''\---/'' | _/ |
#               \ .-\__ `-` ___/-. /
#            ___`. .' /--.--\ `. . __
#         ."" '< `.___\_<|>_/___.' >'"".
#       | | : `- \`.;`\  _ /`;.`/ - ` : | |
#          \ \ `-. \_ __\ /__ _/ .-` / /
#      ==`-.____`-.___\_____/___.-`____.-'==
#                     `=---='
'''
@Project ：pythonalgorithms 
@File ：doublelinklist.py
@Author ：不胜人生一场醉
@Date ：2021/7/13 23:00 
'''


class Node(object):
    def __init__(self, data):
        self.prev = None
        self.data = data
        self.next = None


class DoubleLinkList(object):
    def __init__(self):
        self.header = None
        self.currentnum = 0

    def isempty(self):
        return self.header == None

    def travel(self):
        tempnode = self.header
        while tempnode != None:
            print("{}".format(tempnode.data), end=" ")
            tempnode = tempnode.next
        print("\r")

    def add(self, item):
        node = Node(item)
        if self.isempty():
            self.header = node
            self.currentnum += 1
            return
        node.next = self.header
        self.header.prev = node
        self.header = node
        self.currentnum += 1

    def append(self, item):
        if self.isempty():
            self.add(item)
            self.currentnum += 1
            return
        tempnode = self.header
        while tempnode.next is not None:
            tempnode = tempnode.next
        node = Node(item)
        node.prev = tempnode
        tempnode.next = node
        self.currentnum += 1

    def length(self):
        length = 0
        tempnode = self.header
        while tempnode is not None:
            length += 1
            tempnode = tempnode.next
        return length

    def search(self, item):
        tempnode = self.header
        while tempnode != None:
            if tempnode.data == item:
                return True
            else:
                tempnode = tempnode.next
        return False

    def update(self, index, item):
        pass

    def getitem(self, index):
        if index > self.currentnum or index <= 0:
            raise IndexError("{} is not find in Linklist".format(index))
        tempnode = self.header
        i = 1
        while i < index:
            tempnode = tempnode.next
            i += 1
        if tempnode.next == None:
            return -1
        else:
            return tempnode.data

    def getindex(self, item):

        tempnode = self.header
        i = 0
        flag = False
        while tempnode != None:
            i += 1
            if tempnode.data == item:
                flag = True
                return i
            else:
                tempnode = tempnode.next
        if flag == False:
            return 0

    def insert(self, item, index):
        tempnode = self.header
        if index > self.currentnum + 1 or index <= 0:
            raise IndexError("{} is not find in Linklist".format(index))
        # 指定位置为第一个即在头部插入

        if index == 1:
            self.add(item)
        elif index > self.currentnum - 1:
            self.append(item)
        else:
            node = Node(item)
            for i in range(1, index - 1):
                tempnode = tempnode.next
            node.next = tempnode.next
            node.prev = tempnode
            tempnode.next.prev = node
            tempnode.next = node
        self.currentnum += 1

    def deletebyitem(self, item):
        tempnode = self.header
        while tempnode != None:
            if tempnode.data == item:
                self.currentnum -= 1
                if tempnode == self.header:
                    self.header = self.header.next
                    if tempnode.next:
                        tempnode.next.prev = None
                    return
                if tempnode.next is None:
                    tempnode.prev.next = tempnode.next
                    return
                tempnode.prev.next = tempnode.next
                tempnode.next.prev = tempnode.prev
                return
            tempnode = tempnode.next

    def deletebyindex(self, index):

        if index > self.currentnum or index <= 0:
            raise IndexError("{} is not find in Linklist".format(index))

        i = 1
        tempnode = self.header

        if index == 1:
            self.header = tempnode.next
            if tempnode.next:
                tempnode.prev = None
            self.currentnum -= 1
            return

        while tempnode.next and i < index:
            tempnode = tempnode.next
            i += 1
        if tempnode.next is None:
            tempnode.prev.next = tempnode.next
            self.currentnum -= 1
            return
        if i == index:
            tempnode.prev.next = tempnode.next
            tempnode.next.prev = tempnode.prev
            self.currentnum -= 1


if __name__ == '__main__':
    a = DoubleLinkList()
    a.add(1)  # 1
    a.travel()
    a.add(2)
    a.travel()
    a.append(4)
    a.travel()
    a.append(3)
    a.travel()
    print(a.length())
    print(a.search(1))
    print(a.getindex(4))
    print(a.getindex(5))
    print(a.getitem(2))
    # print(a.getitem(5))
    # IndexError: 5 is not find in Linklist
    a.insert(5, 1)
    a.travel()
    a.insert(6, 5)
    a.travel()
    a.insert(7, 2)
    a.travel()
    a.deletebyitem(7)
    a.travel()
    a.deletebyitem(6)
    a.travel()
    a.deletebyitem(5)
    a.travel()
    a.deletebyindex(2)
    a.travel()
    a.deletebyindex(3)
    a.travel()
    a.deletebyindex(1)
    a.travel()

C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/doublelinklist.py
1 
2 1 
2 1 4 
2 1 4 3 
4
True
3
0
1
5 2 1 4 3 
5 2 1 4 6 3 
5 7 2 1 4 6 3 
5 2 1 4 6 3 
5 2 1 4 3 
2 1 4 3 
2 4 3 
2 4 
4 

Process finished with exit code 0