链表实现不难,但里面涉及到Python的垃圾处理中的分代处理。

当链表删除时,被删除的链表段并没有真正意义上的被删除,可以虚幻的理解的为迷失在内存中,因为其失去了头。Python的分代处理是专门解决这类问题的,因为不太懂分代机制如何实现回收就不再赘述,有篇很好讲解文章地址是:https://www.jianshu.com/p/1e375fb40506

最后,如果担心被删部分不能被很好的回收,可以调用 gc 模块来实现主动垃圾回收。

import gc


class Node:
    def __init__(self, init_data):
        self.__data = init_data
        self.__next = None

    def get_data(self):
        return self.__data

    def get_next(self):
        return self.__next

    def set_data(self, new_data):
        self.__data = new_data

    def set_next(self, new_next):
        self.__next = new_next


class UnorderedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def add_head(self, item):
        temp = Node(item)
        temp.set_next(self.head)
        self.head = temp

    def add_tail(self, item):
        current = self.head
        temp = Node(item)
        if current is None:
            self.head = temp
        else:
            while current.get_next() is not None:
                current = current.get_next()
            else:
                current.set_next(temp)

    def insert(self, item, index):
        temp = Node(item)
        if index > self.size()+1:
            raise Exception("The linked list is not that long")
        elif index == 0:
            self.add_head(item)
        elif index == self.size() + 1:
            self.add_tail(item)
        else:
            current = self.head
            count = 0
            while count < index-1:
                count += 1
                current = current.get_next()
            else:
                fracture = current.get_next()
                current.set_next(temp)
                temp.set_next(fracture)

    def del_head(self):
        if self.size() == 0:
            raise Exception("The linked list is empty")
        else:
            current = self.head
            self.head = current.get_next()
        gc.collect(1)
        return current.get_data()

    def del_tail(self):
        if self.size() == 0:
            raise Exception("The linked list is empty")
        else:
            current = self.head
            size = self.size()
            count = 1
            while count < size-1:
                count += 1
                current = current.get_next()
            else:
                del_data = current.get_next().get_data()
                current.set_next(None)
        gc.collect(1)
        return del_data

    def delete(self, index):
        if index > self.size()+1:
            raise Exception("The linked list is not that long")
        elif index == 0:
            self.del_tail()
        elif index == self.size():
            self.del_tail()
        else:
            current = self.head
            count = 1
            while count < index - 1:
                count += 1
                current = current.get_next()
            else:
                fracture = current.get_next().get_next()
                del_data = current.get_next().get_data()
                current.set_next(fracture)
            gc.collect(1)
            return del_data

    def size(self):
        current = self.head
        count = 0
        while current is not None:
            count += 1
            current = current.get_next()
        return count

    def show(self):
        slow_list = []
        current = self.head
        while current is not None:
            slow_list.append(current.get_data())
            current = current.get_next()
        return slow_list

results matching ""

    No results matching ""

    results matching ""

      No results matching ""