01. 顺序表

  • 顺序表的特点：顺序表中的数据元素本身在内存中连续存储，每个元素所占存储单元大小固定相同。
  • 如Python中的列表就是一个典型的顺序表。
  • 如定义li = [11, 22, 33, 44]，会在堆空间中开辟4个连续的空间，存放四个元素，然后再将这4个连续空间的首地址0x1234赋值给栈中的变量li。
  • 顺序表可以通过索引来获取每一个元素。

1682677702066.jpg

02. 链表

2.1 链表的基本认识

2.1.1 链表的定义

  • 链表的内存空间是不连续的，需要链表中的每一个节点保存指向上一个/下一个的指针。
  • 链表的最小存储单位被称之为节点，节点由以下一些部分组成：
    • 直接前驱pre：上一个节点的内存地址（只在双向链表中存在）；
    • 数据元素本身；
    • 直接后继next：下一个节点的内存地址（单链表和双链表都存在）

image.png

  • 转换成Python代码，我们就可以定义一个Node节点类，这个类中有pre、value和next三个属性。

    1. class Node:
    2.   def __init__(self, value):
    3.       self.pre = None  # 节点的直接前趋
    4.       self.value = value  # 存储数据元素本身
    5.       self.next = None  # 节点的直接后继

  • 节点需要存储上一个/下一个节点的内存地址的原因：

    • 对于顺序表而言，内存空间是连续的，因此只需要知道顺序表的首个地址（首个地址会赋值给变量）就可以得到顺序表中所有元素的地址，进而就可以获取顺序表中的所有元素。
    • 而对于链表而言，其内存空间是不连续的，除了变量知道首个节点的内存空间之外，其他节点之间都是没有关联的，此时就无法获取区域元素的内存地址，也就意味着无法获取元素。
    • 因此，当前节点就需要用next记录下一个节点的内存地址，用pre记录上一个节点的内存地址。此时，链表中的所有节点就像一个串一样被链接起来了。

data1.png

  • 总结：链表（以单链表为例）是将线性表中的各元素分布到存储器的不同存储块中，每个元素存储块被称之为节点；每个节点（尾节点除外）中都有一个指向下一个节点的引用，这样所得到的存储结构称之为链表结构。

    2.1.2 链表与顺序表的比较

  • 顺序表的构建需要预先知道数据的大小，然后才能到内存中申请连续的存储空间。而在进行扩容时，又需要进行数据的搬迁，使用起来并不灵活。

  • 而链表结构可以充分利用计算机的内存空间，实现灵活的内存动态管理。

    2.2 单链表的代码实现

  • 注意：对于单链表（Single Linked List）而言，没有直接前驱，只有直接后继。（即只有一个方向）

    2.2.1 节点类与单链表的基本逻辑

  • 需求描述：需要定义一个单向链表，用来存储L = (22, 33, 44)这三个数据，图解为：

image.png

  • 首先，定义一个Node节点类。由于是单向链表，因此没有直接前驱，只有直接后继。

    1. class Node:
    2.   def __init__(self, value):
    3.       self.value = value  # 存储数据元素本身
    4.       self.next = None  # 节点的直接后继

  • 接着，实例化数据，然后用节点对象.next = 下一个节点实例将节点链接起来。 ```python n1 = Node(22) n2 = Node(33) n3 = Node(44)

n2.next = n3 n1.next = n2

  1. <a name="AAkot"></a>
  2. #### 2.2.2 链表类的定义
  4. - 对于一个链表而言，头节点是很重要的，只有有了头节点，才可以有不断地next。
  5. - 以2.2.1为例，22就是head头节点。
  6. - 对于一个链表而言，一开始head是空的，而当第一个节点添加进来时，自然而言就成了head头节点。
  7. ```python
  8. class SingleLinkedList:
  9.     def __init__(self):
  10.         self.head = None

2.2.3 添加节点（追加元素）

  • 对于链表而言，链表中的所有元素都是节点，而用户传入的一般只有数据元素本身，因此追加元素的第一步就是将数据元素封装成节点对象。

    1. def append(self, item):
    2.   new_node = None(item)

  • 节点封装完成后，接下去要做的就是将节点添加到列表中了。

1682684270683.jpg

  • 若链表为空（即链表中没有一个节点时），则头节点就是当前新添加的节点。

    1. def append(self, item):
    2.   new_node = None(item)
    4.   if not self.head:
    5.       self.head = new_node
    6.       return

  • 若当前链表不为空，则先要找到当前链表的最后一个节点（即尾节点），然后将尾节点的直接后继指向新添加的节点。

  • 寻找尾节点的方法：

    • 将头节点作为起始的尾节点（因为这种情况一定不是空链表，所以头节点一定存在）。

    • 不断判断当前的尾节点是否存在下一个元素。

      • 若存在next，说明当前尾节点不是链表真正的尾节点，需要继续向后找。
      • 若next为None，则说明当前尾节点就是链表真正的尾节点，查找结束。 ```python def append(self, item): new_node = Node(item)

      if not self.head: self.head = new_node return

      找链表的尾节点

      cur = self.head while cur.next: cur = cur.next # 指针向后移动

      将尾节点的直接后继指向当前新的节点

      cur.next = new_node ```

      2.2.4 遍历链表

  • 遍历列表与2.2.3中查找尾节点的操作类似。

    1. def travel(self):
    2.   cur = self.head
    3.   while cur:  # 若当前节点不为None，则打印它的值
    4.       print(cur.value, end=" ")
    5.       cur = cur.next  # 指针向后移动
    6.   print()

    2.2.5 移除链表中的节点（01:10:47）

  • 方法一：



  • 方法二：

  • 阿斯顿

    2.3 链表练习

  • 阿斯顿







  • 阿斯顿