数据结构基础 ——数组VS链表（二）

本是古典何须时尚 2024-04-20 12:27 51阅读 0赞

## 一、数组 ##

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

数组存储格式：

![8ef590f11478406993654ba80e578c13.png][]

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

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

### **二、数组的基本操作** ###

1、读取元素

> print(ll\[3\])

2、更新元素

> ll\[5\]=100
> 
> print(ll\[5\])

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

3、添加元素

> 插入元素有3种情况：
> 
> 1.  尾部插入
> 2.  中间插入
> 3.  超范围插入

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

![2e6ed0c5a91241caac9900affc7ff2bd.png][]

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

![9a52553bc6db4927b600d595ea524a32.png][]

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） 索引正常范围**

![0234f7f2f5d749eb8dfd65d7fbb1ed21.png][]

**（2）索引超出范围**![2b3dd47a43034e738d7bf4832a156d97.png][]

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

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

![f135d3c5108a4381bc731d1c05b83fed.png][]

#创建一个新数组，其容量扩大旧数组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倍**

![854a119200d443e5a778ca2749d47ecc.png][]

**（2）索引超出范围**

![2081db7b90474ae3bdfc7d49a01ffc9f.png][]

4、删除元素

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

![54d99a82d03c4602a4915717ccea2d65.png][]

'''删除数据'''
        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

![7921be052d3549eebe085082bdd10343.png][]

![1943753d0d184368a0e3fba0662816ed.png][]

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

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

## **三、链表** ##

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

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

![d66e4cd8fb54427f8ad3f022ad80effb.png][]

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

![63d6bded75b3412c9857eabe06f1a31e.png][]

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

数组的内存分配方式

![116cbe215a664fe386817ccd65423710.png][]  
链表的内存分配方式  
![862aa8c9c0524c6f9aeb91edb77372ac.png][]

## 四、链表的基本操作 ##

**1、查找节点**

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

![505a3a95a66949ffa7ff03d050a17bde.png][]

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个节点进行修改**

![6c471b03effa41c6ac85a6a66e5af817.png][]

**3、添加节点**

> 与数组类似，在链表中插入节点时，同样分为3种情况:
> 
> 1.  尾部插入
> 2.  头部插入
> 3.  中间插入

*  尾部插入

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

![6e6d9fd469204daebdc178cb2d632cf7.png][]

*  头部插入

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

![8660b6c347e04bffbabb076d856daa0e.png][]

*  中间插入

> 1.  新节点的next指针指向插入位置的节点。
> 2.  插入位置前置节点的next指针，指向新节点。

![12b42cd10f674336b890c3c098fcf078.png][]

'''添加新节点'''
         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()

![67a3d1dfbf004907a321e79afad9afdd.png][]

![6d097e2cc1454eae8cb7092a7064a88c.png][]

**4、删除节点**

> 链表的删除操作同样分为3种情况:
> 
> 1.  尾部删除
> 2.  头部删除
> 3.  中间删除  
>

1.  尾部删除

![be388b99dc9a47aab71556c3f4d584a5.png][]

2.头部删除

![e85f50271da24337a066a3fec75d6421.png][]

3.中间删除

![e1edff4024f9420f9ff4760c37f461ed.png][]

'''删除节点'''
         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()

![9af5030344144f6d97d391af6783a6fb.png][]

![9a5cdef1e3514440b72276e95cb5a6e2.png][]

### 五、数组VS链表 ###

![b00688cd4de541f0be485f19a6cca85f.png][]

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

[8ef590f11478406993654ba80e578c13.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/9fbe572402ae4faf9cfb93681476fb27.png
[2e6ed0c5a91241caac9900affc7ff2bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a91bd05f48c542e7b34cf9087e929297.png
[9a52553bc6db4927b600d595ea524a32.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/83177d006c30409caacf654525aa3694.png
[0234f7f2f5d749eb8dfd65d7fbb1ed21.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/9c7345531f024bbbb57902bdc9e8f84a.png
[2b3dd47a43034e738d7bf4832a156d97.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/65e2948d263e4e85be13f3ed73840263.png
[f135d3c5108a4381bc731d1c05b83fed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/2f2fb4898968459d8132ae690d591d0a.png
[854a119200d443e5a778ca2749d47ecc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/dab7c26c285244669107a4d7978a56e3.png
[2081db7b90474ae3bdfc7d49a01ffc9f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/c6242e66424547f8b07b4ca2b059c593.png
[54d99a82d03c4602a4915717ccea2d65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/f9fb3bf959834ec9ae599472756a3fb0.png
[7921be052d3549eebe085082bdd10343.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/75d09aa333d94fe39a039ebea9e01052.png
[1943753d0d184368a0e3fba0662816ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/6a0351d8168043e69dd88078667e6b7b.png
[d66e4cd8fb54427f8ad3f022ad80effb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/7c57c5702452473486e294a810e5c395.png
[63d6bded75b3412c9857eabe06f1a31e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a3e737ce8ee4499ea23ea19d2928c54a.png
[116cbe215a664fe386817ccd65423710.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/027bd3fb2bb14aef95b53ec9ad2532cb.png
[862aa8c9c0524c6f9aeb91edb77372ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/fef300fb40bc43ed96f5b9de14f294a0.png
[505a3a95a66949ffa7ff03d050a17bde.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/d89d323d7df24bf0b6a7268b5e9cde9a.png
[6c471b03effa41c6ac85a6a66e5af817.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/587f7f0b19ee4839b7070c777de99c82.png
[6e6d9fd469204daebdc178cb2d632cf7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a5bf600f28e847dd91674e1ca566153c.png
[8660b6c347e04bffbabb076d856daa0e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/4fdb7fbf07354e5ba2efb1e8a6c6e915.png
[12b42cd10f674336b890c3c098fcf078.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/af7411c3632545b4b2b5d1e97554d884.png
[67a3d1dfbf004907a321e79afad9afdd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/3f43928b3b9043b2a1e708552d1c5bdf.png
[6d097e2cc1454eae8cb7092a7064a88c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/3434e3306bcf47bba83097492bedd34b.png
[be388b99dc9a47aab71556c3f4d584a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/b1ce5cf3e6eb4af8a86df1983915e25b.png
[e85f50271da24337a066a3fec75d6421.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/cbd8a059a48e47db9d8ec8100c81e383.png
[e1edff4024f9420f9ff4760c37f461ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/063de394c4aa4443bf5815c27272ae7f.png
[9af5030344144f6d97d391af6783a6fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/b75530c69ca3459f82ffae06a6cffbf4.png
[9a5cdef1e3514440b72276e95cb5a6e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/b68215e553284d26a5583cdcb7829e01.png
[b00688cd4de541f0be485f19a6cca85f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a991cc9997c04e3ab56110102e5686fc.png