python __getitem__()方法中LinkedList的实现

Question

我正在 python(3.7.4) 中实现 LinkedList，模块的代码如下：-

链表.py

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

class LinkedList(Node):
    def __init__(self):
        self.__head = None
        self.__cur = None
        self.__count = 0

    def add(self,value):
        if self.__head is None:
            self.__cur = Node(value)
            self.__head = self.__cur
        else:
            self.__cur.ref = Node(value)
            self.__cur = self.__cur.ref
        self.__count += 1

    def getList(self):
        temp = self.__head
        while temp!=None:
            yield temp.value
            temp = temp.ref

    def delete(self,value):
        temp = self.__head
        while temp!=None:
            if temp.value == value and temp == self.__head:
                self.__head = temp.ref
                del temp
                self.__count -= 1
                break
            elif temp.ref != None and temp.ref.value == value:
                temp_ref = temp.ref.ref
                del temp.ref
                self.__count -= 1
                temp.ref = temp_ref
                break
            temp = temp.ref

    def __getitem__(self,index):
        i = 0
        temp = self.__head

        if type(index) is int:
            while temp!=None:
                if i == index:
                    return temp.value
                temp = temp.ref
                i += 1

        elif type(index) is slice:
            if index.start is None:
                start = 0
            else:   start = index.start

            if index.stop is None:
                stop = self.__count
            else:   stop = index.stop

            if index.step is None:
                step = 1
            else:   step = index.step

            returningList = list()
            while temp!=None:
                if start <= i < stop:
                    returningList.append(temp.value)

                if i==0:
                    i = start
                    for _ in range(start):
                        if temp != None:
                            temp = temp.ref
                else:
                    i+=step
                    for _ in range(step):
                        if temp != None:
                            temp = temp.ref
            return returningList

    def __len__(self):
        return self.__count

上述所有功能都运行良好，该模块没有任何错误。

但我的问题是__getitem__()方法。我无法给出确切的逻辑，而且它太大了。

它也不适用于负指数，例如不obj[-1]返回任何内容（len(obj)这里不是 0）。

任何人都可以给我或建议我__getitem__()代码优化和降低复杂性方法的正确逻辑。

Answer 1

您可以这样做，例如：

def __getitem__(self, index):
    if isinstance(index, int):
        if index < 0:
            index = len(self) + index
        # check if `index` is valid
        # search for the element as you're currently doing.
    elif isinstance(index, slice):
        return [self[i] for i in range(len(self))[index]]
    else:
        raise ValueError(f'Linked list cannot be indexed with values of type {type(index)}')

更新：上面的代码非常简洁，但也非常慢。如果我没记错的话，它比 好一点，而下面的O(n**2)代码至少快 71.58 倍（做），并且应该大约是linkedListWith500Elements[::-1]O(n)!

这应该更快，因为它不会每次都迭代列表来检索切片的下一个元素：

class LinkedList:
    ...

    def __iter__(self):
        temp = self.__head
        while temp is not None:
            yield temp.value
            temp = temp.ref

    def __getitem__(self, index):
        if isinstance(index, int):
            if index < 0:
                index = len(self) + index

            for i, value in enumerate(self):
                if i == index:
                    return value
            raise IndexError(f'{type(self).__name__} index {index} out of range(0, {len(self)})')
        elif isinstance(index, slice):
            rangeOfIndices = range(len(self))[index]
            isRangeIncreasing = rangeOfIndices.start <= rangeOfIndices.stop + 1 and rangeOfIndices.step > 0


            rangeOfIndices = iter(rangeOfIndices) if isRangeIncreasing else reversed(rangeOfIndices)

            retval = []  # you can preallocate this...
            updateRetval = retval.append if isRangeIncreasing else (lambda value: retval.insert(0, value))  # ...and change this accordingly, although I haven't tested whether it'll be faster

            try:
                searchingForIndex = next(rangeOfIndices)
            except StopIteration:
                return retval

            temp = self.__head   
            for i, element in enumerate(self):
                if temp is None:
                    break

                if i == searchingForIndex:
                    updateRetval(temp.value)

                    try:
                        searchingForIndex = next(rangeOfIndices)
                    except StopIteration:
                        return retval

                temp = temp.ref

            return retval
        raise ValueError(f'{type(self).__name__} can only be indexed with integers or slices (not {type(index)})')

预分配列表应该快 22% 左右：

...
rangeOfIndices = range(len(self))[index]
isRangeIncreasing = rangeOfIndices.start <= rangeOfIndices.stop + 1 and rangeOfIndices.step > 0

# preallocate the list...     
retval = [None] * len(rangeOfIndices)   

if isRangeIncreasing:
    retvalIndex = 0
    rangeOfIndices = iter(rangeOfIndices)
    # ...and use a different update function
    def updateRetval(value):
        nonlocal retvalIndex
        retval[retvalIndex] = value
        retvalIndex += 1
else:
    retvalIndex = len(retval) - 1
    rangeOfIndices = reversed(rangeOfIndices)
    def updateRetval(value):
        nonlocal retvalIndex
        retval[retvalIndex] = value
        retvalIndex -= 1

try:
...