数据结构与算法 数组和链表

简介: 数据结构与算法 数组和链表

数组

python 数组都是动态数组,长度是自动变化的,所以不需要数组的扩容操作,这也是python运行要比C,Java慢的原因之一

列表: 由于数组长度不可变导致实用性降低,创建了一种动态数组的数据结构,称为列表

所以严格意义来说,python里面的数组就是列表

列表的代码(硬要定义数组不可变化)

class MyList:
    def __init__(self):
        self.__capacity = 10
        self.__nums = [0] * self.__capacity
        self.__size = 0
        self.__extend_ratio: 2
    def size(self):
        return self.__size
    
    def capacity(self):
        return self.__capacity
    
    def get(self, index):
        if index < 0 or index > self.__size:
            raise IndexError('索引越界')
        return self.__nums[index]
        
    def set(self, index, val):
        if index < 0 or index > self.__size:
            raise IndexError('索引越界')
        self.__nums[index] = val
    
    def add(self, val):
        if self.__size == self.__capacity:
            self.__capacity *= self.__extend_ratio
        self.__nums[self.__size] = val
        self.__size += 1
    def insert(self, index, val):
        if index < 0 or index > self.__size:
            raise IndexError('索引越界')
        for i in range(index, self.__size-1):
            self.__nums[i+1] = self.__nums[i]
        
        self.__nums[i] = val
        self.__size += 1
    def remove(self, index):
        if index < 0 or index > self.__size:
            raise IndexError('索引越界')
        
        for i in range(index, self.__size-1):
            self.__nums[i] = self.__nums[i+1]
        
        self.__size -= 1
    
    def extend_capacity(self):
        self.__nums += [0]*self.__capacity*(self.__extend_ratio - 1)
        self.__capacity = len(self.__nums)

链表

链表的代码:

class ListNode:
  def __init__(self, value):
  self.value = value
  self.next = None
  self.prev = None

对比

重点

  • 数组和链表是两种基本的数据结构,分别代表数据在计算机内存中的两种存储方式:连续空间存储和离散空间存储。两者的特点呈现出互补的特性。
  • 数组支持随机访问、占用内存较少;但插入和删除元素效率低,且初始化后长度不可变。
  • 链表通过更改引用(指针)实现高效的节点插入与删除,且可以灵活调整长度;但节点访问效率低、占用内存较多。常见的链表类型包括单向链表、循环链表、双向链表。
  • 动态数组,又称列表,是基于数组实现的一种数据结构。它保留了数组的优势,同时可以灵活调整长度。列表的出现极大地提高了数组的易用性,但可能导致部分内存空间浪费。


目录
相关文章
|
2天前
数据结构 链表(第7、8天)
数据结构 链表(第7、8天)
|
2天前
|
算法 索引 Python
数据结构 数组部分小结
数据结构 数组部分小结
|
2天前
|
存储
数据结构——带头双向循环链表
数据结构——带头双向循环链表
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
6天前
|
存储
初阶数据结构 带头双链表
初阶数据结构 带头双链表
8 0
|
6天前
数据结构初阶 链表的补充
数据结构初阶 链表的补充
7 0
|
6天前
|
存储
数据结构初阶 链表详解
数据结构初阶 链表详解
7 0
|
7天前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
7天前
|
存储 SQL 算法
LeetCode第53题:最大子数组和【python 5种算法】
LeetCode第53题:最大子数组和【python 5种算法】