数组与链表

本是古典何须时尚 2023-06-16 10:51 2阅读 0赞

数组

一、基本概念

1、什么数组？

数组是一种 **线性表**的数据结构。它用一组 **连续**的内存空间，来存储一组具有 **相同类型**的数据。

2、数组是如何实现下标随机访问数组元素的？

我们拿一个长度为10的数组来举例，在下面的图中，计算机给数组分配了一块连续的内存空间，其中内存的首地址为base\_address=1000。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70][]

每次获取数据的时候，计算机都会根据下面的寻址公式计算出元素的存储的内存地址

a[i]_address = base_address + i * data_type_size

3、数组和链表的区别是什么？

*  数组支持随机访问，链表不可以
 *  数组需要连续内存空间，链表是一组零散的内存块。

4、数组的插入操作

（1）假设数组的长度为n，现在，如果我们需要将一个数据插入到数组中的第K个位置，为了把第K个位置腾出来，给新来的数据，我们需要将第k~n的位置往后挪。

如果在数组的末尾插入元素，那就不需要移动数据，此时的时间复杂度为O(1)，而如果在数组的第一个位置插入元素，那么就要移动后面的n个元素，此时的时间复杂度为o(n)，因为在任何位置插入元素的概率都是一样的，所以平均时间复杂度为O((1+2+3+4+...+n)/n) = O(n+1/2) = O(n)

但是，如果我们的数组不要求有序的话，那么我们插入的时候只需要将第k个位置的元素放到最后，然后在k处插入我们的元素。此时时间复杂度为O（1）

5、数组的删除操作

如果要求数组是有序的话，那么时间复杂度和插入一样。

下面来说说数组是无序的情况下。

如果无序的时候，为避免元素移动，我们可以只将要被删除的元素删除，而不去搬移数据（比如js数组，可以置为null），当数组没有更多空间存储了，我们再去真正的删除操作，并且移动数组。

6、需要时刻警惕数组的访问越界的问题。

7、二维数组的寻址公式

对于m\*n的数组：

a[i]_address = base_address + （i*n+j）*byte

8、利用链表来实现LRU缓存策略（最近最少使用策略）（使用次数是有序的）

利用一个有序数组，当有数据需要缓存的时候遍历数组

1.  如果数据已经存在数组中了，则将此数据插入到数组头部，并将头部至数据原来位置的数据往后移一个位置。
2.  如果数据不存在数组中，

*  如果此时缓存已满，则将数组最后一个元素删除掉，把数组中所有数据往后移动，把数据插入到数组头部。
 *  如果此时缓存未满，则将数据插入到头部，然后所有数据往后移

链表

1、链表与数组的区别

首先从底层的存储结构来看

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 1][]

数组需要的是一块连续的内存空间来进行存储，如果计算机没有连续的足够大小的存储空间就会申请失败。 **而链表并不需要连续的内存空间，它通过指针，将一组零散的内存块串联起来。**

2、链表的结构

链表中最常见的三种结构分别是单链表，双链表，循环链表。

（1）单链表

链表通过指针将一组零散的内存块串联起来，这里的内存块就是链表的结点，为了将所有的链表串联起来，每个链表的结点除了存储数据意外，还需要记录链上的下一个结点的地址，称为后继指针next

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 2][]

单链表有两个很重要的结点，头结点和尾结点，一般链表指向的变量的就是头结点的地址，它记录着链表的基地址。而尾结点的next指向的是一个null空地址，代表链表已经没有后续结点了。

链表的插入和删除都比较简单，因为它不用搬移后面的结点，但是找到需要插入位置的前继结点，需要根据指针一个一个结点依次遍历，直到找到相应的结点，所以它的插入和删除时间复杂度都是O(n)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 3][]

(2)循环链表

循环链表就是在单链表的基础上，尾结点的next不再指向null，而是指向头结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 4][]

（3）双向链表

双向链表是在单链表的基础上，每个结点多了一个前继指针prev，指向前一个结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 2][]

双向链表比单链表多了一个存储空间，为什么我们还要用它呢？

虽然插入操作中，双向链表跟单链表时一样的时间复杂度，但是在删除操作中，双向链表还是比单链表有优势的：

从链表中删除一个数据无非就两种情况：

*  删除结点中指定给定值的结点
 *  删除指定指针指向的结点

第一种情况，两种链表的操作都差不多，主要是第二种，

删除一个结点需要它的前继结点，因为需要修改它next指针指向的结点，如果是单链表，则还是需要遍历链表，判断结点的next是否指向特定的结点。但是双向链表，拥有prev，只要修改prev指向结点的next和next结点的prev就可以了。此时单链表的时间复杂度是O(n)，而双向链表的时间复杂度是O(1)。

双向链表主要的思想就是用空间换时间，当内存足够的时候，为了加快代码的执行速度，那么就可以选择空间复杂度相对较高，但是时间复杂度相对较低的算法或数据结构，否则相反。

缓存实际上就是利用了空间换时间的设计思想。

3、利用链表来实现LRU缓存策略（最近最少使用策略）

利用一个有序的单链表，越靠近链表尾部的就是越早访问的，每次有新的数据访问的时候，就遍历一次链表，

1.  如果此数据之前已经存在链表中了，那么就把这个结点在原来的位置删除并移到链表头部。
2.  如果此前没有存在链表中：

*  如果缓存未满，则将其插入链表头部。
 *  如果缓存已满，则将链表尾部的结点删除，将数据插入到链表头部。

链表与数组性能

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 5][]

链表代码书写技巧

1、一定要警惕指针丢失和内存泄漏！比如留意指针的指向问题，删除的时候要对删除结点释放内存空间。

2、针对链表的插入、删除操作，需要对 **插入第一个结点和删除最后一个结点**的情况进行特殊处理。为了解决这个问题，链表可以加一个头结点，head指针总是指向这个结点，因此这样的链表叫做带头链表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 6][]

3、重点留意边界条件处理。

*  如果链表 **为空**，代码是否能正常工作
 *  如果链表只包含 **一个结点**的时候，代码是否能正常工作
 *  如果链表只包含 **两个结点**的时候，代码是否能正常工作
 *  代码逻辑在处理 **头结点和尾结点**的时候，是否能正常工作。

4、用js实现链表

（1）单链表

//初始化结点
    class Node{
        constructor(key){
            this.next = null
            this.key = key
        }
    }
    //初始化单链表
    class List{
        constructor(){
            this.head = null
            this.length = 0
        }
    
    
        //创建结点
         static createNode(key){
            return new  Node(key)
         }
    
    
         //往头部插入数据
         insert(node){
            if (this.head){
                //此时head有指向的结点
                node.next = this.head
            } else {
                node.next = null
            }
            this.head = node
            this.length++
         }
         //删除结点
         delete(node){
            //删除的结点时头结点指向的结点
             //删除的结点是尾结点
             //删除的结点时列表中间的结点
             if (node == this.head){
                 this.head = node.next
                 this.length --;
                 return;
             }
             let prev = this.head
             while (prev.next!=node){
                 prev = prev.next
             }
    
             if (node.next == null){
                 prev.next = null
             }
             if (node.next){
                 prev.next = node.next
             }
             this.length --;
         }
    }

（2）双向链表

//初始化结点
    class Node{
        constructor(key){
            this.next = null
            this.prev = null
            this.key = key
        }
    }
    
    //初始化链表
    class List{
        constructor(){
            this.head = null
            this.length = 0
        }
    
        //创建结点
         static createNode(key){
            return new  Node(key)
         }
    
         //往头部插入数据
         insert(node){
             node.next = this.head
             node.prev = null
            if (this.head){
                //此时head有指向的结点
                this.head.prev = node
            } else {
                node.next = null
            }
            this.head = node
            this.length++
         }
         //删除结点
         delete(node){
            //删除的结点时头结点指向的结点
             //删除的结点是尾结点
             //删除的结点时列表中间的结点
             if (this.head == node){
                 node.next.prev = null
                 this.head = node.next
                 this.length --
                 return
             }
    
             if (node.next){
                 node.prev.next = node.next
                 node.next.prev = node.prev
             }else {
                 //最后一个结点
                 node.prev.next = null
             }
         }
    }

5、常见链表操作

（1）单链表反转

var reverseList = function(head) {
        //如果空链表或者链表只有一个结点就返回原来的链表
        if (head == null || head.next == null) {
            return head
        }
        //遍历链表，将当前结点与上一个结点进行交换，prev用来存储当前结点
       let prev = null,cur = head
      while (cur){
          let temp = cur.next
          cur.next = prev
          prev = cur
          cur = temp
      }
        return prev
    
    
    };

算法题练习

字符回文数判断

回文判断（函数）

编写一个函数int isPalindrome(char s\[\])，判断参数表示的字符串是否是回文，如果是返回1，否则返回0。在主函数中调用它，判断输入的字符串是否是回文，如果是，输出“yes”，如果不是，输出”No”。

回文的定义：“回文数”就是正读倒读都一样的字符串

输入

测试数据的个数 t

第一个字符串

第二个字符串

…….

输出

如果是，输出“yes”，如果不是，输出”No”

样例输入

abba

abcba

样例输出

Yes

function huiwen(str) {
         if(str<0){
           return false
         }
         str +=''
        let length = str.length
        let t = length/2
        let flag = true
        for (let i=0;i<t;i++){
            console.log(str[i],str[length-i-1])
            if (str[i] != str[length-i-1]){
                flag = false
                break
            }
        }
        if (flag){
            console.log(str,'yes')
        } else {
            console.log(str,'no')
        }
    }
    huiwen(10)
    huiwen('abcba')
    huiwen('ab')

![20191126111526329.png][]

空间复杂度O(1)， **空间复杂度看额外的内存消耗**，而不是看数组本身存储需要多少空间！！

时间复杂度O(n)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191126111522640.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191126111526371.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191126111526379.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191126111526393.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191126111526370.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191126111526398.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191126181850241.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw==,size_16,color_FFFFFF,t_70
[20191126111526329.png]: https://img-blog.csdnimg.cn/20191126111526329.png