前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构与算法-链表

数据结构与算法-链表

作者头像
cwl_java
发布2019-10-26 21:14:58
2770
发布2019-10-26 21:14:58
举报
文章被收录于专栏:cwl_Java
简介

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

代码示例
代码语言:javascript
复制
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;
        }
    }

}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/10/18 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 简介
  • 代码示例
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档