栈、队列(链表实现)

时间：2019-09-20 22:49:38 阅读：130 评论：0 收藏：0 [点我收藏+]

1. 链表(单链表、循环链表、双链表、循环双链表)的实现

　　1.1单链表

　　　　每一个节点由数据区及指向下一节点的指针域组成

　　技术分享图片

#coding:utf-8
class SingleLinkedList(object):
    """链表类"""
    __slots__ = [‘_head‘, ‘_size‘]

    class _Node(object):
        """节点类"""
        __slots__ = [‘data‘, ‘next‘]
        def __init__(self, data, next):
            self.data = data
            self.next = next

    def __init__(self):
        self._head = None
        self._size = 0

    def is_empty(self):
        """判断链表是否为空"""
        return self._size==0

    @property
    def length(self):
        return self._size

    def insert(self, index: int, data):
        """任意位置数据插入"""
        if index>self._size or index<0:
            raise IndexError("out of index or invalid")
        else:
            cur_node = self._Node(data, None)
            if self.is_empty():
                self._head = cur_node
            else:
                node = self._head
                count = 0
                while node != None:
                    if index==0:
                        cur_node.next = node
                        self._head = cur_node
                        break
                    elif count==index-1 and index!=0:
                        cur_node.next = node.next
                        node.next = cur_node
                        break
                    count += 1
                    node = node.next
            self._size += 1

    def remove(self, index):
        """任意位置数据删除"""
        if index>self._size or index<0:
            raise IndexError("out of index or invalid")
        else:
            if self.is_empty():
                raise Exception("This singleLinkedList is empty")
            else:
                node = self._head
                count = 0
                while node != None:
                    if index==0:
                        self._head = node.next
                        break
                    elif index!=0 and count+1==index:
                        node.next = node.next.next
                        break
                    count += 1
                    node = node.next
            self._size -= 1

    def __str__(self):
        flag = "<-"
        res = ""
        node = self._head
        while node != None:
            if node.next==None:
                res += ‘[‘+str(node.data)+‘]‘
            else:
                res += (‘[‘+str(node.data)+‘]‘+flag)
            node = node.next
        return res


if __name__ == ‘__main__‘:
    link = SingleLinkedList()
    link.insert(0, 1)
    link.insert(0, 0)
    link.insert(1, 11)
    link.insert(0, 22)
    link.insert(0, 4)
    link.insert(2, 8)   # [4]<-[22]<-[8]<-[0]<-[11]<-[1]
    link.remove(0)  # [22]<-[8]<-[0]<-[11]<-[1]
    link.remove(3)  # [22]<-[8]<-[0]<-[1]
    print(link)