链表的顶级理解

这篇具有很好参考价值的文章主要介绍了链表的顶级理解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1.链表的概念及结构

2.链表的分类

 单向或者双向

 带头或者不带头

 循环或者非循环

3.无头单向非循环链表的实现

 3.1创建单链表

3.2遍历链表

3.3得到单链表的长度

3.4查找是否包含关键字

3.5头插法

 3.6尾插法

3.7任意位置插入

3.8删除第一次出现关键字为key的节点

3.9回收链表

3.10完整代码


1.链表的概念及结构

概念:

链表是一种 物理存储结构上非连续 存储结构,数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。

结构:

链表的顶级理解,链表,数据结构,java,其他,经验分享

链表的顶级理解,链表,数据结构,java,其他,经验分享

实际在内存中每个节点的地址是随机的,只不过用这个节点的next,找到了下一个节点的地址,实现链接。 


2.链表的分类

 实际中链表的结构非常多样

链表的顶级理解,链表,数据结构,java,其他,经验分享

 以下情况组合起来就有8种链表结构:

链表的顶级理解,链表,数据结构,java,其他,经验分享

 单向或者双向

链表的顶级理解,链表,数据结构,java,其他,经验分享

 带头或者不带头

链表的顶级理解,链表,数据结构,java,其他,经验分享

 循环或者非循环

 链表的顶级理解,链表,数据结构,java,其他,经验分享

 我们重点掌握无头单向非循环链表,这种结构在笔试面试中出现很多。并且可以触类旁通其他结构。


3.无头单向非循环链表的实现

链表的功能与顺序表类似,无非是增删查改,在某位置的插入与删除,对数据内容进行管理和操作。

具体实现内容:

(1)创建单链表
(2)遍历链表
(3)得到单链表的长度
(4)查找是否包含关键字
(5)头插法
(6)尾插法
(7)任意位置插入
(8)删除第一次出现关键字为key的节点
(9)回收链表

 3.1创建单链表

public class MyLinkedList {
    class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;// 代表当前链表的头节点的引用
}

3.2遍历链表

public void disPlay() {
        Node sur = head;
        while(sur  != null) {
            System.out.print(sur.val+" ");
            sur = sur.next;
        }
    }

3.3得到单链表的长度

进行遍历,并进行记录,最后进行返回就行

public int size(){
        int count = 0;
        Node cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

3.4查找是否包含关键字

对链表进行遍历,然后一一比

 //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node cur = head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

3.5头插法

将第一个节点的地址赋给我们新添加的节点的next,并且将新添加的节点赋给head,作为新的头节点

  public void addFirst(int data){
        Node node = new Node(data);
        node.next = head;
        head = node;
    }

 3.6尾插法

首先对该链表进行遍历,当遍历到最后一个节点时,将新添加的节点的地址最后一个节点的next。

如果该链表为空,直接将该新增节点设为头节点

 public void addLast(int data){
        Node node = new Node(data);
        if(head == null) {
            head = node;
            return;
        }
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

3.7任意位置插入

需要插入的位置必须为合法,如果不合法,我们会抛出一个异常进行提醒

public class ListIndexOutOfException extends RuntimeException{
    public ListIndexOutOfException() {
    }

    public ListIndexOutOfException(String message) {
        super(message);
    }
}

任意位置插入,我们可以分为种情况,插在开头,插在结尾,插在中间

插在结尾和插在中间可以总结成一种

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data)
            throws ListIndexOutOfException{
        checkIndex(index);
        if(index == 0) {
            addFirst(data);
            return;
        }
       
        Node cur = findIndexSubOne(index);
        Node node = new Node(data);
        node.next = cur.next;
        cur.next = node;
    }

    /**
     * 找到 index-1位置的节点的地址
     * @param index
     * @return
     */
    private Node findIndexSubOne(int index) {
        Node cur = head;
        int count = 0;
        while (count != index-1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }
    private void checkIndex(int index) throws ListIndexOutOfException{
        if(index < 0 || index > size()) {
            throw new ListIndexOutOfException("index位置不合法");
        }
    }

3.8删除第一次出现关键字为key的节点

分为四种情况

(1)一个节点都没有
(2)删除数据在第一个
(3)没有你要删除的数据
(4)有你要删除的数据且不是第一个

//删除第一次出现关键字为key的节点 O(N)
    public void remove(int key)throws ListIndexOutOfException{
        checkIndex(key);
        if(head == null) {
            return ;//一个节点都没有
        }
        //删除数据在第一个
        if(head.val == key) {
            head = head.next;
            return;
        }
        Node cur = searchPrev(key);
         //没有你要删除的数据
        if(cur == null) {
            return;
        }
        Node del = cur.next;//要删除的节点
        cur.next = del.next;
    }

    /**
     * 找到关键字key的前一个节点
     * @param key
     * @return
     */
    private Node searchPrev(int key) {
        Node cur = head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;//没有你要删除的节点
    }

3.9回收链表

将头节点置为空

public void clear() {
        head = null;
    }

3.10完整代码

public class MyLinkedList {
    class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;// 代表当前链表的头节点的引用
    public void disPlay() {
        Node sur = head;
        while(sur  != null) {
            System.out.print(sur.val+" ");
            sur = sur.next;
        }
    }
    public int size(){
        int count = 0;
        Node cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node cur = head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    public void addFirst(int data){
        Node node = new Node(data);
        node.next = head;
        head = node;
    }
    public void addLast(int data){
        Node node = new Node(data);
        if(head == null) {
            head = node;
            return;
        }
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data)
            throws ListIndexOutOfException{
        checkIndex(index);
        if(index == 0) {
            addFirst(data);
            return;
        }

        Node cur = findIndexSubOne(index);
        Node node = new Node(data);
        node.next = cur.next;
        cur.next = node;
    }

    /**
     * 找到 index-1位置的节点的地址
     * @param index
     * @return
     */
    private Node findIndexSubOne(int index) {
        Node cur = head;
        int count = 0;
        while (count != index-1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }
    private void checkIndex(int index) throws ListIndexOutOfException{
        if(index < 0 || index > size()) {
            throw new ListIndexOutOfException("index位置不合法");
        }
    }



    //删除第一次出现关键字为key的节点 O(N)
    public void remove(int key)throws ListIndexOutOfException{
        checkIndex(key);
        if(head == null) {
            return ;//一个节点都没有
        }
        //删除数据在第一个
        if(head.val == key) {
            head = head.next;
            return;
        }
        Node cur = searchPrev(key);
        //没有你要删除的数据
        if(cur == null) {
            return;
        }
        Node del = cur.next;//要删除的节点
        cur.next = del.next;
    }

    /**
     * 找到关键字key的前一个节点
     * @param key
     * @return
     */
    private Node searchPrev(int key) {
        Node cur = head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;//没有你要删除的节点
    }

    public void clear() {
        head = null;
    }

}

以上为我个人的小分享,如有问题,欢迎讨论!!! 

都看到这了,不如关注一下,给个免费的赞 链表的顶级理解,链表,数据结构,java,其他,经验分享

 链表的顶级理解,链表,数据结构,java,其他,经验分享文章来源地址https://www.toymoban.com/news/detail-666652.html

到了这里,关于链表的顶级理解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】链表的分类和双向链表

    本篇是基于上篇单链表所作,推荐与上篇配合阅读,效果更加 http://t.csdnimg.cn/UhXEj 链表的结构非常多样,以下情况组合起来就有8种(2 x 2 x 2)链表结构: 我们一般叫这个头为哨兵位 我们上回讲的单链表就是不带头单项不循环链表。 今天我们要讲带头双向循环的链表。 不过

    2024年01月25日
    浏览(39)
  • 数据结构-二叉链表的结构与实现

    目录 一、引言 二、什么是二叉链表 三、二叉链表的结构 四、二叉链表的实现 1. 创建二叉链表 2. 遍历二叉链表 3. 插入节点 4. 删除节点 五、应用场景 六、总结 七、代码示例 数据结构是计算机科学中的重要概念,它是计算机程序设计的基础。二叉链表是一种常见的数据结构

    2024年02月08日
    浏览(49)
  • 数据结构----链表介绍、模拟实现链表、链表的使用

    ArrayList底层使用连续的空间,任意位置插入或删除元素时,需要将该位置后序元素整体往前或者往后搬移,故时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后

    2024年02月21日
    浏览(51)
  • 【数据结构】十字链表的画法

    有向边又称为弧 假设顶点 v 指向 w,那么 w 称为弧头,v 称为弧尾 顶点节点采用顺序存储 顶点节点 data:存放顶点的信息 firstin:指向以该节点为终点(弧头)的弧节点 firstout:指向以该节点为起点(弧尾)的弧节点 弧节点 tailvex:起点(弧尾)在数组中的索引 headvex:终点(

    2024年02月11日
    浏览(49)
  • 【数据结构】双向链表的实现

    我要扼住命运的咽喉,他却不能使我完全屈服。                      --贝多芬 目录 一.带头循环的双向链表的特点 二.不带头不循环单向链表和带头循环的双向链表的对比 三.初始化链表,创建哨兵结点 四.双向链表的各种功能的实现 1.双向链表的尾插 2.双向链表的打印 

    2023年04月10日
    浏览(47)
  • 数据结构——双向链表的实现

    注意: 双向链表又称带头双向循环链表 这⾥的“带头”跟前⾯我们说的“头节点”是两个概念,实际前⾯的在单链表阶段称呼不严 谨,但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表⾥的头节点,实际为“ 哨兵位 ”,哨兵位节点不存储任何有效元素,只

    2024年02月06日
    浏览(48)
  • 【(数据结构)— 双向链表的实现】

    注意: 这里的 “带头” 跟前面我们说的 “头节点” 是两个概念,实际前面的在单链表阶段称呼不严 谨,但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表里的头节点,实际为 “哨兵位” ,哨兵位节点不存储任何有效元素,只是站在这里“放哨 的” “哨

    2024年02月06日
    浏览(46)
  • 数据结构中链表的实现以及排序

    本期和大家主要分享的是关于数据结构中双向链表的实现过程,那么话不多说,来具体看看吧! 来分析一下,这里呢定义了一个int的数据类型,表明整个链表存放的是整形的数据;其次定义了链表节点的数据类型,其中包括了此节点存放的数据以及链接向下一个节点的地址;

    2024年02月02日
    浏览(46)
  • 数据结构---双向链表的基本操作

    头插法 遍历链表 尾插法 头删法 尾删法 按位置插入数据 按位置删除数据 dooublelinklist.c doublelinklist.h doublemain.c

    2024年02月22日
    浏览(53)
  • 探索数据结构:双向链表的灵活优势

    ✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯,先赞后看哦~🎈🎈 所属专栏:数据结构与算法 贝蒂的主页:Betty’s blog 前面我们学习了单链表,它解决了顺序表中插入删除需要挪动大量数据的缺点。但同时也有仍需改进的地方,比如说:我们有时候需要寻找某个节点

    2024年03月16日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包