数据结构之链表


概念

python内置的数据结构列表是一种顺序表,列表在内存中占用一段连续的内存空间,列表的第一项数据的地址就是列表的地址,数据项的下标其实可以看做是相对于列表起始地址的偏移量,这也就是为什么列表的查询的时间复杂度是O(1)的,而插入insert操作的时间复杂度是O(n)的,因为要把插入位置后面的每个元素都要往后移动一位。

列表对于需要频繁查询数据的情况很合适,但如果需要频繁的插入删除数据项的话,列表的性能就会趋向于O(n)。

此时需要一种新的数据结构,使得数据的插入和删除操作的时间复杂度尽量降低,这就需要链表这种数据结构。

链表,顾名思义,所有的数据项像珠子一样串成一个链,不同的数据项之间通过地址引用连接,因此每个数据项不光要保存自己的数据值,还要指出下一项在内存中的地址,这样一来,数据项可以分散在内存中的任意位置,不需要连续的内存空间存储整个链表,同时,数据的插入删除操作只需要操作插入删除的数据项的相邻两项,时间复杂度降到了O(1)。

构成链表的基本数据结构是节点。每一个节点对象都需要保存两项信息,首先,节点必须包含保存的数据项的信息,称之为节点的数据变量,其次,节点必须保存指向下一个节点的引用

这样的话,链表的大体结构就如下图所示:

图中n1、n2、n3、n4表示数据变量。这时有一个问题,最后一个节点的第二部分应该指向哪里呢,我们加入一个特殊的引用值None,指向None的引用代表着后面没有元素,同时,在首节点的前面加一个head节点,保存第一个节点的地址的引用,如果head等于None,说明是空链表。完整的链表结构如下所示:

代码实现

class Node(object):
    """
    定义节点类
    data: 节点存储的数据
    pnext: 保存下一节点对象
    """
    def __init__(self, data, pnext=None):
        self.data = data
        self.next = pnext

    def __repr__(self):
        """
        重构输出方法,对比__str__方法
        将self.data按照字符串输出
        """
        return str(self.data)

class ChainTable(object):
    """
    定义链表类
    """
    def __init__(self):
        """初始化空链表,头结点的指向为None,链表长度为0"""
        self.head = None
        self.length = 0

    def isEmpty(self):
        """
        判断链表是否为空链表
        :return: True:空链表
        """
        return self.length == 0

    def append(self, dataOrNode):
        """
        链表末端添加节点
        :param dataOrNode: 待添加的节点或数据
        :return:
        """
        #判断参数是不是节点类,不是节点的话要以参数为数据变量建立节点
        if isinstance(dataOrNode, Node):
            item = dataOrNode
        else:
            item = Node(dataOrNode)

        #链表是空链表,直接将新节点作为第一个结点
        if not self.head:
            self.head = item
            self.length += 1
        #链表不为空,遍历到链表末尾添加
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = item
            self.length += 1

    def delete(self, index):
        """
        按索引删除节点
        :param index: 待删除节点的索引号
        :return:
        """
        #判断可能的异常情况
        if self.isEmpty():
            print("thie chain table is empty")
            return
        if index < 0 or index >= self.length:
            print("error:out of index")
            return

        #如果删除的是头结点,直接将头结点指向头结点的下一项
        if index == 0:
            self.head = self.head.next
            self.length -= 1
            return

        #否则,遍历链表至删除的位置,将删除节点的前一项指向删除节点的下一项
        j = 0
        node = self.head
        pnext = self.head
        while node.next and j < index:
            pnext = node
            node = node.next
            j += 1
        if j == index:
            pnext.next = node.next
            self.length -= 1

    def insert(self, index, dataOrNode):
        """
        在链表的index位置插入节点
        :param index: 新节点的插入位置
        :param dataOrNode: 插入的节点或数据
        :return:
        """
        #判断可能的异常情况
        if self.isEmpty():
            print("thie chain table is empty")
            return
        if index < 0 or index >= self.length:
            print("error:out of index")
            return

        #判断dataOrNode的类型
        if isinstance(dataOrNode, Node):
            item = dataOrNode
        else:
            item = Node(dataOrNode)

        #如果插入位置是头结点,新节点指向原来的头结点,更新头结点为新节点,链表长度+1
        if index == 0:
            item.next = self.head
            self.head = item
            self.length += 1
            return

        #否则,遍历链表至新节点要添加的位置,老节点与前节点的连接,插入新节点,前节点指向新节点,新节点指向旧节点
        j = 0
        node = self.head
        pnext = self.head
        while node.next and j < index:
            pnext = node
            node = node.next
            j += 1
        if j == index:
            item.next = node
            pnext.next = item
            self.length += 1

    def update(self, data, index):
        """
        更新指定位置的节点值
        :param data: 新的节点数据
        :param index: 待更新节点的索引
        :return:
        """
        #判断异常情况
        if self.isEmpty():
            print("thie chain table is empty")
            return
        if index < 0 or index >= self.length:
            print("error:out of index")
            return

        #遍历链表至更新位置,更改节点值
        j = 0
        node = self.head
        while node.next and j < index:
            node = node.next
            j += 1
        if j == index:
            node.data = data

    def getItem(self, index):
        """
        根据索引查找节点数据
        :param index: 查找节点的索引
        :return: 节点存储的数据
        """
        if self.isEmpty():
            print("thie chain table is empty")
            return
        if index < 0 or index >= self.length:
            print("error:out of index")
            return

        j = 0
        node = self.head
        while node.next and j < index:
            node = node.next
            j += 1

        return node.data

    def getIndex(self, data):
        """
        根据数据查找节点索引
        :param data: 节点数据
        :return: 节点索引
        """
        if self.isEmpty():
            print("thie chain table is empty")
            return

        j = 0
        node = self.head
        while node:
            if node.data == data:
                return j
            else:
                node = node.next
                j += 1

        if j == self.length:
            print("%s not found" % str(data))
            return

    def clear(self):
        """清空链表"""
        self.head = None
        self.length = 0

    def __repr__(self):
        """
        重构输出方法
        :return: 按数据+空格方式输出
        """
        if self.isEmpty():
            return "empty chain table"
        j = 0
        node = self.head
        nlist = ' '
        while node and j < self.length+5:
            nlist += str(node.data) + ' '
            node = node.next
            j += 1
        return nlist

    def __getitem__(self, index):
        """
        重构get方法
        :param item: 节点索引
        :return: 节点数据
        """
        if self.isEmpty():
            print("thie chain table is empty")
            return
        if index < 0 or index >= self.length:
            print("error:out of index")
            return

        return self.getItem(index)

    def __setItem__(self, data, index):
        """
        重构更新节点方法
        :param data: 更新节点数据
        :param index: 更新节点索引
        :return:
        """
        if self.isEmpty():
            print("thie chain table is empty")
            return
        if index < 0 or index >= self.length:
            print("error:out of index")
            return
        self.update(data, index)

    def __len__(self):
        """
        重构链表长度方法
        :return: 链表长度
        """
        return self.length


def test_chaintable():
    """测试链表类"""
    chaintable = ChainTable()

    print(chaintable.isEmpty())

    for i in range(10):
        chaintable.append(i)

    print(chaintable)
    print(len(chaintable))

    chaintable.update(10, 1)
    print(chaintable)

    chaintable.delete(3)
    print(chaintable)

    chaintable.insert(3, 30)
    print(chaintable)

    print(chaintable.getItem(3))
    print(chaintable[3])

    chaintable.insert(0, 100)
    print(chaintable)

    print(chaintable.head)

运行测试程序,输出结果为:

True
 0 1 2 3 4 5 6 7 8 9 
10
 0 10 2 3 4 5 6 7 8 9 
 0 10 2 4 5 6 7 8 9 
 0 10 2 30 4 5 6 7 8 9 
30
30
 100 0 10 2 30 4 5 6 7 8 9 
100

与预期结果相符。


文章作者: likai
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 likai !
评论
 上一篇
物理内存管理 物理内存管理
操作系统内存管理系列之一
2020-07-29
下一篇 
python数据结构之双端队列 python数据结构之双端队列
概念双端队列是一种有次序的数据集合,跟队列类似,也有首端与尾端之分,但与队列不同的是,双端队列的首端和尾端都可以进行入队和出队操作,即新元素既可以添加到首端,也可以添加到尾端,同理,已有的元素也可以从任意一端移除。因此,双端队列集合了队列和
2020-07-27
  目录