Press "Enter" to skip to content

数据结构之链表

之前介绍的动态数组,都是以用户的角度来看的,实际栈,队列底层都是依托于静态数组实现的,靠resize来解决固定容量问题。但是这次所说的链表是真正的动态数据结构(最简单的)

为什么链表是很重要的数据结构:

  • 真正的动态数据结构
  • 更深入的理解引用或者指针
  • 更深入的理解递归
  • 辅助组成其它数据结构

链表

数据存储在节点(Node)中

优点:真正的动态,不需要处理固定容量的问题

缺点:丧失了随机访问的能力

数组和链表的对比

  • 数组最好用于索引|有语意的情况。scores[2]
  • 最大的优点:支持快速查询
  • 链表不适合用于索引有语意的情况。
  • 最大的优点:动态

在链表中添加元素

对于链表来说,我们要想访问链表中的所有节点,我们必须将链表的头存储起来,通常叫head,在类中我们应该有一个node类型的变量head指向链表中的第一个节点,而每次的添加相当于循环head->next的节点添加内容

在链表头添加元素

假设我们此时要将666这个元素添加到链表的头部,我们如何不破坏链表的原有数据结构
只需要两句

node.next = head;
head = node;

在链表中间添加元素


在链表中,实际没有索引这个概念,只是借助索引 ,假设我们如果要往索引为2的节点添加666这个元素 ,首先 需要创建666这个节点,找到666之前的节点,把666之前的节点的next指向666,把666的next指向他之前的这个节点的之后的节点就完成了插入,如下图

要注意的是,这个替换的顺序很重要假设调换赋值顺序,如
prev.next=node;
node.next=prev.next;

将会出现数据错乱

删除元素

删除元素和添加元素基本类似,都是定位之前一个删除元素之前的元素
修改元素指向才是改变链表的本质(修改元素并不能改变链表)

链表的时间复杂度分析

添加操作O(n)

  • addLast($e)  O(n)
  • addFirst($e)  O(1)
  • add($index,$e)  O(n/2) = O(n)

删除操作O(n)

  • removeLast($e)  O(n)
  • removeFirst($e)  O(1)
  • remove($index,$e)  O(n/2) = O(n)

修改操作O(n)

  • set($index,$e)   O(n)

查找操作 O(n)

  • get($index)  O(n)

从上我们可以得知 链表的增删改查的复杂度都是O(n)级别,比起数组来说链表整体的时间复杂度要差

不过对于链表来说,如果我们只对链表的头进行操作,响应的时间复杂度是O(1)级别的

其实对于链表来说,它适合做的事情其实是不去修改,而对于查也不能任意的元素 ,而只查链表头的元素,而增加和删除的时候也只对链表头进行操作

使用链表实现栈
使用链表实现递归
使用链表实现队列
leetcode 203号题目(除链表元素)

在本人的github可以参考
https://github.com/htmax/Play-with-Data-Structures

根据链表理解递归

什么是递归?
所谓递归,简单点来说,就是一个函数直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
本质上,将原来的问题,转化为更小的同一问题
举例:数组求和
Sum(arr[0…n-1] ) = arr[0] + Sum( arrr[1…n-1]) ← 更小的同一问题
Sum( arr[1…n-1]) = arr[1] + Sum( arr[2…n-1] ) ← 更小的同一问题
……………………………………………………
Sum( arr[n-1…n-1]) = arr[n-1] + Sum( [] )        ←最基本的问题

class Sum
{
    public static function sums($arr, $l)
    {
        if ($l < 0 || $l == count($arr) || $l > count($arr)) {
            return 0;
        }

        return $arr[$l] + self::sums($arr, $l + 1);
    }
}

$arr = [1, 2, 3, 4, 5, 6, 7, 8];
echo Sum::sums($arr, 0);

注意递归函数的“宏观”语意,递归函数就是一个函数,完成一个功能,我们在写递归函数的时候,不需要陷进递归调用里去纠结这个递归是怎样调用的,我们可以把递归想象成一个子函数,子函数的功能就是解决上层的逻辑,很多时候我们这样想象递归,对于正确的写出递归函数很有帮助

链表具有天然的递归结构
对于链表我们可以理解成一个一个节点的挂接,也可以理解成一个头节点后面又挂接了一个更短的链表,也可以理解成1后面又挂接了一个更短的链表,以此类推知,直到最后,我们可以理解成空本身也是一个链表 ,空就是最基础的链表,有了这种思考,其实对于链接中的很多操作都可以利用递归的方式完成

例子:LeetCode中第203号问题,链表中删除元素 ,实现代码在github

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

分析这个问题

对于最原始的链表我们可以把他理解成是头节点e后面跟了一个更短的链表,假设我们现在已经有了一个函数,函数的功能就是删除这个更小的链表中相应的元素
假定 我们执行完了这个操作之后,剩下的元素是这个红色的链表,对于我们的原问题其实就是没有考虑一个头节点,如果头节点e不需要删除,那么原问题就是这个头节点e后面挂接上我们这个子问题求得的这个链表,如果e需要删除,那么最终的结果就是我们后续求出来的这个红色的链表,这样我们就递归的把链表中删除元素这个问题解决了

class ListNode
{
    public $val  = 0;
    public $next = null;

    function __construct($val)
    {
        $this->val = $val;
    }
}


class Solution {

    /**
    * @param ListNode $head
    * @param Integer $val
    * @return ListNode
   */
function removeElements($head, $val) {
    if ($head == null) {
        return null;
    }

    $head->next = $this->removeElements($head->next, $val);

    return $head->val == $val ? $head->next : $head;
    }
}

递归函数的”微观”解读

首先我们看一下之前栈的调用例子,子函数调用

执行A函数的第二行去调用B函数,执行B函数的第二行去调用了C函数,其实递归调用本质上和这种子函数调用没有区别,不过我调用的子函数还是这个函数本身而已

我们还用之前的数组求和的例子来举例

假设我们的数组只有两个元素arr = [6,10]
调用sum(arr,0);求出数组第0个元素到最后一个元素的和
第一步判断 if( l==n) 不等于,继续向下执行
此时我们进入了递归调用
其实就是调用了sum(arr ,1)
继续判断 if( l==n) 不等于,继续向下执行
继续进行递归调用,其实就是调用了sum(arr ,2)
if( l==n) 等于 返回 0
返回到第二步
x=0
res =arr[1]+x; ==>  res =10+0;
再返回到第一步
x=10
res =arr[0]+x; ==>  res = 6+10;
res =16

我们进一步的微观解读 链表中删除元素这个例子


模拟调用,对6- >7->8- ->null删除7
红色的圆圈①②③代表代码中的步数
调用步骤:

  1. 步head不等于空,执行第步,递归调用
    传入链表head->next  =7->8->NULL
  2. 步head不等于空,执行第步,递归调用
    传入链表head->next  = 8->NULL
  3. 步head不等于空,执行第步,递归调用
    传入链表head->next  =NULL
  4. 步head等于NULL 返回

返回步骤:

  1. 返回上一步的第行调用,head->next = NULL ,此时head=8->NULL,执行第步,判断head->val  == 7 不等于,返回head
  2. 返回上一步的第行调用,head->next=8->NULL 执行第步,此时head=7->8->NULL,判断head->val  == 7 等于 ,返回head->next = 8->NULL
  3. 返回上一步的第行调用,head = 6->8->NULL,执行第步,判断head->val  == 7 不等于 head不变 head = 6->8->NULL

此时我们回到栈 将ABC都改为调用A其实与递归一致

递归调用是有代价的:函数调用+系统栈空间

更多和链表相关的问题
关于递归
近乎和链表相关的所有操作,都可以使用递归的形式完成

双链表

 

每个数据结点中都有两个指针,分别指向前一个节点和后一个节点。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点,由于有两个节点所以维护起来稍微比单链表复杂一点

循环链表


循环链表的好处是进一步把很多操作进行了统一,比如说我们在链表结尾添加一个元素,我们就不需要tail节点一直指着结尾,可以直接在虚拟头节点dummyHead的前面添加一个元素,它就等于是在整个链表的结尾添加了一个元素,java的链表类LinkedList底层实现是循环双向链表

数组链表
(明确知道链表的数量,有优势)

数组链表的关键是next是一个int型,指向的是下一个节点的索引,对于数组来说索引不可能为负数,所以-1代表链表已经结束,在某种情况下,如果你明确知道你要处理的元素是多少个,这种情况下使用数组链表是更加方便的

Leave a Reply

Your email address will not be published. Required fields are marked *