elab_mvp/test/linked_list.py

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


class LinkedListOneway(object):
    def __init__(self, node=None):
        self.__head = node

    def get_head(self):
        return self.__head

    def __len__(self):
        cur = self.__head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

    def is_empty(self):
        return self.__head == None

    def add(self, value):
        """
        头插法
        先让新节点的next指向头节点
        再将头节点替换为新节点
        顺序不可错，要先保证原链表的链不断，否则头节点后面的链会丢失
        """
        node = Node(value)
        node.next = self.__head
        self.__head = node

    def append(self, value):
        """
            尾插法
        :param value:
        :return:
        """
        node = Node(value)
        cur = self.__head
        if self.is_empty():
            self.__head = node
        else:
            while cur.next:
                cur = cur.next
            cur.next = node

    def insert(self, pos, value):
        # 插入指定位置
        if pos <= 0:
            self.add(value)
        elif pos > len(self) - 1:
            self.append(value)
        else:
            node = Node(value)
            prior = self.__head
            count = 0
            # 在插入位置的前一个节点停下
            while count < (pos - 1):
                prior = prior.next
                count += 1
            # 先将插入节点与节点后的节点连接，防止链表断掉，先链接后面的，再链接前面的
            node.next = prior.next
            prior.next = node

    def remove_value(self, value):
        """
        删除值
        :param value:
        :return:
        """
        curr = self.__head
        if curr is None:
            raise Exception("链表为空，无法删除值")
        i = 0
        while curr:
            if curr.value == value:
                break
            curr = curr.next
            i += 1
        prior = self.__head
        j = 0
        k = i
        while prior:
            if j == k - 1:
                print(j)
                break
            prior = prior.next
            j += 1
        if i == 0:
            self.__head = self.__head.next
        elif i > self.__len__() - 1:
            raise Exception("未查询到此数据")
        elif 0 < i < self.__len__() - 1:
            nextnext = prior.next
            prior.next = nextnext.next
        else:
            pass
        print("删除的值为:%s 位置为:%s" % (value, i))

    def remove_index(self, index):
        cur = self.__head
        if cur is None:
            raise Exception('链表为空，无法删除')
        if index > self.__len__():
            raise Exception('下标越界')
        stu = self.__head
        for i in range(index - 1):
            stu = stu.nex
        temp = stu.next
        stu.next = temp.next

    def search(self, value):
        cur = self.__head
        if cur is None:
            raise Exception('链表为空')
        while cur is not None:
            if cur.value == value:
                return True
            else:
                cur = cur.next
        return False

    def reverse(self):
        cur = self.__head
        pre = None
        while cur:
            prenext = cur.next
            cur.next = pre
            pre = cur
            cur = prenext
        self.__head = pre

    def show(self):
        cur = self.__head
        while cur:
            print(cur.value)
            cur = cur.next


if __name__ == '__main__':
    head = LinkedListOneway()
    head.append(1)
    head.append(2)
    head.append(3)
    head.insert(2, 5)
    head.remove_value(3)
    # head.reverse()
    head.show()