您现在的位置是： 网站首页 >> Python Python

链表是一种物理存储单元上非连续性、非顺序性的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点（链表中每一个元素称为节点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在内存或磁盘上的顺序。数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

这里就用Python实现了单向和双向链表数据结构。

一，实现单向链表

首先实现单向链表节点

# 单向链表节点
class LinkListNode:

    # 初始化链表节点
    def __init__(self, data):

        self.data = data
        self.next = None

    # 检测节点数据
    def has_value(self, value):

        if self.data == value:
            return True
        else:
            return False

这里我定义了链表节点,初始化了存储数据的数据域(data),以及存储下一个节点位置的指针域(next),和一个检测节点数据的方法







单向链表编码

# 单向链表
class UnLinkList:

    def __init__(self):

        # 初始化链表头尾数据
        self.head = None
        self.tail = None
        self.length = 0

    # 添加数据到链表
    def add_item_to_list(self, item):

        if not isinstance(item, LinkListNode):
            item = LinkListNode(item)
        if self.head is not None:
            if self.tail is not None:
                self.tail.next = item
        else:
            self.head = item
        self.tail = item

    # 根据索引删除链表中某个数据
    def remove_item_by_index(self, index):

        if isinstance(index, int):
            if index > self.list_length() - 1 or index < 0:
                raise ValueError("the index out of the list range")
        else:
            raise TypeError("must be int, no type {}".format(type(index)))

        current_index = 0
        current_node = self.head
        previous_node = None

        while current_node is not None:
            if current_index == index:
                if previous_node is not None:
                    previous_node.next = current_node.next
                else:
                    current_node = current_node.next
            current_index += 1
            previous_node = current_node
            current_node = current_node.next

    # 链表元素长度
    def list_length(self):

        current_node = self.head
        while current_node is not None:
            self.length += 1
            current_node = current_node.next

        return self.length

    # 输出链表
    def output_list(self):

        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next

    # 根据值查找链表数据
    def search(self, value):

        results = []
        current_node = self.head
        while current_node is not None:
            if current_node.has_value(value):
                results.append(current_node)
            current_node = current_node.next

        return results

这里实现了向链表中添加以及根据索引从链表中移除数据,获取链表长度,输出链表及查找链表等方法.

初始化了头部数据以及尾部数据,链表长度.







二,双向链表实现

双向链表相对于单向链表来说,就是增加了一个指向上一个节点地址的指针域(previous),大部分相似,但在从链表中移除数据时就需要多考虑几个步骤.




双向链表节点

class DbLinkListNode(LinkListNode):

    def __init__(self, data):

        self.previous = None
        super(DbLinkListNode, self).__init__(data)

这里就直接继承了单向链表节点,然后添加了previous属性




下面是实现双向链表代码

class DbLinkList(UnLinkList):

    def __init__(self):

        super(DbLinkList, self).__init__()

    def add_item_to_list(self, item):

        if not isinstance(item, DbLinkListNode):
            item = DbLinkListNode(item)
        if self.head is not None:
            if self.tail is not None:
                item.previous = self.tail
                self.tail.next = item
        else:
            self.head = item
        self.tail = item

    def remove_item_by_index(self, index):


        if not isinstance(index, int):
            raise TypeError("must be int, not type {}".format(type(index)))
        if index > self.list_length() - 1 or index < 0:
            raise ValueError("the index out of the list range")

        current_index = 0
        current_node = self.head

        while current_node is not None:
            if current_index == index:
                if current_node.previous is not None:
                    if current_node.next is not None:
                        current_node.previous.next = current_node.next
                        current_node.next.previous = current_node.previous
                    else:
                        current_node.previous.next = current_node.next
                else:
                    if current_node.next is not None:
                        self.head = current_node.next
                        self.head.previous = current_node.previous
                    else:
                        self.head = current_node.next

            current_index += 1
            current_node = current_node.next

这里同样是继承了单向链表,然后重写了add和remove方法,可以看见remove操作中,相比于单向链表多了几个步骤.




最后运行一下看效果





这里只实现了单向链表以及双向链表,循环链表类似,只需要在双向链表的基础上将尾部节点指向下一个节点地址的指针由指向None改为指向头部节点,同样头部节点指向上一个节点地址的指针由指向None改为指向尾部节点.