数据结构基础 ——数组VS链表(二)

一、数组

    数组对应的英文是array,是有限个相同类型的变量所组成的有序集合,数组中的每一个变量称为元素。数组是最简单、最常用的数据结构。

数组存储格式:

 在Python语言中,并没有直接使用数组这个概念,而是使用列表(list)和元组( tuple)这两种集合,它们本质上都是对数组的封装。其中,列表是一个动态可扩展的数组,支持任意地添加、删除、修改元素;而元组是一个不可变集合,一旦创建就不再支持修改。

 数据结构的操作无非是增、删、改、查4种情况!

二、数组的基本操作

 1、读取元素

print(ll[3])

 2、更新元素

ll[5]=100

print(ll[5])

可知: 数组读取元素和更新元素的时间复杂度都是O(1)。
 

 3、添加元素

    插入元素有3种情况:

  1. 尾部插入
  2. 中间插入
  3. 超范围插入

 (1)尾部插入,是最简单的情况,直接把插入的元素放在数组尾部的空闲位置即可,等同于更新元素的操作。

 

(2)中间插入,稍微复杂一些。由于数组的每一个元素都有其固定下标,所以不得不首先把插入位置及后面的元素向后移动,有个空位置,再把要插入的元素放到对应的数组位置上。

class MyArray:
    '''初始化'''

    def __init__(self, capcity):
        self.arrs = [None] * capcity  # 数组
        self.size = 0  # 大小

    '''添加'''

    def add(self, index, value):
        # 判断是否超出范围
        if index < 0 or index >= self.size:
            raise Exception('数组下标越界!')
        # 将数据往后移动,直到index这个位置为止
        for i in range(self.size - 1, index - 1, -1):
            self.arrs[i + 1] = self.arrs[i]

        # 插入新数据
        self.arrs[index] = value
        # 个数
        self.size += 1

    '''显示'''

    def show(self):
        for i in range(self.size):
            print(self.arrs[i], end=',')
if __name__ == '__main__':
    # 创建对象
    my = MyArray(4)
    #在第一个位置添加数据
    my.add(0, 8)
    my.add(0, 10)
    my.add(0, 20)
    my.add(0, 2)
    # IndexError: list assignment index out of range
    # my.add(0,15)

    #显示数据
    my.show()

(1) 索引正常范围

 

 (2)索引超出范围

 (3)如现在有一个长度为6的数组,已经装满了元素,这时还想插入一个新元素。

   解决方法:  可以创建一个新数组,长度是旧数组的2倍,再把旧数组中的元素统统复制过去,这样就实现了数组的扩容。

 #创建一个新数组,其容量扩大旧数组2倍,再把原数组拷贝到新数组中
    def resize(self):
        self.arrnews=[None]*len(self.arrs)*2
        #旧数组的数据拷贝到新数组中
        for i in range(self.size):
            self.arrnews[i]=self.arrs[i]
        #再把新数组给旧数组
        self.arrs=self.arrnews



    '''添加'''
    def add(self, index, value):
        # 判断是否超出范围
        if index < 0 or index > self.size:
            raise Exception('数组下标越界!')

        #如果超出范围,就扩容
        if self.size>=len(self.arrs):
            self.resize()

        # 将数据往后移动,直到index这个位置为止
        for i in range(self.size - 1, index - 1, -1):
            self.arrs[i + 1] = self.arrs[i]

        # 插入新数据
        self.arrs[index] = value
        # 个数
        self.size += 1
if __name__ == '__main__':
    # 创建对象
    my = MyArray(6)
    #在第一个位置添加数据
    my.add(0, 8)
    my.add(0, 10)
    my.add(0, 20)
    my.add(0, 2)
    my.add(0, 7)
    my.add(0, 3)
    # IndexError: list assignment index out of range
    # my.add(100,200)
    for i in range(30,41):
         my.add(0,i)
    #显示数据
    my.show()

(1) 数组大小超出范围,直接扩容2倍

(2)索引超出范围

 4、删除元素

        数组的删除操作和插入操作的过程相反,如果删除的元素位于数组中间,其后的元素都需要向前挪动1位。

 '''删除数据'''
    def remove(self,index):
       if index<0 or index>self.size:
           raise Exception('数组下标越界!')
       #从右往左移动,直到indx
       for i in range(index,self.size):
           self.arrs[i]=self.arrs[i+1]
       #个数减少
       self.size-=1
if __name__ == '__main__':
    # 创建对象
    my = MyArray(6)
    #在第一个位置添加数据
    my.add(0, 8)
    my.add(0, 10)
    my.add(0, 20)
    my.add(0, 2)
    my.add(0, 7)
    my.add(0, 3)
    # IndexError: list assignment index out of range
    # my.add(100,200)
    for i in range(30,41):
         my.add(0,i)

    #显示数据
    my.show()

    my.remove(3)
    # my.remove(23)

    my.show()

 数组拥有非常高效的随机访问能力优势,数组的劣势体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中,插入、删除元素都会导致大量元素*移动,影响效率。

总的来说,数组所适合的是读操作多、写操作少的场景。

三、链表

链表(linked list〉是一种在物理上非连续、非顺序的数据结构,由若干节点(node)所组成。

(1) 单向链表的每一个节点又包含两部分,一部分是存放数据的变量data,另一部分是指向下一个节点的指针next

(2) 双向链表比单向链表稍微复杂一些,它的每一个节点除了拥有data和next指针,还拥有指向前置节点的prev指针

数组在内存中的存储方式是顺序存储,而链表在内存中的存储方式则是随机存储。 

数组的内存分配方式


链表的内存分配方式
 

四、链表的基本操作

1、查找节点

     从头节点开始找第3个节点

  

class Node:  #新节点
    def __init__(self,data):
        self.data=data
        self.next=None

class MyLinkedList:
     '''初始化 大小,头部,尾部'''
     def __init__(self):
         self.size=0
         self.head=None
         self.tail=None

     '''根据索引查找数据'''
     def get(self,index):
         if index<0 or index>self.size:
             raise  Exception('超出链表节点范围!')
         p=self.head
         for i in range(index):
             p=p.next
         return p

2、更新节点

     从头节点开始找第2个节点进行修改

3、添加节点

与数组类似,在链表中插入节点时,同样分为3种情况:

  1. 尾部插入
  2. 头部插入
  3. 中间插入
  • 尾部插入

最后一个节点的next指针指向新插入的节点

  • 头部插入
  1. 把新节点的next指针指向原先的头节点。
  2. 把新节点变为链表的头节点。

  • 中间插入
  1. 新节点的next指针指向插入位置的节点。
  2. 插入位置前置节点的next指针,指向新节点。

   

  '''添加新节点'''
     def insert(self,data,index):
         if index < 0 or index > self.size:
             raise Exception('超出链表节点范围!')
         #获取节点对象
         node=Node(data)
         #空链表
         if self.size==0:
             self.head=node
             self.tail=node
         #插入头部
         elif index==0:
             node.next=self.head  #将新节点指向原先的头节点
             self.head=node  #新节点变为链表的头节点
         #插入尾部
         elif self.size==index:
             self.tail.next=node #尾节点指向新节点
             self.tail=node   #新节点变为链表的尾节点
         #插入中间
         else:
             prev_node=self.get(index-1) #获取前一个节点
             node.next=prev_node.next  #新节点指向插入位置的节点
             prev_node.next=node  #前置节点指向新节点
         self.size+=1
if __name__ == '__main__':
   my= MyLinkedList()
   for i in range(5):
        my.insert(20+i,i)
       
   #my.insert(100,10)
   my.show()

4、删除节点

链表的删除操作同样分为3种情况:

  1. 尾部删除
  2. 头部删除
  3. 中间删除
     
  1. 尾部删除

      2.头部删除

     3.中间删除

 

 '''删除节点'''
     def remove(self, index):
         if index < 0 or index > self.size:
             raise Exception('超出链表节点范围!')
         #删除头节点
         if index==0:
             del_node=self.head  #删除头节点
             self.head=self.head.next #指向头节点next成为头节点
         #删除尾节点
         elif index==self.size-1:
             prev_node = self.get(index - 1) #获取前一个节点
             del_node = prev_node.next  #删除前个节点next
             prev_node.next=None  #前一个节点为空
             self.tail=prev_node  #尾节点指向前节点
         #删除中间节点
         else:
             prev_node=self.get(index-1)  #获取前节点
             next_node=prev_node.next.next   #获取前节点的下一个节点
             del_node=prev_node.next #删除节点
             prev_node.next=next_node #前节点指向下个节点
         self.size-=1
         return del_node



     '''显示'''
     def show(self):
         # 头节点
         p=self.head
         #循环节点是否为空
         while p is not None:
             print(p.data)  #打印节点
             p=p.next   #指向下一个节点指针next
         print('*'*30)

if __name__ == '__main__':
   my= MyLinkedList()
   for i in range(5):
        my.insert(20+i,i)

   my.show()

    my.remove(3)
   #my.remove(30)

   my.show()

五、数组VS链表

   总之: 数组在于能够快速定位元素,对于读操作多写操作少的场景来说,用数组更合适一些。链表的优势在于能够灵活地进行插入和删除操作,如果需要频繁插入、删除元素,用链表更合适一些。

上一篇:【C++】类和对象①(什么是面向对象 | 类的定义 | 类的访问限定符及封装 | 类的作用域和实例化 | 类对象的存储方式 | this指针)


下一篇:农业现代化:UWB模块为农业领域带来的效益和便利