数据结构——链表——渔舟唱晚

[409229455_9361 (渔舟唱晚)]

链表与数组的区别

• 复杂度分析

时间复杂度	数组	链表
插入删除	O(n)	O(1)
随机访问	O(1)	O(n)

• 其他角度分析

  • 内存连续，利用CPU的机制，可以预读链表中的数据，故访问效率高
  • 而数组在内存中并不是连续存储的，所以CPU缓存不友好，没办法预读
  • 数组的大小不固定，及时动态申请，也需要拷贝数据，费时费力
  • 链表支持动态扩容
  • 链表的缺点是：存储空间大

单链表和循环链表

• 区别在于头结点与尾结点是否相连
• 循环链表从尾部可以直接到达头，适合环形数据结构，比如约瑟夫问题

双向链表优点

1. 找到上一个结点的时间复杂度为O(1)

2. 插入、删除操作更高效

   • 删除结点中“值等于给定值”的结点
   • 删除指定指针指向的结点

代码实现单链表

# 链节点类
class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None


# 链表类
class LinkedList:
    def __init__(self):
        self.head = None

    # 根据 data 初始化一个新链表
    def create(self, data):
        self.head = ListNode(0)
        cur = self.head
        for i in range(len(data)):
            node = ListNode(data[i])
            cur.next = node
            cur = cur.next

    # 获取链表长度
    def length(self):
        count = 0
        cur = self.head
        while cur:
            count += 1
            cur = cur.next
        return count

    # 查找元素
    def find(self, val):
        cur = self.head
        while cur:
            if val == cur.val:
                return cur
            cur = cur.next

        return None

    # 头部插入元素
    def insert_to_head(self, val):
        node = ListNode(val)
        node.next = self.head
        self.head = node

    # 尾部插入元素
    def insert_to_tail(self, val):
        node = ListNode(val)
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = node

    # 中间插入元素
    def insert_to_middle(self, index, val):
        count = 0
        cur = self.head
        while cur and count < index - 1:
            count += 1
            cur = cur.next

        if not cur:
            return 'Error'

        node = ListNode(val)
        node.next = cur.next
        cur.next = node

    # 改变元素
    def change(self, index, val):
        count = 0
        cur = self.head
        while cur and count < index:
            count += 1
            cur = cur.next

        if not cur:
            return 'Error'

        cur.val = val

    # 链表头部删除元素
    def remove_head_element(self):
        if self.head:
            self.head = self.head.next

    # 链表尾部删除元素
    def remove_tail_element(self):
        if not self.head.next:
            return 'Error'

        cur = self.head
        while cur.next.next:
            cur = cur.next
        cur.next = None

    # 链表中间删除元素
    def remove_middle_element(self, index):
        count = 0
        cur = self.head

        while cur.next and count < index - 1:
            count += 1
            cur = cur.next

        if not cur:
            return 'Error'

        del_node = cur.next
        cur.next = del_node.next