数据结构与算法-链表

简介

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

代码示例
package *;

/**
 * @program: data-structure
 * @description: 链表实现
 * @author: ChenWenLong
 * @create: 2019-09-10 09:27
 **/
public class MyLinked<T> {
    Node head = null; // 头节点

    /**
     * 功能描述:
     * 〈链表中的节点,data代表节点的值,next是指向下一个节点的引用〉
     *
     * @params :
     * @return :
     * @author : cwl
     * @date : 2019/9/10 9:29
     */
    private class Node<T> {
        Node<T> next = null;// 节点的引用,指向下一个节点
        T data;// 节点的对象,即内容

        public Node(T data) {
            this.data = data;
        }
    }

    /**
     * 功能描述:
     * 〈向链表中插入数据〉
     *
     * @params : [d]
     * @return : void
     * @author : cwl
     * @date : 2019/9/10 9:29
     */
    public void addNode(T d) {
        Node newNode = new Node(d);// 实例化一个节点
        if (head == null) {
            head = newNode;
            return;
        }
        Node tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = newNode;
    }

    /**
     * 功能描述:
     * 〈根据索引删除节点〉
     *
     * @params : [index]
     * @return : boolean
     * @author : cwl
     * @date : 2019/9/10 9:29
     */
    public boolean deleteNode(int index) {
        if (index < 1 || index > length()) {
            return false;
        }
        if (index == 1) {
            head = head.next;
            return true;
        }
        int i = 1;
        Node preNode = head;
        Node curNode = preNode.next;
        while (curNode != null) {
            if (i == index) {
                preNode.next = curNode.next;
                return true;
            }
            preNode = curNode;
            curNode = curNode.next;
            i++;
        }
        return false;
    }

    /**
     * 功能描述:
     * 〈返回节点长度〉
     *
     * @params : []
     * @return : int
     * @author : cwl
     * @date : 2019/9/10 9:30
     */
    public int length() {
        int length = 0;
        Node tmp = head;
        while (tmp != null) {
            length++;
            tmp = tmp.next;
        }
        return length;
    }

    /**
     * 功能描述:
     * 〈删除指定节点〉
     *
     * @params : [n]
     * @return : boolean
     * @author : cwl
     * @date : 2019/9/10 9:30
     */
    public boolean deleteNode11(Node<T> n) {
        if (n == null || n.next == null) {
            return false;
        }
        T tmp = n.data;
        n.data = n.next.data;
        n.next.data = tmp;
        n.next = n.next.next;
        System.out.println("删除成功!");
        return true;
    }

    /**
     * 功能描述:
     * 〈打印节点〉
     *
     * @params : []
     * @return : void
     * @author : cwl
     * @date : 2019/9/10 9:31
     */
    public void printList() {
        Node tmp = head;
        while (tmp != null) {
            System.out.println(tmp.data);
            tmp = tmp.next;
        }
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

30段极简Python代码:这些小技巧你都Get了么

Python 是机器学习最广泛采用的编程语言,它最重要的优势在于编程的易用性。如果读者对基本的 Python 语法已经有一些了解,那么这篇文章可能会给你一些启发...

9110
来自专栏LINUX阅码场

何兴鹏: select函数源码简析

select()允许一个程序监听多个文件描述符,等待一个或者多个文件描述符的I/O操作变成“就绪”状态(比如:可读)。

6220
来自专栏SIGAI学习与实践平台

理解支持向量机

支持向量机是机器学习中最不易理解的算法之一,它对数学有较高的要求。之前SIGAI微信公众号已经发过“用一张图理解SVM脉络”,“理解SVM的核函数和参数”这两篇...

10820
来自专栏LINUX阅码场

两个非常有意思的适合桌面使用的Linux task调度器: BFS和MuqSS

大家都知道Linux内核task调度器经历了O(n),O(1)调度器,目前是CFS,期间也出现了几个优秀的候选调度器,但最终都没能并入内核,我们只能从一些零散的...

15220
来自专栏CDA数据分析师

Python 分析国庆热门旅游景点,告诉你哪些地方好玩、便宜、人又少!

使用Python分析出国庆哪些旅游景点:好玩、便宜、人还少的地方,不然拍照都要抢着拍!

8510
来自专栏EffectiveCoding

关于java 中的main函数

我们刚开始写java 程序最常见的除了System.out.println( );之外应该就是 public static void main( String ...

11320
来自专栏攻城狮的那点事

Java垃圾回收机制详解(面试题)

每个对象都有一个引用计数器,当对象被引用一次计数器就加 1;当引用失效时计数器就减 1。当对象的计数器为 0 时,对象就是要被回收的。简单高效,缺点是无法解决对...

20520
来自专栏小海怪python学习

javascript第3讲:数据类型(ES5中)

7220
来自专栏苦逼的码农

经典面试题:最长回文子串

回文串是面试常常遇到的问题(虽然问题本身没啥意义),本文就告诉你回文串问题的核心思想是什么。

7320
来自专栏算法工程师之路

回溯法+约束编程-LeetCode37(数独扫雷问题、Tuple使用)

在Python中,大家都知道tuple这个概念,是一个只读的元素容器,容器内的元素数据类型可以不同,而在CPP中大部分的容器只能储存相同数据类型的数据,而std...

11320

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励