表 （python实现），,python 中的顺

python 中的顺序表

　　在python中的顺序表其实就是list。是动态数组（Cpython）。

　　从细节上看，Python中的列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着，每次添加或删除一个元素时，由引用组成的数组需要该标大小（重新分配）。幸运的是，Python在创建这些数组时采用了指数分配，所以并不是每次操作都需要改变数组的大小。但是，也因为这个原因添加或取出元素的平摊复杂度较低。
　　

单链表

class Node(object):    def __init__(self, item):        self.elem = item        self.next = None  #下一个节点的内存地址class singleLinkList():    def __init__(self):        self.__head = None    #私有属性 有限范围在此类中。 链表头只存下一个节点的内存地址    def is_empty(self)-> bool:        return self.__head is None  #is 判断两变量内存地址是否相等    def length(self)-> int:        if self.is_empty():            return 0        count = 0        cur = self.__head        while cur is not self.__head:   #while cur            cur += 1            cur = cur.next        return count    def add(self, item):        #头插法        node = Node(item)        node.next = self.__head        self.__head = node    def travel(self):        if self.is_empty():            return        cur = self.__head        while cur:            print(cur.elem)            cur = cur.next    def append(self,item):        if self.is_empty():            self.add(item)        else:            cur = self.__head            node = Node(item)            while cur:                cur = cur.next            cur=node    def insert(self,index:int,item:int):        if index <= 0:            self.add(item)        elif index>self.length()-1:            self.append(item)        else:            cur = self.__head            n=1            while cur.next:                if n==index:                    break                n += 1                cur = cur.next        node = Node(item)        node.next = cur.next  # 被插节点next 赋给 node‘s next        cur.next = node       # 被插节点的next 指向 node    def remove(self,item):        if self.is_empty:  # 节点为空的情况            raise ValueError("null")        cur = self.__head        pre = None        if self.item == item:            self.__head = cur.next        while cur.next:            pre=cur            cur=cur.next            if cur.item == item:                pre.next = cur.next

循环单链表

class Node():    def __init__(self, item):        self.item = item        self.next = None# 单向循环链表class SingleLink():    def __init__(self):        self.__head = None    def is_empty(self):        return self.__head is None    def length(self):        if self.is_empty():            return 0        n = 1        cur = self.__head        while cur.next != self.__head:            cur = cur.next            n += 1        return n    def travel(self):        if self.is_empty():            return False        cur = self.__head        while cur.next != self.__head:            print(cur.item)            cur = cur.next    def add(self, item):        """首插法        """        node = Node(item)        if self.is_empty():            self.__head = node            node.next = self.__head        else:            cur = self.__head            node.next = self.__head  # 插入节点先指向head            while cur.next != self.__head:                cur = cur.next            cur.next = node            self.__head = node    def append(self, item):        """尾插法        """        node = Node(item)        if self.is_empty():            self.__head = node            node.next = self._head        else:            cur = self.__head            while cur.next != self.__head:                cur = cur.next            cur.next = node            node.next = self.__head    def insert(self, pos, item):        """        插入节点        :param  pos item:        :return:        """        if pos < 0:            self.add(item)        elif pos > (self.length()-1):            self.append(item)        else:            node = Node(item)            cur = self.__head            n = 1            while n != pos:                cur = cur.next                n += 1            node.next = cur.next            cur.next = node    def remove(self, item):        """        删除节点        :param item:        :return:        """        if self.is_empty():            return        cur = self.__head        pre = None        if cur.item == item:            # 如果链表不止一个节点            if cur.next != self._head:                # 先找到尾节点，将尾节点的next指向第二个节点                while cur.next != self._head:                    cur = cur.next                # cur 指向了尾节点                cur.next = self._head.next                self._head = self._head.next            else:                # 链表只有一个节点                self._head = None            # 头节点不是要删除的元素        else:            pre = self._head            while cur.next != self._head:                # 找到了要删除的元素                if cur.item == item:                    pre.next = cur.next                    return                else:                    pre = cur                    cur = cur.next            # 尾节点操作            if cur.item == item:                #尾部删除                pre.next = cur.next    def search(self, item):        """查找节点是否存在"""        if self.is_empty():            return False        cur = self.__head        if cur.item == item:            return True        while cur.next != self.__head:            cur = cur.next            if cur.item == item:                return True        return False

双向链表

class Node():    def __init__(self, item):        self.item = item        self.prev =None        self.next = Noneclass DLinkList(object):    """双向链表"""    def __init__(self):        self.__head = None    def is_empty(self):        """判断链表是否为空"""        return self.__head is None    def length(self):        """返回链表的长度"""        cur = self.__head        count = 0        while cur != None:            count += 1            cur = cur.next        return count    def travel(self):        """遍历链表"""        cur = self.__head        while cur != None:            print(cur.item)            cur = cur.next        print("")    def add(self, item):        """头插法"""        node = Node(item)        if self.is_empty():            self.__head = node        else:            node.next = self.__head            self.__head.prev = node            self.__head = node    def append(self, item):        """尾部插入元素"""        node = Node(item)        if self.is_empty():            # 如果是空链表，将_head指向node            self._head = node        else:            # 移动到链表尾部            cur = self._head            while cur.next != None:                cur = cur.next            # 将尾节点cur的next指向node            cur.next = node            # 将node的prev指向cur            node.prev = cur    def search(self, item):        """查找元素是否存在"""        cur = self._head        while cur != None:            if cur.item == item:                return True            cur = cur.next        return False    def insert(self, pos, item):        """在指定位置添加节点"""        if pos <= 0:            self.add(item)        elif pos > (self.length() - 1):            self.append(item)        else:            node = Node(item)            cur = self._head            count = 0            # 移动到指定位置的前一个位置            while count < (pos - 1):                count += 1                cur = cur.next            # 操作流程为顺时针1234            # 1.将node的prev指向cur            node.prev = cur            # 2.将node的next指向cur的下一个节点            node.next = cur.next            # 3.将cur的下一个节点的prev指向node            cur.next.prev = node            # 4.将cur的next指向node            cur.next = node    def remove(self, item):        """删除元素"""        if self.is_empty():            return        else:            cur = self._head            # 如果首节点的元素就是要删除的元素            if cur.item == item:                # 如果链表只有这一个节点                if cur.next == None:                    self._head = None                else:                    # 将第二个个节点的prev设置为None                    cur.next.prev = None                    # 将_head指向第二个节点                    self._head = cur.next                return            # 首节点不是要删除的节点            while cur != None:                if cur.item == item:                    # 将cur的前一个节点的next指向cur的后一个节点                    cur.prev.next = cur.next                    # 将cur的后一个节点的prev指向cur的前一个节点                    cur.next.prev = cur.prev                    break                cur = cur.next            # 尾结点删除

表 （python实现）