python实现双向循环链表

# -*- coding:utf-8 -*-

# __author__ :kusy

# __content__:双向循环链表实现

# __date__:2018/9/29 16:34

# 节点类

class DNode(object):

    def __init__(self, prev, next, value):

        self.prev = prev    # 前驱

        self.next = next    # 后继

        self.value = value  # 值

class DoubleLinkTable(object):

    def __init__(self):

        self.nCount = 0     # 节点个数

        self.nHead = DNode(None, None, None)    # 表头

        self.nHead.prev = self.nHead    # 表头的前驱后继都是自己

        self.nHead.next = self.nHead    # 表头的前驱后继都是自己

        self.node = self.nHead

    # 节点数目

    def size(self):

        return self.nCount

    # 判断链表是否为空

    def is_empty(self):

        return self.nCount == 0

    # 获取index位置的节点

    def getnode(self, index):

        if index == 0:

            return self.nHead

        if index < 0 or index > self.nCount:

            raise Exception('IndexOutOfBounds')

        # 二分正向查找

        if index < self.nCount / 2:

            self.node = self.nHead.next

            i = 0

            while i < index - 1:

                self.node = self.node.next

                i += 1

            return self.node

        # 反向查找剩余部分

        self.node = self.nHead.prev

        rindex = self.nCount - index

        j = 0

        while j < rindex:

            self.node = self.node.prev

            j = j + 1

        return self.node

    # 获取index位置节点的值

    def get(self, index):

        return self.getnode(index).value

    # 插入新节点（后插）

    def insert(self, index, value):

        now_node = self.getnode(index)

        new_node = DNode(None,None,value)

        new_node.prev = now_node

        new_node.next = now_node.next

        now_node.next.prev = new_node

        now_node.next = new_node

        self.nCount += 1

    # 删除节点

    def delete(self, index):

        if index == 0:

            raise Exception('0 is not allowed!')

        now_node = self.getnode(index)

        now_node.prev.next = now_node.next

        now_node.next.prev = now_node.prev

        self.nCount -= 1

if __name__ == '__main__':

    dlt = DoubleLinkTable()

    # 头节点下标为0

    dlt.insert(0, 12)

    dlt.insert(1, 13)

    dlt.insert(1, 14)

    print('---------------------------')

    for i in range(dlt.nCount+1):

        print(i, ':', dlt.get(i))

    print('size:', dlt.nCount)

    dlt.delete(2)

    print('-------after delete--------')

    for i in range(dlt.nCount+1):

        print(i, ':', dlt.get(i))

    print('size:', dlt.nCount)

C:\Users\suneee\AppData\Local\Programs\Python\Python36\python.exe E:/wangjz/PyWorkSpace/LearnPython/PY0929/double_linktable.py

---------------------------

0 : None

1 : 12

2 : 14

3 : 13

size: 3

-------after delete--------

0 : None

1 : 12

2 : 13

size: 2

Process finished with exit code 0