线性表你还不知道原理?给老王整的明明白白

简介: 线性表你还不知道原理?给老王整的明明白白

一、线性表必知必懂的原理

(一)线性表通俗易懂原理

线性表是n个数据元素的有限序列,最常用的是链式表达,通常也叫做线性链表或者链表在链表中存储的数据元素也叫做结点,一个结点存储的就是一条数据记录

每个结点的结构包括两个部分:

  • 1、具体的数据值;
  • 2、指向下一个结点的指针。

在链表的最后一个结点,通常会有个头指针用来指向第一个结点

对于链表的最后一个结点,由于在它之后没有下一个结点,因此它的指针是个空指针

假如:小明,小张,小李和小郑在排队卖鸡翅,但是排队就是讲究先来先买的原则,不能插队。小明再购买鸡翅付钱的时候突然没钱了,假设小明和小郑认识,小明需要找到小郑借钱来付上买鸡翅的钱。。。那么小明想要找到小郑,就需要先找到他的下一个结点,一看不是小郑,就继续下一个结点,直到找到为止。

小明是可以找到小郑的,但是小郑就无法找到小明了,也就是说单链表反过来查找是不行的,也被称之为单向链表

为了弥补单向链表的不足,我们可以对单向链表进行改造:

对于单向链表,把最后一个元素的指针指向第一个元素,就得到了循环链表

这样小郑就可以查找他自己的next结点,就可以找到小明或者小李等。

由于单向链表一个结点只有指向下一个结点的指针,可以想象一下,是不是也可以修改成每个结点也指向上一个结点,是不是就可以找到自己上一个结点的数据了呢。

我们再增加一个指向上一个结点的指针,这样就得到了双向链表

当然了,还有更好的办法,那就是把循环链表双向链表进行结合就得到了双向循环链表

不管是循环链表还是双向链表,还是双向循环链表,都是在单向链表的基础上加以改造得到的,改造后的链表在操作某种数据的时候可以提高一定的效率,所以单向链表是基础。

二、线性表对数据的操作

对数据的操作无非就是对数据的增删改查。只是不同的结构有着不同的处理逻辑罢了。

(一)增加操作(老王插队神操作)

小明、小张、小李、小郑在排着队取票,突然来了一个老王,老王非常的着急,因为老王马上就要到火车发车的时间了,只好插队了,此时老王跟后面所有的排队的人都打了个招呼,然后大家也都同意他插队进去,那么老王就先去取票了,我们忽略打招呼的过程,重点放在如何插队

我们先不管如何插入到链表中的,先看图说话

老王如果想插队必定插入到小明的后面,因为老王在插队的过程中小明此时可能会正在取票呢。

那么插入老王后的数据就是:

整个插入操作也非常的简单,只需要让老王的next指向小张,然后小明再指向老王就ok了。

思考一下????

反过来操作可以吗?

小明先指向老王老王的next指向小张

可以吗?

答案是不可以的,这样的话,小明先指向老王之后,小张以及小张之后的数据会全部丢失的。不信你看:

代码如下:

newNode.next = head.next
head.next = newNode

(二)删除操作(小明取完票让位给老王)

老王要想取到票,还欠一点火候,欠什么呢?需要等待小明取完票,然后离开才可以的。

那么就需要小明离开这个链表,我们通常说删除小明这个结点。

删除操作也比较简单,只需要把前一个结点指向后面的后面的这个结点就ok了。

代码:(直接就可以忽略小明这个结点)

head.next=head.next.next;

(三)查找操作

查找操作我们通常会查两种,第一种是按照位置的序号,第二种是按照值来查找。

例如:

  • 查找第3个位置的是谁;
  • 查找小张是否还在排队。

在链表中的查找功能是比较弱的,对于链表中的查找,唯一的办法就是一个挨着一个的遍历去对比,对比较着去查找。

时间复杂度也就是O(N)。

三、单链表案例

(一)案例1:反转链表

1、题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/reverse-linked-list

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


2、解题思路

3、解题代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null)
            return head;
        //定义三个指针暂存后面的或者前面的结点,防止丢失。
        ListNode curr,prev,next;
        curr=head;
        prev=next=null;
        while(curr!=null){
            next = curr.next;
            curr.next = prev;
            prev=curr;
            curr=next;
        }
        return prev;       
    }
}

如果不明白,可以自己画图来试试。

(二)案例2:找出链表的中间节点

1、题目描述

876. 链表的中间结点

难度简单256收藏分享切换为英文关注反馈

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

示例 1:

输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2:

输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。

提示:

  • 给定链表的结点数介于 1100 之间。

https://leetcode-cn.com/problems/middle-of-the-linked-list/

2、解题思路

思路很简单,就是利用两个指针来完成,一个走的比较快的,一个走的比较慢的。

每次快的走2个(next.next),每次慢的走1个节点(next)。

当快等于null时(next.next=null时),停止;

当快的next不为空时,返回慢的next节点。

当快的next为空时,返回慢的当前节点。

3、解题代码

//找出链表中间节点
    static public ListNode middleNode(ListNode head) {
        if(head==null)
            return head;
        ListNode fast,//快
                slow;//慢
        fast=slow=head;
        while (fast!=null && fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast.next!=null)
            return slow.next;
        return slow;
    }

(三)案例3:判断链表是否有环

1、题目描述

141. 环形链表

难度简单738收藏分享切换为英文关注反馈

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos-1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

2、解题思路

此题也是可以利用快慢指针来完成的,同样,快指针一次走两步,慢指针一次走一步,如果有环的话,快和慢两个指针早晚会相遇的。那么如果快指针的val等于慢指针的val那么直接返回true即可。

3、解题代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
         if(head==null)
            return false;
        ListNode fast,slow;
        fast=slow=head;
        while (fast!=null && fast.next!=null && fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast.val==slow.val)
                return true;
        }
        return false;
    }
}

四、链表总结

链表对数据的存储方式是按照顺序的存储。


什么时候用?

  • 当数据元素不确定时。
  • 当需要经常进行数据的新增和删除时。

链表的反转、快慢指针是高效的操作链表的主要方法,是必须要掌握的内容。

目录
相关文章
用试题这把“剑“帮你破除指针与数组之间的那些猫腻
用试题这把“剑“帮你破除指针与数组之间的那些猫腻
61 0
|
算法 Go C语言
02【C语言 & 趣味算法】借书方案问题:小明有5本新书,要借给A、B、C三位小朋友,若每人每次只能借1本,则可以有多少种不同的借法?
02【C语言 & 趣味算法】借书方案问题:小明有5本新书,要借给A、B、C三位小朋友,若每人每次只能借1本,则可以有多少种不同的借法?
02【C语言 & 趣味算法】借书方案问题:小明有5本新书,要借给A、B、C三位小朋友,若每人每次只能借1本,则可以有多少种不同的借法?
|
存储
数据结构上机实践第八周项目6- 猴子选大王(数组版)
数据结构上机实践第八周项目6- 猴子选大王(数组版)
166 0
数据结构上机实践第八周项目6- 猴子选大王(数组版)
数据结构上机实践第四周项目5 - 猴子选大王
数据结构上机实践第四周项目5 - 猴子选大王
152 0
数据结构上机实践第四周项目5 - 猴子选大王
|
存储 程序员 C++
【数据结构初阶】单链表补充内容+又双叒叕刷链表题
【数据结构初阶】单链表补充内容+又双叒叕刷链表题
63 0
【数据结构初阶】单链表补充内容+又双叒叕刷链表题
|
存储 算法 索引
代码随想录算法训练营第六天 | 哈希表 四道简单题
代码随想录算法训练营第六天 | 哈希表 四道简单题
95 0
|
算法 NoSQL Redis
关于跳表,这么解释你肯定能听懂
如何用 30s 给面试官讲清楚什么是跳表
117 0
关于跳表,这么解释你肯定能听懂
|
人工智能
一本通-加分二叉树+分离与合体(区间DP+记录方案)
一本通-加分二叉树+分离与合体(区间DP+记录方案)
140 0
L2-029 特立独行的幸福 (25 分)(数组模拟)
L2-029 特立独行的幸福 (25 分)(数组模拟)
124 0
★色盲悖论正解!
假设:有一个人,他有一种奇怪的色盲症。他看到的两种颜色和别人不一样,他把蓝色看成绿色,把绿色看成蓝色。   但是他自己并不知道他跟别人不一样,别人看到的天空是蓝色的,他看到的是绿色的,但是他和别人的叫法都一样,都是“蓝色”;小草是绿色的,他看到的却是蓝色的,但是他把蓝色叫做“绿色”。
2709 0