B02-数据结构-线性结构-线性表链式表示&单链表

数据结构-线性结构-线性表链式表示&单链表

一、线性表的链式表示

1.1、线性表的链式表示的存储结构特点

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续，也可以是不连续的）。

1.2、线性表的链式表示的节点组成

为了表示每个数据元素a[i]与其直接后继数据元素a[i+1] 之间的逻辑关系，对数据元素 a[i] 来说，除了存储本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素 a[i] 的存储映像，称为节点（node）。它包括两个域:

• 数据域：存储数据元素信息的域
• 指针域：存储直接后继存储位置的域

N个节点链接成一个链表，即为线性表的链式存储结构。又由于此链表只包含一个指针域，故又称线性链表或单链表。
（a[0], a[2], a[3], … , a[n-1]）

1.3、线性表的链式表示的示例

二、单链表

2.1、定义

N个节点链接成一个链表，即为线性表的链式存储结构。又由于此链表只包含一个指针域，故又称线性链表或单链表。

2.2、单链表的结构示例

假设这样一个链表， 如下

(ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)

由于链式表的特性，其整个链表的存取必须从头指针开始进行。头指针指示链表中的第一个节点（即第一个数据元素的存储映像）的存储位置，同时由于最后一个数据元素没有直接后继，则线性链表中最后一个节点的指针为空。

物理存储示例

逻辑示例

2.3、创建链表

2.3.1、创建链表的方法

上面展示了单链表的逻辑样子，那么我们怎么实际操作，让一个一个节点变成这种逻辑样子了？

要实现这种逻辑结构，我们有两种方法

• 头插法：新添加的节点作为头部（即head指向的节点），特点倒序，第一个插入的元素在最后面
• 尾插法：新添加的节点作为尾部，特点正序，第一个插入的元素在最前面

2.3.2、头插法创建链表步骤

第一步：将head指向第一个元素a[0], a[0]的next指向None，如下图所示

第二步：将第二个元素a[1]的next指向第一个元素a[0]，如下图所示

第三步：将head指向第二个元素a[2],如下图所示

同样的三步，来创建链表的第三个节点a[2]，以及之后的节点a[n]

2.3.3、尾插法创建链表步骤

由于链表本身是没有记录尾部在哪个节点，故需要另外一个指针，告知链表的最后一个节点。

第一步：开始 head 是指向第一个元素a[0], a[0] 的next指向 None。同时一个指针 tail （用于标识最后一个节点） 也指向第一个元素a[0]。如下图所示

第二步：将第一个元素 a[0 ]的 next 指向，先添加的节点 a[1]

第三步：将 tail 指向第二个元素a[1]，a[1]的 next 指向 None

同样的三步，来创建链表的第三个节点a[2]，以及之后的节点a[n]

2.4、使用链表

2.4.1、查找、访问、遍历元素

• 查找：查找对应值的下标
• 访问：通过下标访问对应元素值
• 遍历：打印链表所有元素的值

实现思路

假设存在如下一个链表：

无论是访问、遍历、查找列表元素，我们都需要从链表头（head）开一个一个访问。这样我们需要一个标识，标识我们当前遍历的位置。于是我们引入一个标识 cur，来记录当前访问节点的位置。

第一步，创建一个指针，用于表明的当前节点位置。开始 cur 指向 链表的第一个节点（通head一样）。如图所示

第二步，判断当前节点是否是需要的。如果不是，我们需要访问下一个节点。这样我们就要将cur 指向链表当前节点的下一个节点（即当前节点next指向的节点）。通过cur = cur.next 即可实现。如果是，我们就返回对应值或者下标。

2.4.2、插入元素

假如当前链表如下

现在我们希望在a[1]的节点后面插入一个元素，作为新的a[2]
第一步：创建一个标识 cur ，指向即将要插入的位置的前一个，即 a[1] 的位置。

第二步：将要插入的元素的next ， 指向当前 cur 指向节点 其next指向 的节点，即a[2]。 node.next = cur.next

第三步：将cur.next 指向 插入的节点 cur.next = node

2.4.3、删除元素

接着上面的情况，我们要删除a[2]对应的节点，如下图所示

第一步：找到要删除的节点（a[2]）前一个节点（a[1]），我们用 cur 指向a[1]

第二步：将cur（a[1]）的next 指向a[3]， 即 cur.next = cur.next.next

第三步：a[2]的next 指向 None

2.5、Python实现代码示例

class Node:
    def __init__(self, data):
        # 链表节点数据域
        self.data = data
        # 链表节点指针域
        self.next = None


class SingleLinkedList:
    """
    单链表
    """
    def __init__(self, li):
        """
        作用：单链表初始化(尾插法)
        使用方法：SingleLinkedList(
        :param li:
        """
        self.head = None        # 单链表头
        self.length = len(li)      # 单链表长度，节点个数
        self.create_list_tail(li)   # 使用尾插法创建链表

    def create_list_head(self, li):
        """
        通过头插入创建单链表
        :param li: 对应链表数据，比如['ZHAO', 'QIAN', 'SUN', 'LI', 'ZHOU', 'WU', 'ZHENG', 'WANG']
        :return:
        """
        # 链表头指向第一个节点
        self.head = Node(li[0])
        for data in li[1:]:
            # 创建新的节点
            node = Node(data)
            # 新节点next指向，之前头节点指向的节点
            node.next = self.head
            # 链表头指向新的节点
            self.head = node

    def create_list_tail(self, li):
        """
        通过尾插法创建单链表
        :param li: 对应链表数据，比如['ZHAO', 'QIAN', 'SUN', 'LI', 'ZHOU', 'WU', 'ZHENG', 'WANG']
        :return:
        """
        # 链表头指向第一个节点
        self.head = Node(li[0])
        # 链表尾指向第一个节点
        tail = self.head
        for data in li[1:]:
            # 创建新的节点
            node = Node(data)
            # 当前节点的next指向下一个节点
            tail.next = node
            # 链表尾指向新创建的节点
            tail = node

    def search_ele(self, ele_data):
        """
        在静态单链线性表中，查找第一个值为ele_data的元素
        若找到返回对应的序列，否则返回-1
        :param ele_data: 元素的值
        :return: i 位置，从0开始, 如果不存在返回-1
        """
        i = 0
        cur = self.head
        while cur.next:
            if cur.data == ele_data:
                return print(i)
            else:
                cur = cur.next
                i += 1
        else:
            return print(-1)

    def visit_ele(self, index):
        """
        在静态单链线性表中，通过下标访问元素
        :param index: 链表下标
        :return: 返回对应元素, 若下标不在链表长度范围内，返回None
        """
        if type(index) is int and 0 <= index <= self.length:
            i = 0
            cur = self.head
            while i < index:
                cur = cur.next
                i += 1
            else:
                return print(cur.data)
        else:
            return print('下标异常')

    def traverse_ele(self):
        """
        在静态单链表线性表中，遍历整个链表
        :return: 返回整个链表
        """
        i = 0
        cur = self.head
        while cur.next:
            print('%s(%s)' % (cur.data, i), end=' ')
            cur = cur.next
            i += 1

    def insert_ele(self, index, ele_data):
        """
        根据下标插入元素
        :param index: 插入元素的位置
        :param ele_data: 插入的元素
        :return:
        """
        if type(index) is int and 0 <= index <= self.length:
            # 创建需要插入的元素节点
            node = Node(ele_data)
            i = 0
            cur = self.head
            # 从头开始遍历元素，根据index查找对应位置的前一个
            while i < index - 1:
                cur = cur.next
                i += 1
            else:
                node.next = cur.next
                cur.next = node
                self.length += 1
                return True
        else:
            return print('下标异常')

    def delete_ele(self, index):
        """
        根据下标删除元素
        :param index: 需要删除元素的下标
        :return:
        """
        if type(index) is int and 0 <= index <= self.length:
            i = 0
            cur = self.head
            # 从头开始遍历元素，根据index查找对应位置的前一个
            while i < index - 1:
                cur = cur.next
                i += 1
            else:
                node = cur.next
                cur.next = cur.next.next
                node.next = None
                self.length -= 1
                return True
        else:
            return print('下标异常')


if __name__ == '__main__':
    # 创建链表
    l1 = SingleLinkedList(['ZHAO', 'QIAN', 'SUN', 'LI', 'ZHOU', 'WU', 'ZHENG', 'WANG'])
    # 查找元素‘SUN'对应的位置
    l1.search_ele('SUN')
    # 查找下标为1的对应元素
    l1.visit_ele(1)
    # 遍历整个链表
    l1.traverse_ele()
    print('')
    # 链表添加某个元素
    l1.insert_ele(2, 'NEW')
    l1.traverse_ele()
    print('')
    # 链表删除某个元素
    l1.delete_ele(2)
    l1.traverse_ele()

2.6、单链表操作的时间复杂度对比

操作	时间复杂度	说明
访问	O(n)	我们可以通过下标访问，由于链表需要从头开始遍历，最好情况是第一个就找到，时间复杂度O(1) 。 最后情况是最后一个，时间复制度是 O(n) ， 平均情况是 O(1/2 * n) 。整体来说认为是O(n)
查找	O(n)	我们可以通过下标访问，由于链表需要从头开始遍历，最好情况是第一个就找到，时间复杂度O(1) 。 最后情况是最后一个，时间复制度是 O(n) ， 平均情况是 O(1/2 * n) 。整体来说认为是O(n)
插入	O(n)	插入涉及两个步骤，第一步找到元素位置，找到元素位置的时间复杂度为O(n) ，第二步修改相关next 时间复杂度为O(1)。整体就是O(n) + O(1),我们认为整体时间复杂度是O(n)
删除	O(n)	插入涉及两个步骤，第一步找到元素位置，找到元素位置的时间复杂度为O(n) ，第二步修改相关next 时间复杂度为O(1)。整体就是O(n) + O(1),我们认为整体时间复杂度是O(n)