数据结构--单向链表篇（python实现）

写在开头

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)

链表的优缺点

优点

• 不需要预先知道数据大小，实现灵活的内存动态管理

• 插入、删除指定数据速度快

缺点

• 读取指定位置数据速度慢

• 空间开销比较大

链表的分类

单向链表

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值

双向链表

一种更复杂的链表是“双向链表”或“双面链表”

每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）

循环链表

在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现

要转换一个循环链表，可以开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点

循环链表中第一个节点之前就是最后一个节点，反之亦然

数组 VS 链表

单向链表

单链表的基本操作

节点的创建
初始化单向链表
插入节点
头节点
中间节点
尾节点
删除节点
访问节点
查找节点

初始化单链表

需要初始化node类(需要一个节点)

class ListNode:
  def __init__(self, val: int):
    self.val: int = val        # 节点值
    self.next: ListNode | None = None # 指向下一节点的引用

创建链表

class MyLinkedList:
  def __init__(self):
    self.size = 0
    self.head = ListNode(0)

插入节点

插入数据

这个方法写完了可以直接在添加头节点和添加尾节点的地方直接进行调用

插入节点的方法本质上都是往哪一个地方插入，无论是头节点或者尾节点，因此我们可以将插入的方法写出一个通用的方法

 def add_at_index(self, index:int, val:int):
    '''
     将val的值增加到指定index索引的位置
     :index 索引  0<=index<=size
     '''
    # 判断索引是否有效
    if index > self.size:
      return
    index = max(0, index) 
    # 创建新节点
    add_node = LinkNode(val)
    # 获取头节点
    pred = self.head
    # 根据index找到前驱节点
    for _ in range(index):
      pred = pred.next
    # 将新节点的下一个节点 指向 前驱节点的 下一个节点
    add_node.next = pred.next
    # 将前驱节点的下一个节点 指向 新节点
    pred.next = add_node
    # 链表长度+1
    self.size += 1

插入头节点

def add_at_head(self, val: int) -> None:
  self.add_at_index(0, val)

插入尾节点

def add_at_tail(self, val: int) -> None:
  self.add_at_index(self. Size, val)

获取数据

获取单链表中第index个节点

def get(self,index:int) -> int:
    '''
     获取index索引位置的值
     '''
    # 判断索引是否有效
    if index < 0 or index >= self.size:
      return -1
    #  获取头节点
    pred = self.head
    # 遍历链表，index次
    for _ in range(index+1):
      pred = pred.next
    # 返回index索引位置的值
    return pred.val

删除数据

如果索引index有效，则删除链表中的第index个节点

def delete_at_index(self,index:int) -> None:
    '''
     删除index索引位置的值
     '''
    # 判断索引是否有效
    if index < 0 or index >= self.size:
      return
    # 获取头节点
    pred = self.head
    # r遍历链表，index次,找到前驱节点
    for _ in range(index):
      pred = pred.next
    pred.next = pred.next.next
    # 链表长度-1
    self.size -= 1

遍历链表

def traverse(self):
  cur = self.head.next # 从头节点的下一个节点开始遍历
  while cur: # 当当前节点不为空时
    # 对当前节点执行特定操作，例如打印节点的值
    print(cur.val)
    cur = cur.next # 移动到下一个节点

写在最后

单向链表不难，可以这样理解，链表中的每一个元素称之为节点，每个节点都包含两部分，用来存放具体信息的和用来存放指向下一个节点位置的（你可以想象为单线联系，你不知道你的上线是谁，但你知道你的下线在哪，每次想要找到你们这个组织中的某个谁，都必须从这个组织的开头进行查找，所以是On的复杂度），添加节点就是组织上又加入了一个人，你可以选择把它放在组织中的任何位置，前提是得在组织中，你得让他的上级知道它有了下级，并且给它指定一个下级（如果有的话），删除节点就是这个人在这个组织中没有上线和下线了（将指向该节点的指针指向别处），没人搭理你了，你就被删除了。

理解完简单的概念之后，在画个图加深一下印象，相信单向链表对你而言也是非常轻松的。